devbox
酷酷是懒虫
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

排序算法：插入排序（直接插入排序、希尔排序）_采用插入排序方法进行排序.

作者：酷酷是懒虫 | 2024-06-19 14:54:35

赞

踩

采用插入排序方法进行排序.

朋友们、伙计们，我们又见面了，本期来给大家解读一下有关排序算法的相关知识点，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！

C 语 言 专 栏：C语言：从入门到精通

数据结构专栏：数据结构

个  人  主  页 ：stackY、

目录

 

前言：

1.排序的概念及其运用

1.1排序的概念

1.2排序的应用

1.3常见的排序算法

2.排序算法的实现

2.1插入排序

2.1.1基本思想

2.1.2直接插入排序

#直接插入排序完整代码：

2.1.3希尔排序 

#预排序

#直接插入排序

#希尔排序完整代码：

3.算法的效率比较

前言：

排序无处不在，在生活中我们无时无刻都在间接或者直接的使用排序这个方法，很多复杂的事情在经过排序之后都会变得简单许多。那么，在现阶段我们学习的数据结构一这块排序又该怎么实现呢？

1.排序的概念及其运用

1.1排序的概念

排序：
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.2排序的应用

比如我们电脑桌面上的应用的排序方式：

比如我们网购的时候也可以对商品进行排序：

比如2023中国高校排行榜：

 等等都是通过排序来展示出来的，所以可见排序无论是在哪个领域都应用广泛。

1.3常见的排序算法

如果大家想要测试自己的排序算法正确与否可以在这个OJ链接来进行测试：https://leetcode.cn/problems/sort-an-array/

2.排序算法的实现

2.1插入排序

2.1.1基本思想

直接插入排序是一种简单的插入排序法，其基本思想是：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为 止，得到一个新的有序序列 。
这其实就跟我们玩扑克牌一样，摸牌、插入：

2.1.2直接插入排序

当插入第 i(i>=1) 个元素时，前面的 array[0],array[1],…,array[i-1] 已经排好序，此时用 array[i] 的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将 array[i] 插入，原来位置上的元素顺序后移。
排升序：简单的总结就是在[0, end]这个区间中插入tmp，从end的位置开始比较，如果tmp小于end这个位置的元素，那么就将end往后面挪，然后与end-1这个元素再作比较（前提是：[0, end] 这个区间的元素有序）。

我们先来写出一趟插入排序的基本逻辑：

排升序：在[0,end]区间插入tmp，先比较tmp与end的大小关系，如果比end小，那么将end往后面挪一个，在用tmp和end-1比较，如果比end-1小，再将end-1往后挪，直到tmp比[0,end]区间中那个元素大，那么就停止，如果tmp比这个区间的所有数都要小，那么直接将tmp放在第一个位置即可。

代码演示： 

  1. //直接插入排序
  2. //在[0,end]插入tmp
  3. //升序
  4. void InsertSort(int* a, int n)
  5. {
  6.     //一趟插入排序
  7. 	int end;
  8. 	int tmp;
  9.     
  10. 	while (end >= 0)
  11. 	{
  12. 		if (a[end] > tmp)
  13. 		{
  14.             //挪数据
  15. 			a[end + 1] = a[end];
  16. 			end--;
  17. 		}
  18. 		else
  19. 		{    
  20. 			break;
  21. 		}
  22. 	}
  23.     //放数据
  24.     //走到这里有两种情况：
  25.     //1.tmp比a[end]大
  26.     //2.tmp比a中的任何数都小
  27.     a[end + 1] = tmp;
  28. }

完成了一趟的插入排序，那么怎么样实现在数组中排序呢？

第一次取数组的第一个元素直接放进去即可，第二次就需要和第一次放进去的元素进行比较，然后排成有序，也就是说我们可以将第一个元素看成有序，然后把后面的依次插入，所以呢，我们可以将已插入的数据看作是手里的手牌，未插入的数据看作牌堆的牌，我们每一次摸一张插入一张，这样子就实现了使用插入排序排序数组

#直接插入排序完整代码：

  1. //直接插入排序
  2. //在[0,end]插入tmp
  3. //升序
  4. void InsertSort(int* a, int n)
  5. {
  6. 	for (int i = 1; i < n; i++)
  7. 	{
  8. 		//一趟插入排序
  9. 		int end = i - 1;
  10. 		int tmp = a[i];
  11.  
  12. 		while (end >= 0)
  13. 		{
  14. 			if (a[end] > tmp)
  15. 			{
  16. 				//挪数据
  17. 				a[end + 1] = a[end];
  18. 				end--;
  19. 			}
  20. 			else
  21. 			{
  22. 				break;
  23. 			}
  24. 		}
  25. 		//放数据
  26. 		//走到这里有两种情况：
  27. 		//1.tmp比a[end]大
  28. 		//2.tmp比a中的任何数都小
  29. 		a[end + 1] = tmp;
  30. 	}
  31. }
