• 一起学数据结构（10）——排序

    从本文开始，通过若干篇文章展开对于数据结构中——排序的介绍。

    1. 排序的概念：

             将一堆杂乱无章的数据，通过一定的规律顺序排列起来。即将一个无序序列排列成一个有序序（由小到大或者由大到小）的运算。

            在数据的排序中需要注意，如果需要排序的对象同时有多个数据域（例如对学生进行排序，往往有学号，班级等多个数据域），排序往往是针对于其中一个数据域进行的。

    2. 排序的种类：

           对于排序，本文及下面的文章中将着重介绍下列给出的排序：插入排序、希尔排序、选择排序、冒泡排序、快速排序、归并排序、计数排序。

    3. 插入排序：

    3.1 思路分析：

            对于插入排序，其基本思想可以概括为：每一步都将待排序的对象，按照该对象与已有数据的大小关系，插入到前面已经排好序的一组数据的合适的位置中。因此，插入排序可以看作一个一边进行插入，一边保持已有序列有序的排序。

            为了便于理解插入排序的基本思想，下面给出一个例子：

            对于上面给出的例子，按照上面插入排序的基本思想来进行排序，则需要首先比较待插入元素5与数组中已有元素进行比较。直到插入到一个合适的位置。所以对上述的案例进行排序后，最终结果为;

           对于上面给出的插入排序的过程需要理解，并不是真的对数组不断插入新的元素进行排序。而是将数组中的一部分看作插入的部分，例如对于下面的数组：

           将已经有序的序列，即数组中的1,2,4,7称为有序序列。将后面的数组成的序列称之为无序序列。如果这个序列进行插入排序，只是将元素6看作待插入元素。通过不断比对待插入元素与数组中元素的大小关系，来调整元素6至合适的位置。

          为了方便后续编写插入排序的代码，将有序序列的最后一位的下标记为end，将待插入元素的下标记为end+1。所以，end一开始所对应的下标就是数组第一个元素的下标，即0，待插入元素的下标就是end+1=1，即数组中的第二个元素。对比调整后，数组中前两个元素会变为有序序列。接着按照上面的步骤循环，即令end = 1，即有序序列的第二个元素，或者说数组中的第一个元素。待插入元素的下标等于end+1=2，即数组中的第二个元素。。。。。。。

    3.2 代码演示：

          通过上面给出的思路，可以总结出下面代码：

    1. void InsertSort(int* a, int n)
    2. {
    3. 	int end = 0;
    4. 	for (end = 0; end < n - 1; end++)
    5. 		{
    6. 			int tmp = a[end + 1];
    7. 			while (end >= 0)
    8. 			{
    9. 				if (a[end] > tmp)
    10. 				{
    11. 					a[end + 1] = a[end];
    12. 				}
    13. 				else
    14. 				{
    15. 					break;
    16. 				}
    17. 				end--;
    18. 			}
    19. 			a[end + 1] = tmp;
    20. 		}
    21.  
    22. }

    对于插入排序，因为没有开辟额外的空间，所以插入排序的空间复杂度为O(1),当数组完全逆序时，插入排序需要执行的次数可以看作一个等差数列，所以插入排序的时间复杂度为O(n^2) 

    3.3 插入排序测试：

    测试函数如下：

    1. void TestInsertsort()
    2. {
    3. 	int a[] = { 2,1,3,4,6,9,5,8 };
    4. 	int size = sizeof(a) / sizeof(int);
    5. 	InsertSort(a, size);
    6. 	ArrayPrint(a, size);
    7. }

    其中函数ArrayPrint是用于打印数组的函数，原理过于简单，不予解释，运行效果如下：


     

    4. 希尔排序： 

    4.1 思路分析及代码演示：

            对于上面给出的插入排序中提到，如果插入排序需要排序的数组是逆序的，则插入排序的时间复杂度为O(n)，如果需要排序的数组为顺序的，则时间复杂度为O(n)，为了优化插入排序在排序逆序数组时较大的时间复杂度，可以尝试在对数组进行插入排序之间，先对数组进行依次预排序，让数组中某些元素是顺序的。对于先进行预处理，再进行一次插入排序的排序，就是文章本部分要介绍的希尔排序。例如下面的数组：

    对于预排序，其步骤如下：首先确定一个间隔数，这里将这个间隔数命名为gab，通过利用 gab将数组分为若干个区间。并且对相邻区间的首元素进行一次类插入排序的操作。具体步骤将通过下面的图形进行演示：

    1. 假设gab = 3，则利用gab分组后的数组可以表示为：

    继续利用上面方法对数组中未分组的元素进行分组，可以表示为下面的图片，图中不同颜色的图形用于区分不同的组：

    2. 接着，对于一组中的元素进行一次类插入排序的操作，即比较同一组的不同区间的首元素的大小关系，将小的元素放到前面。例如，对于红线组中的元素进行上述操作：

    对于本部分的操作，可以利用插入排序的思想来实现，依旧定义end表示本组第一个元素的下标，例如红线组的9，end+gab则表示本组下一个区间的首元素的坐标，再创建一个变量tmp用于存储end+gab所对应的元素。例如红线组的5。由于end所对应的元素＞end+gab所对应的元素。所以让end代表的元素覆盖到end+gab的位置。再让tmp覆盖到end位置。该过程可用代码表示为：

    1. void ShellSort(int* a, int n)
    2. {
    3. 	int end = 0;
    4. 	int gab = 3;
    5. 	int tmp = a[end + gab];
    6. 	
    7. 	if (a[end] > tmp)
    8. 	{
    9. 		a[end + gab] = a[end];
    10. 	}
    11.  
    12. 	a[end] = tmp;
    13. }

     但是，上面的过程并不完整，并且只能交换一次，加入遇到下面的情景：

    假设 end所对应的元素为9，end+gab所对应的元素为4，按照上面的代码交换一次后：

            可以看到，5,4这两个元素的大小关系还是不满足。因此，并不能向上面仅仅对 end，end+gab的元素的大小关系进行判断，还需要对交换后前面的元素的关系重新进行一次判断，如果不满足则再次交换。方法为：再进行一次交换后，令end-gab，此时end-gab对应的元素为5，(end-gab)+gab对应的元素为4，对二者再次进行一次交换。

           为了满足多次交换的目的需要利用到循环。所以对于循环的结束条件有两条：1是end < 0，2是元素的大小关系不符合。

          即使在加上上面的补充后，代码也只能用于单个组中一组end，end+gab元素的交换，为了完成整租的交换，需要让end所对应的下标不断向后gab个位置。所以可以将上述代码优化为：

    1. //希尔排序
    2. void ShellSort(int* a, int n)
    3. {
    4. 	int gab = 3;
    5. 	for (int end = 0; end < n - gab; end += gab)
    6. 	{
    7. 		int tmp = a[end + gab];
    8. 		while (end >= 0)
    9. 		{
    10. 			if (a[end] > tmp)
    11. 			{
    12. 				a[end + gab] = a[end];
    13. 				end -= gab;
    14. 			}
    15. 			else
    16. 			{
    17. 				break;
    18. 			}
    19. 		}
    20. 		a[end + gab] = tmp;
    21. 	}
    22. }

    完善后的代码，可以一次性完成一组的预排序。但是在预排序的过程中需要对多组数据进行排序。通过对下面图形的观察可以得知，当end初始值就为2时，此时进行预排序的就是紫色线条对应的组，也就是需要预排序的最后一组。所以，可以在将上面的代码进行一次优化，让其能够处理多组预排序

    并且，对于gab的值也是变化的，gab的值越大，数组中大的元素向后移动的距离越长，gab越小，移动的距离也越小，当gab=1，数组为有序。

    代码如下：
     

    1. //希尔排序
    2. void ShellSort(int* a, int n)
    3. {
    4. 	int gab = n;
    5. 	while (gab > 1)
    6. 	{
    7. 		gab = gab / 2;
    8. 		for (int i = 0; i < gab; i++)
    9. 		{
    10. 			for (int end = i; end < n - gab; end += gab)
    11. 			{
    12. 				int tmp = a[end + gab];
    13. 				while (end >= 0)
    14. 				{
    15. 					if (a[end] > tmp)
    16. 					{
    17. 						a[end + gab] = a[end];
    18. 						end -= gab;
    19. 					}
    20. 					else
    21. 					{
    22. 						break;
    23. 					}
    24. 				}
    25. 				a[end + gab] = tmp;
    26. 			}
    27. 		}
    28. 	}
    29. }

    对于预排序部分的代码，还有另一种更简洁的部分，这里先给出相应代码，再进行逻辑分析：

    1. //希尔排序
    2. void ShellSort1(int* a, int n)
    3. {
    4. 	    int gab = n;
    5. 		while (gab > 1)
    6. 		{
    7. 			gab = gab / 2;
    8. 			for (int i = 0; i < n - gab; i++)
    9. 			{
    10. 				int end = i;
    11. 				int tmp = a[end + gab];
    12. 				while (end >= 0)
    13. 				{
    14. 					if (a[end] > tmp)
    15. 					{
    16. 						a[end + gab] = a[end];
    17. 						end -= gab;
    18. 					}
    19. 					else
    20. 					{
    21. 						break;
    22. 					}
    23. 				}
    24. 				a[end + gab] = tmp;
    25. 			}
    26. 		}
    27. }

    观察上面给出的代码，可以发现，相对于上面给出的预排序，这种预排序省略了一个for循环。逻辑也不同。对于现在给出的预排序，并不是按照严格分组，先进行完一组，再进行一组。而是在确定了gab之后，直接按照数组下标的顺序进行预排序，例如：

    对于前面一种的预排序，是先对5,4进行预排序，再对5,9进行预排序，再对9,5进行预排序，此时，红线所对应的组完成了预排序，于是再对绿线所对应的组的元素开始预排序，顺序为：1,7,7,6。

    但是对于现在给出的预排序，预排序的顺序为：5,4, 1,7, 2,4, 4,9 ,。。。。。。

    由于希尔排序的时间复杂度的计算极其复杂，这里直接给出结论，希尔排序的时间复杂度大致在O(n^{1.3})左右。空间复杂度为O(1)。

    4.2 希尔排序测试：

    测试函数如下：

    1. void TestShellSort()
    2. {
    3. 	int b[] = { 9,1,2,5,7,4,8,6,3,5 };
    4. 	int size = sizeof(b) / sizeof(int);
    5. 	ShellSort(b, size);
    6. 	printf("希尔排序：");
    7. 	ArrayPrint(b, size);
    8. }

    结果如下：

    5. 冒泡排序：

    5.1 代码演示：

            对于冒泡排序的相关原理，可以在文章C语言——冒泡排序和qsort排序-CSDN博客浏览，文章在本部分只给出冒泡排序的相关代码以及测试结果，对实现原理不做论述。

    1.  void BubbleSort(int* a, int n)
    2. {
    3. 	 for (int j = 0; j < n; j++)
    4. 	 {
    5. 		 int exchange = 0;
    6. 		 for (int i = 1; i < n; i++)
    7. 		 {
    8. 			 if (a[i - 1] > a[i])
    9. 			 {
    10. 				 Swap(&a[i - 1], &a[i]);
    11. 				 exchange = 1;
    12. 			 }
    13. 		 }
    14. 		 if (exchange == 0)
    15. 		 {
    16. 			 break;
    17. 		 }
    18. 	 }
    19. }

    5.2 冒泡排序测试：

    测试函数如下：

    1. //冒泡排序
    2.  void BubbleSort(int* a, int n)
    3. {
    4. 	 for (int j = 0; j < n; j++)
    5. 	 {
    6. 		 int exchange = 0;
    7. 		 for (int i = 1; i < n; i++)
    8. 		 {
    9. 			 if (a[i - 1] > a[i])
    10. 			 {
    11. 				 Swap(&a[i - 1], &a[i]);
    12. 				 exchange = 1;
    13. 			 }
    14. 		 }
    15. 		 if (exchange == 0)
    16. 		 {
    17. 			 break;
    18. 		 }
    19. 	 }
    20. }
    1. void Swap(int* x, int* y)
    2. {
    3. 	int tmp = *x;
    4. 	*x = *y;
    5. 	*y = tmp;
    6. }

    结果如下：

    6. 堆排序 ：

    对于堆排序的相关原理及代码实现，在之前的文章如何利用堆来模拟堆排序-CSDN博客已经做了详细的解释，这里不再进行多余论述。

    7. 选择排序：

    7.1 思路分析以及代码演示：

            对于选择排序的原理，总结下来只有一句话，即每次排序时，选出数组中最小的值以及最大的值，将最小的值换到数组的最左边，最大的值换到数组的最右边。

           为了达成上述目的，可以创建min,max两个变量，通过遍历数组将二者选择出来，再通过交换函数，让两个值在数组中的位置分别达到最左边，最右边。

    代码如下：

    1.  void SelectSort(int* a, int n)
    2.  {
    3. 	 int begin = 0, end = n - 1;
    4. 	 while (begin < end)
    5. 	 {
    6. 		 int mini = begin, maxi = begin;
    7. 		 for (int i = begin + 1; i <= end; i++)
    8. 		 {
    9. 			 if (a[i] > a[maxi])
    10. 			 {
    11. 				 maxi = i;
    12. 			 }
    13. 			 if (a[i] < a[mini])
    14. 			 {
    15. 				 mini = i;
    16. 			 }
    17. 		 }
    18. 		 Swap(&a[begin], &a[mini]);
    19. 		 if (maxi == begin)
    20. 		 {
    21. 			 maxi = mini;
    22. 		 }
    23. 		 Swap(&a[end], &a[maxi]);
    24. 		 begin++;
    25. 		 end--;
    26. 	 }
    27.  }

    7.2 选择排序测试：

    测试函数如下：

    1. TestSelectSort()
    2. {
    3. 	int d[] = { 7,8,1,4,5,9,2,3,6};
    4. 	int size = sizeof(d) / sizeof(int);
    5. 	SelectSort(d, size);
    6. 	printf("选择排序：");
    7. 	ArrayPrint(d, size);
    8. }

     结果如下：

    对于选择排序，显而易见，时间复杂度为O(n^2)，空间复杂度为O(1)。

  • 相关阅读:
    正点原子lwIP学习笔记——Socket接口UDP实验
    正则表达式基础
    人工智能的未来———因果推理：Causal Inference: What If chapter2 A Randomized experiments 文章解读
    PHP 变量
    STM32智能物流机器人系统教程
    设计思维｜如何构建价值导向的设计思维？
    【学习笔记】CF1784F Minimums or Medians
    工具篇 | WSL使用入门教程以及基于WSL和natApp内网穿透实践 - 对比VMWare
    李彦宏回顾大模型重构百度这一年
    一文带你了解 ESLint
  • 原文地址：https://blog.csdn.net/2301_76836325/article/details/133965567