【排序算法 上】带你手撕常见排序 (插入,希尔,选择,堆排序) (动图详解)

这篇具有很好参考价值的文章主要介绍了【排序算法 上】带你手撕常见排序 (插入,希尔,选择,堆排序) (动图详解)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

欢迎来到 Claffic 的博客 💞💞💞

【排序算法 上】带你手撕常见排序 (插入,希尔,选择,堆排序) (动图详解)“东风随春归,发我枝上花。”

前言: 

排序是日常生活中极其常见的一种算法,它的功能很简单,就是将数字按照升序/降序排列,最终形成一组有序的数字,不过形成有序数字的过程有多种实现方式,它们各有好坏,接下来,由我带你手撕排序算法。


目录

🥰写在前面 

💐Part1.插入排序 

1.1直接插入排序

1.1.1思想

1.1.2实现 

1.2希尔排序

1.2.1思想

1.2.2实现

🌺Part2:选择排序 

2.1选择排序

2.1.1思想

2.1.2实现

2.2堆排序

2.2.1思想

2.2.2实现 


写在前面 

排序离我们的生活很近,这是一种很重要的算法,比如:

【排序算法 上】带你手撕常见排序 (插入,希尔,选择,堆排序) (动图详解)

网上购物按价格升序排序

【排序算法 上】带你手撕常见排序 (插入,希尔,选择,堆排序) (动图详解)

世界500强排名 

排序是常见的,也是重要的,寻找最优的排序能做到优化,所以理解掌握排序是必要的。

下面是要讲解的常见排序:

【排序算法 上】带你手撕常见排序 (插入,希尔,选择,堆排序) (动图详解)

我们默认实现排升序,一个一个来:

Part1.插入排序 

1.1直接插入排序

1.1.1思想

相信多数人是打牌的,你知道吗,在摸牌的时候,你就悄悄进行了插入排序操作:

【排序算法 上】带你手撕常见排序 (插入,希尔,选择,堆排序) (动图详解)

这种排序就是新拿到的数字与已有的数字进行比较,确定合适的位置后进行插入操作。

结合动图深度理解: 

【排序算法 上】带你手撕常见排序 (插入,希尔,选择,堆排序) (动图详解)

可以看到: 

• 当只有一个数字时,没有可比性,可理解为有序;

•  取下一个数字b,与前一个数字a比较,如果b小于a,则需要调整二者的位置,如果a小于b,符合升序,则不需要调整;

•  前一部分排好的数字逐渐增多,取此区间后最近的数字进行挨个比对,不是合适位置,比较过的数字就后移一位,是合适位置,就进行插入操作。

1.1.2实现 

// 插入排序
void InsertSort(int* a, int n)
{
	for (int i = 1; i < n; i++)
	{
		int tmp= a[i];
		int endi = i - 1;
		while (endi >= 0)
		{
			if (tmp < a[endi])
			{
				a[endi + 1] = a[endi];
				endi--;
			}
			else
				break;
			a[endi + 1] = tmp;
		}
	}
}

特征分析:

当原数字越接近有序时,效率越高;

时间复杂度:最好:O(N)  最坏:O(N^2);

空间复杂度:O(1);

稳定性(是否动了相同数字的相对位置)稳定

这个排序看起来效率并不高,希尔在快速排序的基础上进行了优化:

1.2希尔排序

1.2.1思想

本质还是插入排序,只不过希尔做了一个巧妙的处理:引入了 gap ,每隔一个gap分为一组;

先让一部分数字相对有序,再调整下一部分,直至最后有序;

【排序算法 上】带你手撕常见排序 (插入,希尔,选择,堆排序) (动图详解)

1.2.2实现

// 希尔排序
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		//gap /= 2;
		gap = gap/3 + 1;

		for (int i = 0; i < n - gap; i++)
		{
			int endi = i;
			int tmp = a[i + gap];
			while (endi >= 0)
			{
				if (tmp < a[endi])
				{
					a[endi + gap] = a[endi];
					endi -= gap;
				}
				else
					break;
				a[endi + gap] = tmp;
			}
		}
	}
}

意:gap是多少并没有明确规定,一般是 gap/3+1  

特征分析:

希尔排序是对直接插入排序的优化,给gap相当于进行预排序,当gap==1时数组就相当有序了,比起直接插入,会快一些;

时间复杂度:最好:O(N^1.25)~O(N^1.3) (参考《计算机程序设计技巧》--Knuth)  最坏:O(N^2);

空间复杂度:O(1);

稳定性:不稳定

Part2:选择排序 

2.1选择排序

2.1.1思想

这种排序方法是我们出厂自带的排序方法,试想:给你一堆乱序的数字,你会怎么排?

通常情况下,我们会从头到尾扫一遍,选出最小的放到最前面,再扫一眼,选出第二大的放到第二位。

这就是选择排序的基本思想。

动图: 

【排序算法 上】带你手撕常见排序 (插入,希尔,选择,堆排序) (动图详解)

是不是挺符合认知规律的? 

2.1.2实现

// 选择排序
void SelectSort(int* a, int n)
{
	int left = 0, right = n - 1;
	while (left < right)
	{
        // 初始化
		int mini = left;
		int maxi = left;
        // 找到较大/较小值的下标
		for (int i = left+1; i <= right; i++)
		{
			if (a[i] < a[mini]) // 前后顺序会影响结果
			{
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		Swap(&a[mini], &a[left]);
        // 调试过程中会有left与maxi重叠的情况,这时需要针对这种情况调整
		if (left == maxi)
			maxi = mini;
		Swap(&a[maxi], &a[right]);

		left++;
		right--;
	}
}

特征分析: 

直接选择排序思路易理解,但效率不高,不实用;

时间复杂度:最好:O(N^2)  最坏:O(N^2);

空间复杂度:O(1);

稳定性:不稳定 

2.2堆排序

2.2.1思想

堆排序在往期 什么是堆,如何实现?(附堆排序,TOP-K问题) 中有详解, 

先是建大堆,再是模拟删除操作,这里就不多说啦。

2.2.2实现 

//堆排序
void HeapSort(int* a, int n)
{
	//向下调整(效率更高)
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);

		end--;
	}
}

特征分析:

利用堆的特性,选数快很多,效率较高

时间复杂度:最坏:O(N*logN)  最好:O(N*logN) ;

空间复杂度:O(1);

稳定性:不稳定


总结:

这期是常见排序的前半部分,讲了两类排序:插入排序和选择排序,思想不难,多注意实现中的细节。我打算将后半部分放在下期:交换排序和归并排序。

码文不易 

如果你觉得这篇文章还不错并且对你有帮助,不妨支持一波哦  💗💗💗文章来源地址https://www.toymoban.com/news/detail-418324.html

到了这里,关于【排序算法 上】带你手撕常见排序 (插入,希尔,选择,堆排序) (动图详解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包