直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)（最好的情况可以做到O(N)）
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

直接插入排序和冒泡排序比较：

通过上面的实现过程还看不出来插入排序的速度，我们可以和之前学过的  冒泡排序作一比较

冒泡排序的时间复杂度也为O(N^2)，那么使用它们两个算法分别来排升序一个原本就是升序的数组，那么即便数据一次都不需要挪动，冒泡排序还需要O(N^2)，但是直接插入排序只需要O(N)。所以直接插入排序在某种特殊情况下还是蛮快的。

2.1.3希尔排序 

希尔排序也被称为缩小增量排序

希尔排序法的基本思想是：
1.预排序：接近有序
2.插入排序

整体步骤就是确定一个整数值gap，然后间隔为gap，将所有数据分为gap组，对着gap组数据分别进行插入排序，最后再整体来一次插入排序，这个预排序的目的就是为了让数据接近有序，以便减少最后一次插入排序的时间。
例如要将：9 8 7 6 5 4 3 2 1 0 排成升序

#预排序

接下来我们就用代码来演示：

我们先不管gap怎么设置，在这里我们就先将gap设置为3

还是使用上面的例子：9 8 7 6 5 4 3 2 1 0 排成升序

1.先将这组数据分为gap组，然后分别对这gap组数据进行插入排序。

①我们先来进行一次排序，这次类比之前的直接插入排序不一样的是：先得保存下一个数据，因为往后面挪动数据会进行覆盖，然后每一次比较的是间隔为gap的数据：

代码演示：

  1. //希尔排序
  2. void ShellSort(int* a, int n)
  3. {
  4. 	int gap = 3;
  5.  
  6. 	//一次插入排序
  7. 	int end;
  8. 	//保存下一个位置的数据
  9. 	int tmp = a[end + gap];
  10. 	//比较、挪动
  11. 	while (end >= 0)
  12. 	{
  13. 		if (a[end] > tmp)
  14. 		{
  15. 			a[end + gap] = a[end];
  16. 			end -= gap;
  17. 		}
  18. 		else
  19. 		{
  20. 			break;
  21. 		}
  22. 	}
  23. 	a[end + gap] = tmp;
  24. }

②接着我们如何将这gap组中的其中一组进行排序呢？

这里要注意一个问题，对其中一组数据进行插入排序时每一次跳过的不是1，而是gap，并且end在往后面走的过程中不能大于n - gap，如果大于n - gap，那么tmp就会造成越界访问。

代码演示：

  1. //希尔排序
  2. void ShellSort(int* a, int n)
  3. {
  4. 	int gap = 3;
  5.  
  6. 	//              控制条件得注意、 步长要注意
  7. 	for (int i = 0; i < n - gap; i += gap)
  8. 	{
  9. 		//一次插入排序
  10. 		int end = i;
  11. 		//保存下一个位置的数据
  12. 		int tmp = a[end + gap];
  13. 		//比较、挪动
  14. 		while (end >= 0)
  15. 		{
  16. 			if (a[end] > tmp)
  17. 			{
  18. 				a[end + gap] = a[end];
  19. 				end -= gap;
  20. 			}
  21. 			else
  22. 			{
  23. 				break;
  24. 			}
  25. 		}
  26. 		a[end + gap] = tmp;
  27. 	}
  28. }

③进行完其中一组的排序，接下来就要进行gap组分别排序，如果我们仔细观察不难发现，当end为0的时候排序的是第一组，当end为1的时候排序的是第二组，那么我们可以再设置一个循环，以gap为控制循环条件：

代码演示：

  1. //希尔排序
  2. void ShellSort(int* a, int n)
  3. {
  4. 	int gap = 3;
  5.  
  6. 	//循环gap组，对gap组的数据分别进行插入排序
  7. 	for (int j = 0; j < gap; j++)
  8. 	{
  9. 		//              控制条件得注意、 步长要注意
  10. 		for (int i = j; i < n - gap; i += gap)
  11. 		{
  12. 			//一次插入排序
  13. 			int end = i;
  14. 			//保存下一个位置的数据
  15. 			int tmp = a[end + gap];
  16. 			//比较、挪动
  17. 			while (end >= 0)
  18. 			{
  19. 				if (a[end] > tmp)
  20. 				{
  21. 					a[end + gap] = a[end];
  22. 					end -= gap;
  23. 				}
  24. 				else
  25. 				{
  26. 					break;
  27. 				}
  28. 			}
  29. 			a[end + gap] = tmp;
  30. 		}
  31. 	}
  32. }

