• 数据结构与算法—插入排序&选择排序

    目录

    一、排序的概念

    二、插入排序  

    1、直接插入排序 

    特性总结：

    2、希尔排序

    特性总结：

     三、选择排序

    1、直接选择排序 

    特性总结：

    2、堆排序—排升序(建大堆)

    向下调整函数

    堆排序函数

    特性总结：

    代码完整版： 

     头文件

     函数文件

     测试文件

    一、排序的概念

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

     

    二、插入排序  

    比如，在实际中我们玩扑克牌时，就用了插入排序的思想

    1、直接插入排序 

    直接插入排序是一种简单的排序算法，它的基本思想是将一个记录插入到已经排序好的有序表中，从而得到一个新的、记录数增加1的有序表。这个算法适用于少量数据的排序，是稳定的排序方法，即相等的元素的顺序不会改变。

    直接插入排序的算法过程如下：

    1. 从第一个元素开始，该元素可以认为已经被排序；
    2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
    3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
    4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
    5. 将新元素插入到该位置后；
    6. 重复步骤2~5。

    如果我们将这个过程比作扑克牌的排序，每次我们都是从牌堆中拿出一张牌，然后将它插入到左手中正确的位置，最终左手中的牌都是排序好的。

     我们来看一下代码的运行过程：

    1. void InsertSort(int* a, int n)
    2. {
    3. 	for (int i = 0; i < n - 1; i++) {
    4. 		int end = i;
    5. 		int tmp = a[i + 1];
    6. 		while (end >= 0) {
    7. 			if (a[end] > tmp) {
    8. 				a[end + 1] = a[end];
    9. 				end--;
    10. 			}
    11. 			else {
    12. 				break;
    13. 			}
    14. 		}
    15. 		a[end + 1] = tmp;
    16. 	}
    17. }
    • 函数参数：指针a接收数组，n接收数组元素个数。
    • 首先，外层循环从第一个元素开始遍历到倒数第二个元素，因为在内层循环中需要比较当前元素和前一个元素的大小，所以最后一个元素不需要再比较。
    • 在外层循环中，我们将当前元素的下一个元素作为待插入元素，将当前元素的下标保存在变量end中，这个变量表示当前元素在已排序部分中的位置。
    • 接下来while循环中，我们在已排序部分从后往前遍历，比较当前元素和已排序部分中的元素大小，如果当前元素小于已排序部分中的元素，则将已排序部分中的元素后移一位，直到找到当前元素的正确位置。
    • 最后，我们将待插入元素插入到正确的位置，即end+1的位置。
    • 内层循环结束后，当前元素已经被插入到了正确的位置，我们继续外层循环，处理下一个元素，直到所有元素都被插入到正确的位置。

    特性总结：

    1. 元素集合越接近有序，直接插入排序算法的时间效率越高
    2. 时间复杂度：O(N^2)
    3. 空间复杂度：O(1)，它是一种稳定的排序算法
    4. 稳定性：稳定

    2、希尔排序

     希尔排序（Shell Sort）是一种改进的插入排序算法，它的基本思想是将待排序的序列分成若干个子序列，对每个子序列进行插入排序，然后再将整个序列进行一次插入排序。通过这种方式，可以使得序列中较小的元素尽可能地快速地移动到前面，从而减少了插入排序的比较次数和移动次数，提高了排序的效率。

    希尔排序的算法过程如下：

    1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
    2. 按增量序列个数k，对序列进行k趟排序；
    3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对每个子序列进行插入排序；
    4. 将各个子序列中的排序结果合并成一个序列。

    代码如下：

    1. void ShellSort(int* a, int n)
    2. {
    3. 	//1、gap >  1 预排序
    4. 	//2、gap == 1 直接插入排序
    5. 	int gap = n;
    6. 	while (gap > 1) {
    7. 		gap = gap / 3 + 1;// +1可以保证最后一次一定是1
    8. 		for (int i = 0; i < n - gap; i++) {
    9. 			int end = i;
    10. 			int tmp = a[end + gap];
    11. 			while (end >= 0) {
    12. 				if (a[end] > tmp) {
    13. 					a[end + gap] = a[end];
    14. 					end -= gap;
    15. 				}
    16. 				else {
    17. 					break;
    18. 				}
    19. 			}
    20. 			a[end + gap] = tmp;
    21. 		}
    22. 	}
    23. }
    • 首先，我们选择一个增量gap=n，然后将序列分成若干个子序列，对每个子序列进行插入排序。
    • 在这个实现中，我们使用了一个while循环来计算增量gap，每次将gap除以3并加1，保证gap最小为1，此时进行直接插入排序。
    • 在外层while循环中，我们将序列分成若干个子序列，每个子序列的长度为gap。然后，我们对每个子序列进行插入排序，将子序列中的元素插入到已排序部分的正确位置。

    • 在内层循环中，我们使用了一个变量end来表示当前元素的下标，每次将end减去gap，直到找到当前元素的正确位置。然后，我们将待插入元素插入到正确的位置，即end+gap的位置。

    • 内层循环结束后，当前子序列已经排好序了，我们继续外层while循环，处理下一个子序列，直到所有子序列都被排好序了。

     以数组 a = [9, 8, 7, 6, 5, 4, 3, 3, 2, 1, 0]，长度 n = 11为例，演示排序过程

    图中颜色相同的值为当前<间距gap>下的子序列，从前往后依次比较每个子序列（也就是相距 gap 个位置的值的大小）。

    特性总结：

    1. 希尔排序是对直接插入排序的优化。
    2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
    3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定，但我们只需记住结论：O（N^ 1.3），复杂的推导和计算过程不需要了解。

     三、选择排序

    1、直接选择排序 

    第一种：通过不断选择未排序序列中的最小元素，并将其放到已排序序列的末尾，逐步构建有序序列。外层循环控制已排序序列的末尾位置，内层循环用于找到未排序序列中的最小元素。通过不断交换位置，将最小元素放到已排序序列的末尾，直到整个数组排序完成。

    1. void SelectSort(int arr[], int n) {
    2.     int i, j, minIndex, temp;
    3.     for (i = 0; i < n-1; i++) {
    4.         minIndex = i;
    5.         for (j = i+1; j < n; j++) {
    6.             if (arr[j] < arr[minIndex]) {
    7.                 minIndex = j;
    8.             }
    9.         }
    10.         temp = arr[i];
    11.         arr[i] = arr[minIndex];
    12.         arr[minIndex] = temp;
    13.     }
    14. }

    第二种：通过每一轮的比较，找到最大值和最小值，将最大值的节点跟右边交换，最小值节点跟左边交换，达到排升序的效果。

    我们先看代码，然后通过一个例子就能明白了。 

    1. void Swap(int* p1, int* p2)
    2. {
    3. 	int tmp = *p1;
    4. 	*p1 = *p2;
    5. 	*p2 = tmp;
    6. }
    7.  
    8. void SelectSort(int* a, int n)
    9. {
    10. 	int begin = 0, end = n - 1;
    11. 	while (begin < end)
    12. 	{
    13. 		int maxi = begin, mini = begin;
    14. 		for (int i = begin; i <= end; i++)
    15. 		{
    16. 			if (a[i] > a[maxi])
    17. 			{
    18. 				maxi = i;
    19. 			}
    20.  
    21. 			if (a[i] < a[mini])
    22. 			{
    23. 				mini = i;
    24. 			}
    25. 		}
    26.  
    27. 		Swap(&a[begin], &a[mini]);
    28. 		// 如果maxi和begin重叠，修正一下即可
    29. 		if (begin == maxi)
    30. 		{
    31. 			maxi = mini;
    32. 		}
    33.  
    34. 		Swap(&a[end], &a[maxi]);
    35.  
    36. 		++begin;
    37. 		--end;
    38. 	}
    39. }
    • 代码中的变量begin和end分别表示当前未排序的元素范围的起始和结束位置。
    • 在while循环中，每次从begin到end的范围内找到最大和最小的元素，分别用maxi和mini记录它们的下标。
    • 然后将mini所指向的元素与begin所指向的元素交换位置，将maxi所指向的元素与end所指向的元素交换位置。
    • 如果maxi和begin重叠，说明mini所指向的元素是当前未排序元素中最大的，需要将maxi更新为mini。
    • 最后，begin指针向后移动一位，end指针向前移动一位，继续进行下一轮排序。 

    我们来用一个简单的例子演示一下这个选择排序算法的过程。

    假设我们有一个数组`a`，它的元素为：[5, 3, 8, 6, 4, 2]，我们要对它进行排序。

    首先，begin指向第一个元素，end指向最后一个元素：

    1. begin = 0
    2. end = 5

    接下来，我们进入主循环，因为`begin`小于`end`，所以我们需要继续排序。在第一轮排序中，我们需要找到未排序部分的最大值和最小值。

    首先，我们将`maxi`和`mini`都初始化为`begin`，也就是第一个元素的索引。然后，我们遍历未排序部分的元素，找到最大值和最小值的索引。在这个例子中，最大值的索引是2，最小值的索引是5。

    1. maxi = 2
    2. mini = 5

    接下来，我们将未排序部分的最小值交换到开始位置，将未排序部分的最大值交换到结束位置。这时，数组的状态变为：[2, 3, 5, 6, 4, 8]

    由于我们已经将当前范围的最大值和最小值放到了正确的位置，所以我们将`begin`向后移动一位，将`end`向前移动一位，继续进行下一轮排序。此时，`begin`指向第二个元素，`end`指向倒数第二个元素：

    1. begin = 1
    2. end = 4

    在第二轮排序中，我们需要找到未排序部分的最大值和最小值。这时，最大值的索引是3，最小值的索引是1。

    1. maxi = 3
    2. mini = 1

    接下来，将未排序部分的最小值交换到开始位置，将未排序部分的最大值交换到结束位置。这时，数组的状态变为：[2, 3, 5, 4, 6, 8] 

    进行下一轮排序。此时，`begin`指向第三个元素，`end`指向第四个元素： 

    1. begin = 2
    2. end = 3

     在第三轮排序中，我们需要找到未排序部分的最大值和最小值。这时，最大值的索引是2，最小值的索引是1。 

    1. maxi = 2
    2. mini = 3

    最后，我们将未排序部分的最小值交换到开始位置，将未排序部分的最大值交换到结束位置。这时，数组的状态变为：[2, 3, 4, 5, 6, 8]，所有元素都排序完成，排序结束。

    特性总结：

    1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
    2. 时间复杂度：每一轮比较都需要遍历数组，查找最大最小值，第一轮遍历N个数据，第二轮是N-2个数据，第三轮N-4 …，遍历次数为：N+N-2+N-4+…+1，一个等差数列求和，所以总的时间复杂度为O(N^2)
    3. 空间复杂度：O(1)
    4. 稳定性：不稳定

    2、堆排序—排升序(建大堆)

    向下调整函数

    1. void Swap(int* p1, int* p2)
    2. {
    3. 	int tmp = *p1;
    4. 	*p1 = *p2;
    5. 	*p2 = tmp;
    6. }
    7.  
    8. void AdjustDown(int* a, int n, int parent)
    9. {
    10. 	int child = parent * 2 + 1;
    11.  
    12. 	while (child < n){
    13. 		if (child + 1 < n && a[child + 1] > a[child])
    14. 			++child;
    15.  
    16. 		if (a[child] > a[parent]){
    17. 			Swap(&a[child], &a[parent]);
    18. 			parent = child;
    19. 			child = parent * 2 + 1;
    20. 		}
    21.  
    22. 		else
    23. 			break;
    24. 	}
    25. }
    • 通过传入参数获取到当前的左子节点的位置。
    • 当child位置小于数组元素个数时进行判断。
    • 进入循环，首先判断检查右子节点是否存在并且比左子节点的值大，如果是，将 child 更新为右子节点的索引，以确保选择更小的子节点进行比较。
    • 比较选定的子节点的值与父节点的值，如果子节点的值大于父节点的值，就交换它们。
    • 更新parent为新的子节点位置，更新child为新的左子节点位置，然后继续比较和交换，直到不再需要交换为止。
    • 如果当前子节点不大于当前父节点则停止循环。

    堆排序函数

    1. // 排升序
    2. void HeapSort(int* a, int n)
    3. {
    4. 	// 建大堆
    5. 	for (int i = (n-1-1)/2; i >= 0; --i)
    6. 	{
    7. 		AdjustDown(a, n, i);
    8. 	}
    9.  
    10. 	int end = n - 1;
    11. 	while (end > 0)
    12. 	{
    13. 		Swap(&a[0], &a[end]);
    14. 		AdjustDown(a, end, 0);
    15. 		--end;
    16. 	}
    17. }
    1.  在HeapSort函数中，第一个循环调用了AdjustDown函数，将待排序数组构建成了一个大堆。但是，这个大堆并不是完全有序的，只是满足了大堆的性质，即每个节点的值都大于或等于其左右子节点的值。因此，需要进行第二个while循环，将大堆中的元素依次取出，交换堆顶元素和数组末尾元素，并重新调整大堆，直到整个数组有序。
    2. 第二个while循环中，将堆顶元素与数组末尾元素交换，然后将剩余元素重新调整为大堆。这样，每次交换后，数组末尾的元素就是当前大堆中的大值，而剩余元素仍然满足大堆的性质。重复以上步骤，直到整个数组有序。

    特性总结：

    1. 堆排序使用堆来选数，效率就高了很多。
    2. 时间复杂度：O(N*logN)
    3. 空间复杂度：O(1)
    4. 稳定性：不稳定

    代码完整版： 

     头文件

    1. #include
    2. #include
    3. #include
    4.  
    5. void PrintArray(int* a, int n);
    6. void InsertSort(int* a, int n);
    7. void ShellSort(int* a, int n);
    8. void SelectSort(int* a, int n);
    9. void HeapSort(int* a, int n);

     函数文件

    1. #include "sort.h"
    2.  
    3. void PrintArray(int* a, int n)
    4. {
    5. 	for (int i = 0; i < n; i++) {
    6. 		printf("%d ", a[i]);
    7. 	}
    8. 	printf("\n");
    9. }
    10.  
    11. void InsertSort(int* a, int n)
    12. {
    13. 	for (int i = 0; i < n - 1; i++) {
    14. 		int end = i;
    15. 		int tmp = a[i + 1];
    16. 		while (end >= 0) {
    17. 			if (a[end] > tmp) {
    18. 				a[end + 1] = a[end];
    19. 				end--;
    20. 			}
    21. 			else {
    22. 				break;
    23. 			}
    24. 		}
    25. 		a[end + 1] = tmp;
    26. 	}
    27. }
    28.  
    29. void ShellSort(int* a, int n)
    30. {
    31. 	//1、gap >  1 预排序
    32. 	//2、gap == 1 直接插入排序
    33. 	int gap = n;
    34. 	while (gap > 1) {
    35. 		gap = gap / 3 + 1;// +1可以保证最后一次一定是1
    36. 		for (int i = 0; i < n - gap; i++) {
    37. 			int end = i;
    38. 			int tmp = a[end + gap];
    39. 			while (end >= 0) {
    40. 				if (a[end] > tmp) {
    41. 					a[end + gap] = a[end];
    42. 					end -= gap;
    43. 				}
    44. 				else {
    45. 					break;
    46. 				}
    47. 			}
    48. 			a[end + gap] = tmp;
    49. 		}
    50. 	}
    51. }
    52.  
    53. void Swap(int* p1, int* p2)
    54. {
    55. 	int tmp = *p1;
    56. 	*p1 = *p2;
    57. 	*p2 = tmp;
    58. }
    59.  
    60. void SelectSort(int* a, int n)
    61. {
    62. 	int begin = 0, end = n - 1;
    63. 	while (begin < end)
    64. 	{
    65. 		int maxi = begin, mini = begin;
    66. 		for (int i = begin; i <= end; i++)
    67. 		{
    68. 			if (a[i] > a[maxi])
    69. 			{
    70. 				maxi = i;
    71. 			}
    72.  
    73. 			if (a[i] < a[mini])
    74. 			{
    75. 				mini = i;
    76. 			}
    77. 		}
    78.  
    79. 		Swap(&a[begin], &a[mini]);
    80. 		// 如果maxi和begin重叠，修正一下即可
    81. 		if (begin == maxi)
    82. 		{
    83. 			maxi = mini;
    84. 		}
    85.  
    86. 		Swap(&a[end], &a[maxi]);
    87.  
    88. 		++begin;
    89. 		--end;
    90. 	}
    91. }
    92.  
    93. void AdjustDown(int* a, int n, int parent)
    94. {
    95. 	int child = parent * 2 + 1;
    96. 	while (child < n) {
    97. 		if (child + 1 < n && a[child + 1] > a[child]) {
    98. 			child++;
    99. 		}
    100. 		if (a[child] > a[parent]) {
    101. 			Swap(&a[child], &a[parent]);
    102. 			parent = child;
    103. 			child = parent * 2 + 1;
    104. 		}
    105. 		else {
    106. 			break;
    107. 		}
    108. 	}
    109. }
    110.  
    111. void HeapSort(int* a, int n)
    112. {
    113. 	for (int i = (n - 1 - 1) / 2; i >= 0; --i) {
    114. 		AdjustDown(a, n, i);
    115. 	}
    116. 	int end = n - 1;
    117. 	while (end > 0) {
    118. 		Swap(&a[0], &a[end]);
    119. 		AdjustDown(a, end, 0);
    120. 		end--;
    121. 	}
    122. }

     测试文件

    1. #include"Sort.h"
    2. #include
    3.  
    4. void TestInsertSort()
    5. {
    6. 	//int a[] = { 4,7,1,9,3,4,5,8,3,2 };
    7. 	int a[] = { 4,7,1,9,3,6,5,8,3,2,0 };
    8. 	PrintArray(a, sizeof(a) / sizeof(int));
    9. 	InsertSort(a, sizeof(a) / sizeof(int));
    10. 	PrintArray(a, sizeof(a) / sizeof(int));
    11. }
    12.  
    13. void TestSelectSort()
    14. {
    15. 	//int a[] = { 4,7,1,9,3,6,5,8,3,2,0 };
    16. 	int a[] = { 9,7,1,3,3,0,5,8,3,2,3 };
    17. 	PrintArray(a, sizeof(a) / sizeof(int));
    18. 	SelectSort(a, sizeof(a) / sizeof(int));
    19. 	PrintArray(a, sizeof(a) / sizeof(int));
    20. }
    21.  
    22. void TestHeapSort()
    23. {
    24. 	int a[] = { 4,7,1,9,3,6,5,8,3,2,0 };
    25. 	PrintArray(a, sizeof(a) / sizeof(int));
    26. 	HeapSort(a, sizeof(a) / sizeof(int));
    27. 	PrintArray(a, sizeof(a) / sizeof(int));
    28. }
    29.  
    30. void TestOP()
    31. {
    32. 	srand(time(0));
    33. 	const int N = 1000000;//运行时间较长可自行更改大小
    34. 	int* a1 = (int*)malloc(sizeof(int) * N);
    35. 	int* a2 = (int*)malloc(sizeof(int) * N);
    36. 	int* a3 = (int*)malloc(sizeof(int) * N);
    37. 	int* a4 = (int*)malloc(sizeof(int) * N);
    38. 	int* a5 = (int*)malloc(sizeof(int) * N);
    39. 	int* a6 = (int*)malloc(sizeof(int) * N);
    40. 	int* a7 = (int*)malloc(sizeof(int) * N);
    41.  
    42.  
    43. 	for (int i = 0; i < N; ++i)
    44. 	{
    45. 		a1[i] = rand();
    46. 		a2[i] = a1[i];
    47. 		a3[i] = a1[i];
    48. 		a4[i] = a1[i];
    49. 		a5[i] = a1[i];
    50. 		a6[i] = a1[i];
    51. 		a7[i] = a1[i];
    52. 	}
    53.  
    54. 	int begin1 = clock();
    55. 	InsertSort(a1, N);
    56. 	int end1 = clock();
    57.  
    58. 	int begin2 = clock();
    59. 	ShellSort(a2, N);
    60. 	int end2 = clock();
    61.  
    62. 	int begin3 = clock();
    63. 	SelectSort(a3, N);
    64. 	int end3 = clock();
    65.  
    66. 	int begin4 = clock();
    67. 	HeapSort(a4, N);
    68. 	int end4 = clock();
    69.  
    70. 	printf("InsertSort:%d\n", end1 - begin1);
    71. 	printf("ShellSort:%d\n",  end2 - begin2);
    72. 	printf("SelcetSort:%d\n", end3 - begin3);
    73. 	printf("HeapSort:%d\n",   end4 - begin4);
    74.  
    75. 	free(a1);
    76. 	free(a2);
    77. 	free(a3);
    78. 	free(a4);
    79. 	free(a5);
    80. 	free(a6);
    81. 	free(a7);
    82. }
    83.  
    84. int main()
    85. {
    86. 	//TestInsertSort();
    87. 	//TestShellSort();
    88. 	//TestSelectSort();
    89. 	//TestHeapSort();
    90.  
    91. 	TestOP();
    92.  
    93. 	return 0;
    94. }
    95.

  • 相关阅读:
    优维产品最佳实践：主机合规性检查
    记录腾讯云重置密码之后ssh就连不上的踩坑
    自学Python 47 日期和时间函数（二）
    管理器注册类方法和调用类函数方法
    拒绝加班:巧用前端电子表格中构建公式树
    渣土车识别监测 渣土车未盖篷布识别抓拍算法
    嵌入式Linux驱动开发6---sysfs文件系统与 kobject结构体
    学习阿里如何进行数据指标体系的治理
    动态规划算法（1）
    JSX（ JavaScript XML）简介及语法规则
  • 原文地址：https://blog.csdn.net/m0_73800602/article/details/134274720