【数据结构--八大排序】之冒泡排序+选择排序+插入排序

这篇具有很好参考价值的文章主要介绍了【数据结构--八大排序】之冒泡排序+选择排序+插入排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【数据结构--八大排序】之冒泡排序+选择排序+插入排序,数据结构与算法,数据结构,算法,排序算法

💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃个人主页 :阿然成长日记 👈点击可跳转
📆 个人专栏: 🔹数据结构与算法🔹C语言进阶
🚩 不能则学,不知则问,耻于问人,决无长进
🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍

【数据结构--八大排序】之冒泡排序+选择排序+插入排序,数据结构与算法,数据结构,算法,排序算法

一、冒泡排序

1.原理:

🔸每次从a]0]开始,从左到右,相邻元素依次进行比较。
🔸每比较完一轮,序列中最大的一个或最小的一个就被换到了数组最后的位置,数组下标-1。
🔸继续从头开始下一轮。

2.流程图:

【数据结构--八大排序】之冒泡排序+选择排序+插入排序,数据结构与算法,数据结构,算法,排序算法

3.代码:

//冒泡排序
int* BubbleSort(int* a, int n)
{

	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 0; j < n - i - 1; j++)
		{
			if (a[j + 1] < a[j])
			{
				int tmp = a[j + 1];
				a[j + 1] = a[j];
				a[j] = tmp;
			}
		}
	}
	return a;
}

4.测试结果:

【数据结构--八大排序】之冒泡排序+选择排序+插入排序,数据结构与算法,数据结构,算法,排序算法

5.时间复杂度

O(N^2)文章来源地址https://www.toymoban.com/news/detail-722447.html

二、选择排序

1.原理:

🔸 第一次选择a[0]元素,开始向后遍历同时找最大值,和最小值,最大值放到末尾,最小值放到开头。
🔸第二次选择a[1]元素,开始向后遍历同时找最大值,和最小值,最大值放到末尾,最小值放到开头,直到到end-1位置。
🔸重复上述操作
注意:如果max在beain位置,会造成排序错误,只需max = min即可;

2.流程图:

此流程图是在遍历时只找最小值的方法;
而我们选择优化这个排序,通过在遍历时同时寻找最大值和最小值,来提升排序效率。
【数据结构--八大排序】之冒泡排序+选择排序+插入排序,数据结构与算法,数据结构,算法,排序算法

3.代码:

//选择排序
void SlectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	while(begin<end)
	{
		int max = begin;
		int min = begin;
		for (int i = begin+1; i <= end; i++)
		{
			if (a[min] > a[i])
			{
				min = i;
			}
			if (a[max] < a[i])
			{
				max = i;
			}
		} 
		//先交换最小值到左边,
		Swap(&a[begin], &a[min]);
		//特殊情况。如果max在beain位置,会造成排序错误
		if (begin == max)
		{
			max = min;
		}
		//在交换最大值到右边
		Swap(&a[end], &a[max]);
		begin++;
		end--;
	}
}

4.测试结果:

【数据结构--八大排序】之冒泡排序+选择排序+插入排序,数据结构与算法,数据结构,算法,排序算法

5.时间复杂度

O(N^2)

三、直接插入排序

1.原理:

🔹>内循环:每次取end+1下标位置值保存到tmp中,从end下标处向前作比较,如果比他小,就将该元素后移,如果大于或等于就停止,并将tmp值赋值给end+1位置,直到end小于0位置,
🔹>外循环:end++

2.流程图:

【数据结构--八大排序】之冒泡排序+选择排序+插入排序,数据结构与算法,数据结构,算法,排序算法

3.代码:

//直接插入排序
int* InsetSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
			}
			else
			{
				break;
			}
			end--;
		}
		a[end + 1] = tmp;
	}
	return a;
}

4.测试结果:

【数据结构--八大排序】之冒泡排序+选择排序+插入排序,数据结构与算法,数据结构,算法,排序算法

5.时间复杂度

O(N^2)

到了这里,关于【数据结构--八大排序】之冒泡排序+选择排序+插入排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包