上面的代码用了三层循环，看起来是比较复杂的，但是我们可以进行改版一下，大家注意看代码的变化：

  1. //希尔排序
  2. void ShellSort(int* a, int n)
  3. {
  4. 	int gap = 3;
  5.  
  6. 	//对gap组数据分别进行插入排序
  7. 	for (int i = 0; i < n - gap; i++)
  8. 	{
  9. 		//一次插入排序
  10. 		int end = i;
  11. 		//保存下一个位置的数据
  12. 		int tmp = a[end + gap];
  13. 		//比较、挪动
  14. 		while (end >= 0)
  15. 		{
  16. 			if (a[end] > tmp)
  17. 			{
  18. 				a[end + gap] = a[end];
  19. 				end -= gap;
  20. 			}
  21. 			else
  22. 			{
  23. 				break;
  24. 			}
  25. 		}
  26. 		a[end + gap] = tmp;
  27. 	}
  28. }

很多老铁在这里看不懂改版之后代码，小编在这里带大家解释一下：首先上面的这两种代码的所需要的时间是完全没有区别的，如果使用三层循环，比较容易理解，改版之后的代码比较难理解，三层循环采用的是分组排序，两层循环采用的是多组并排（当i == 0时排序的是第一组第一个元素，当i == 1时排序的是第二组的第一个元素......以此类推就将这全部的数据排完了），这样解释应该就不难理解。

 这里采取自愿，两种方法的效率都是一样，没有区别，按照个人喜欢来自取。

#直接插入排序

当把gap组数据分别插入排序之后，还需要进行最后一次插入排序，那么最直接的方法就是直接在上面的代码的最后面再调用一次普通的插入排序即可，但是这未免有点太麻烦了，所以我们需要从gap下手，我们可以先来比较一下插入排序和希尔排序：

gap在这里决定了每一次的步长，所以：

gap越大，大的数可以更快的到后面，小的数可以更快的到前面，但是数据越不接近有序。

gap越小，大的数和小的数移动的比较缓慢，但是数据在移动完之后越接近有序。

gap == 1时，就是直接插入排序。

在上面排序10个数据的时候gap为3是比较合适的，但是如果要排序10000个数据，gap还是为3的话就有点挫了，所以gap的设定要根据元素个数来进行确定，然后在排序到最后一次时gap得是1，为了完成最后一次的直接插入排序。

#希尔排序完整代码：

  1. //希尔排序
  2. void ShellSort(int* a, int n)
  3. {
  4. 	//1. gap > 1：预排序
  5. 	//2. gap == 1 ：直接插入排序
  6.  
  7. 	int gap = n;
  8. 	while (gap > 1)
  9. 	{
  10. 		gap = gap / 3 + 1;
  11. 		//对gap组数据分别进行插入排序
  12. 		for (int i = 0; i < n - gap; i++)
  13. 		{
  14. 			//一次插入排序
  15. 			int end = i;
  16. 			//保存下一个位置的数据
  17. 			int tmp = a[end + gap];
  18. 			//比较、挪动
  19. 			while (end >= 0)
  20. 			{
  21. 				if (a[end] > tmp)
  22. 				{
  23. 					a[end + gap] = a[end];
  24. 					end -= gap;
  25. 				}
  26. 				else
  27. 				{
  28. 					break;
  29. 				}
  30. 			}
  31. 			a[end + gap] = tmp;
  32. 		}
  33. 	}
  34. }

希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们后面可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定，在某些大佬的书籍中就提到过：
《数据结构 (C 语言版 ) 》 --- 严蔚敏

《数据结构 - 用面相对象方法与 C++ 描述》 --- 殷人昆

 所以呢，希尔排序的时间复杂度是O(N^{3/2})

4. 稳定性：不稳定

3.算法的效率比较

 在这里我们来比较我们已学过的冒泡排序、堆排序、直接插入排序和希尔排序的效率，再比较之前我们再来回顾一下冒泡排序和堆排序：

  1. //冒泡排序
  2. void BubbleSort(int* a, int n)
  3. {
  4. 	//设置冒泡排序的趟数
  5. 	for (int i = 0; i < n - 1; i++)
  6. 	{
  7. 		//一趟冒泡排序的次数
  8. 		bool exchange = false;
  9. 		for (int j = 1; j < n - j; j++)
  10. 		{
  11. 			if (a[j] > a[j + 1])  //如果前面的一个数字大于后面的数字就交换
  12. 			{
  13. 				int tmp = a[j];
  14. 				a[j] = a[j + 1];
  15. 				a[j + 1] = tmp;
  16. 				exchange = true;
  17. 			}
  18. 		}
  19. 		if (exchange == false)
  20. 		{
  21. 			break;
  22. 		}
  23. 	}
  24. }
  1. //堆排序
  2.  
  3. //交换函数
  4. void Swap(int* p1, int* p2)
  5. {
  6. 	int tmp = *p1;
  7. 	*p1 = *p2;
  8. 	*p2 = tmp;
  9. }
  10.  
  11. //向下调整
  12. void AdjustDown(int* a, int n, int parent)
  13. {
  14. 	//假设左孩子为左右孩子中最小的节点
  15. 	int child = parent * 2 + 1;
  16.  
  17. 	while (child < n)  //当交换到最后一个孩子节点就停止
  18. 	{
  19. 		if (child + 1 < n  //判断是否存在右孩子
  20. 			&& a[child + 1] < a[child]) //判断假设的左孩子是否为最小的孩子
  21. 		{
  22. 			child++;   //若不符合就转化为右孩子
  23. 		}
  24. 		//判断孩子和父亲的大小关系
  25. 		if (a[child] < a[parent])
  26. 		{
  27. 			Swap(&a[child], &a[parent]);
  28. 			//更新父亲和孩子节点
  29. 			parent = child;
  30. 			child = parent * 2 + 1;
  31. 		}
  32. 		else
  33. 		{
  34. 			break;
  35. 		}
  36. 	}
  37. }
  38.  
  39. //O(N * logN)
  40. void HeapSort(int* a, int n)
  41. {
  42. 	//建堆--向下调整算法建堆
  43. 	//时间复杂度为O(N)
  44. 	for (int i = ((n - 1) - 1) / 2; i >= 0; --i)
  45. 	{//       这里的n-1表示最后一个叶子节点
  46. 		//       最后一个叶子节点的父亲就是：
  47. 		//           （n-1）-1/2；
  48. 		AdjustDown(a, n, i);
  49. 	}
  50.  
  51. 	//O(N * logN)
  52. 	int end = n - 1;
  53. 	while (end > 0)
  54. 	{
  55. 		//交换堆顶和最后一个数据的位置
  56. 		Swap(&a[0], &a[end]);
  57. 		//向下调整，找次小的
  58. 		AdjustDown(a, end, 0);
  59. 		end--;
  60. 	}
  61. }

接下来我们可以使用一段代码来测试一下上面的这四种算法的效率区别。

采用的思路就是随机生成1w个数据，然后使用这些算法进行排序：

代码演示：

  1. // 测试排序的性能对比
  2. void TestOP()
  3. {
  4. 	srand(time(0));
  5. 	const int N = 100000;
  6. 	int* a1 = (int*)malloc(sizeof(int) * N);
  7. 	int* a2 = (int*)malloc(sizeof(int) * N);
  8. 	int* a3 = (int*)malloc(sizeof(int) * N);
  9. 	int* a4 = (int*)malloc(sizeof(int) * N);
  10.  
  11. 	for (int i = 0; i < N; ++i)
  12. 	{
  13. 		a1[i] = rand();
  14. 		a2[i] = a1[i];
  15. 		a3[i] = a1[i];
  16. 		a4[i] = a1[i];
  17. 	}
  18. 	int begin1 = clock();
  19. 	InsertSort(a1, N);
  20. 	int end1 = clock();
  21. 	int begin2 = clock();
  22. 	ShellSort(a2, N);
  23. 	int end2 = clock();
  24. 	int begin3 = clock();
  25. 	BubbleSort(a3, N);
  26. 	int end3 = clock();
  27. 	int begin4 = clock();
  28. 	HeapSort(a4, N);
  29. 	int end4 = clock();
  30. 	int begin5 = clock();
  31.  
  32. 	printf("InsertSort:%d\n", end1 - begin1);
  33. 	printf("ShellSort:%d\n", end2 - begin2);
  34. 	printf("BubbleSort:%d\n", end3 - begin3);
  35. 	printf("HeapSort:%d\n", end4 - begin4);
  36.  
  37. 	free(a1);
  38. 	free(a2);
  39. 	free(a3);
  40. 	free(a4);
  41. }

在这里测试的时候建议大家使用Release版本，测试效果会更好（这里测试的单位都是毫秒）：

朋友们、伙计们，美好的时光总是短暂的，我们本期的的分享就到此结束，最后看完别忘了留下你们弥足珍贵的三连喔，感谢大家的支持！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/酷酷是懒虫/article/detail/736816
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号