【数据结构】排序-C语言版（一）-阿里云开发者社区

各类排序算法基本思想是什么？如何实现？时间复杂度分别是多少？稳定吗？

常见的排序算法有如下7种：

一、插入排序

插入排序基本思想：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

1.直接插入排序

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

055-InsertSort.h

1. #pragma once
2. #include<stdio.h>
3. #include <stdlib.h>
4. 
5. 
6. //打印
7. void Print(int* a, int n);
8. 
9. //直接插入排序
10. void InsertSort(int* a, int n);

055-InsertSort.c

1. #include "055-InsertSort.h"
2. 
3. //打印
4. void Print(int* a, int n)
5. {
6.  for (int i = 0; i < n; i++)
7.  {
8.    printf("%d ", a[i]);
9.  }
10. 
11.   printf("\n");
12. }
13. 
14. //直接插入排序
15. void InsertSort(int* a, int n)
16. {
17.   //多趟排序
18.   for (int i = 0; i < n - 1; i++)
19.   {
20.     //把temp插入到数组的[0,end]有序区间中
21.     int end = i;
22.     int temp = a[end + 1];
23.     while (end >= 0)
24.     {
25.       if (temp < a[end])
26.       {
27.         a[end + 1] = a[end];
28.         end--;
29.       }
30.       else
31.       {
32.         break;
33.       }
34.     }
35. 
36.     a[end + 1] = temp;
37. 
38.   }
39. 
40. }

055-TestInsertSort.c

1. #include "055-InsertSort.h"
2. 
3. void TestInsertSort()
4. {
5.  int arr[] = { 9,1,2,5,7,4,8,6,3,5 };
6.  InsertSort(arr, sizeof(arr) / sizeof(arr[0]));
7.  Print(arr, sizeof(arr)/sizeof(arr[0]));
8. }
9. 
10. int main()
11. {
12.   TestInsertSort();
13. 
14.   return 0;
15. }

直接插入排序的特性总结：

(1) 元素集合越接近有序，直接插入排序算法的时间效率越高

(2) 时间复杂度：O(N^2)

(3) 空间复杂度：O(1)，它是一种稳定的排序算法

(4) 稳定性：稳定

2、希尔排序

希尔排序法又称缩小增量法。基本思想：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

055-ShellSort.h

1. #pragma once
2. #include<stdio.h>
3. #include <stdlib.h>
4. 
5. //打印
6. void Print(int* a, int n);
7. 
8. //希尔排序
9. void ShellSort(int* a, int n);

055-ShellSort.c

1. #include "055-ShellSort.h"
2. 
3. //打印
4. void Print(int* a, int n)
5. {
6.  for (int i = 0; i < n; i++)
7.  {
8.    printf("%d ", a[i]);
9.  }
10. 
11.   printf("\n");
12. }
13. 
14. //希尔排序 - 先分组，对分组的数据，插入排序
15. //1.预排序-接近有序
16. //2.直接插入
17. void ShellSort(int* a, int n)
18. {
19.   //gap>1的时候，预排序
20.   //gap==1的时候，直接插入排序
21.   int gap = n;
22.   while (gap > 1)
23.   {
24. 
25.     gap = gap / 3 + 1;
26.     for (int i = 0; i < n - gap; i++)
27.     {
28.       //把temp插入到数组的[0,end]有序区间中
29.       int end = i;
30.       int temp = a[end + gap];
31.       while (end >= 0)
32.       {
33.         if (temp < a[end])
34.         {
35.           a[end + gap] = a[end];
36.           end -= gap;
37.         }
38.         else
39.         {
40.           break;
41.         }
42. 
43.       }
44.       a[end + gap] = temp;
45. 
46.     }
47.     //printf("gap:%d-> ", gap);
48.     //Print(a, n);
49.   }
50. }

055-TestShellSort.c

1. #include " 055-ShellSort.h"
2. 
3. void TestShellSort()
4. {
5.  int arr[] = { 10,7,8,9,6,5,4,3,2,1,0,-1,-2,-3,-4,-5,-6,-7,-8,-9 };
6.  ShellSort(arr, sizeof(arr) / sizeof(arr[0]));
7.  Print(arr, sizeof(arr) / sizeof(arr[0]));
8. }
9. 
10. int main()
11. {
12.   TestShellSort();
13. 
14.   return 0;
15. }

希尔排序特性总结：

（1）希尔排序是对直接插入排序的优化。

（2）当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。整体而言，达到了优化的效果。

（3）希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定，实验和基础上推断时间复杂度为O(N^1.3)。

① 最坏的情况是逆序时，gap很大时，while循环的时间复杂度为O(N)

② 当gap很小时，本来应该是O(N*N) ，但是经过预排序后，数组已经接近有序，所以这里还是O(N)

（4）稳定性：不稳定

二、选择排序

选择排序基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

1.直接选择排序

基本思想：

（1）在元素集合array[i]—array[n-1]中选择关键码最大(小)的数据元素。

（2）若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个(第一个)元素交换。

（3）在剩余的array[i]—array[n-2]（array[i+1]—array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。

055-SelectSort.h

1. #pragma once
2. #include<stdio.h>
3. #include <stdlib.h>
4. 
5. //打印
6. void Print(int* a, int n);
7. 
8. //直接选择排序
9. void SelectSort(int* arr, int n);

055-SelectSort.c

1. #include"055-SelectSort.h"
2. 
3. //打印
4. void Print(int* a, int n)
5. {
6.  for (int i = 0; i < n; i++)
7.  {
8.    printf("%d ", a[i]);
9.  }
10. 
11.   printf("\n");
12. }
13. 
14. void Swap(int* p1, int* p2)
15. {
16.   int temp = *p1;
17.   *p1 = *p2;
18.   *p2 = temp;
19. }
20. 
21. //直接选择排序
22. void SelectSort(int* a, int n)
23. {
24.   int left = 0, right = n - 1;
25.   while (left < right)
26.   {
27.     //选出最大的值和最小的值
28.     int maxIndex = left, minIndex = left;
29.     for (int i = left; i <= right; i++)
30.     {
31.       if (a[i] < a[minIndex])
32.       {
33.         minIndex = i;
34.       }
35.       if (a[i] > a[maxIndex])
36.       {
37.         maxIndex = i;
38.       }
39.     }
40.     Swap(&a[left], &a[minIndex]);
41. 
42.     //如果maxIndex和left位置重叠，那么maxIndex位置的书就被换走了，要修正一下max的位置
43.     if (maxIndex == left)
44.     {
45.       maxIndex = minIndex;
46.     }
47. 
48.     Swap(&a[right], &a[maxIndex]);
49.     ++left;
50.     --right;
51.   } 
52. }

055-TestSelectSort.c

1. #include "055-SelectSort.h"
2. 
3. void TestSelectSort()
4. {
5.  int arr[] = { 10,9,8,7 6,5,4,3,2,1};
6.  SelectSort(arr, sizeof(arr) / sizeof(arr[0]));
7. 
8.  Print(arr, sizeof(arr) / sizeof(arr[0]));
9. }
10. 
11. int main()
12. {
13.   TestSelectSort();
14. 
15.   return 0;
16. }

直接选择排序的特性总结：

（1）直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

（2）时间复杂度：O(N^2)

（3）空间复杂度：O(1)

（4）稳定性：不稳定

2.堆排序

堆排序(Heapsort)是利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。堆的排序过程请查看文章【数据结构】堆-C语言版一文中堆的排序小节

055-HeapSort.h

1. #pragma once
2. #include<stdio.h>
3. #include<stdlib.h>
4. 
5. //打印
6. void Print(int* a, int n);
7. 
8. //堆排序
9. void HeapSort(int* arr, int n);

055-HeapSort.c

1. #include "055-HeapSort.h"
2. 
3. //打印
4. void Print(int* a, int n)
5. {
6.  for (int i = 0; i < n; i++)
7.  {
8.    printf("%d ", a[i]);
9.  }
10. 
11.   printf("\n");
12. }
13. 
14. void Swap(int* p1, int* p2)
15. {
16.   int temp = *p1;
17.   *p1 = *p2;
18.   *p2 = temp;
19. }
20. 
21. //向下调整
22. void AdjustDown(int* a, int n, int parent)
23. {
24.   int child = parent * 2 + 1;
25.   while (child < n)
26.   {
27.     //选出左右孩子中的小孩子，建大堆就把第二个<改成>
28.     if (child + 1 < n && a[child + 1] > a[child])
29.     {
30.       child++;
31.     }
32.     //小孩子比父亲小，交换小孩子和父亲，建大堆就把<改成>
33.     if (a[child] > a[parent])
34.     {
35.       Swap(&a[child], &a[parent]);
36.       //交换父亲和孩子后，可能导致不满足堆的定义，需要继续调整
37.       parent = child;
38.       child = parent * 2 + 1;
39.     }
40.     //小孩子比父亲大，跳出while循环，结束这一次的向下调整，否则一直死循环并且什么都不做
41.     else
42.     {
43.       break;
44.     }
45.   }
46. }
47. 
48. //堆排序
49. void HeapSort(int* a, int n)
50. {
51.   //升序，建大堆
52.   for (int i = (n - 1 - 1) / 2; i >= 0; i--)
53.   {
54.     AdjustDown(a, n, i);
55.   }
56.   int end = n - 1;
57.   while (end > 0)
58.   {
59.     Swap(&a[0], &a[end]);
60.     AdjustDown(a, end, 0);
61.     end--;
62.   }
63. }

055-TestHeapSort.c

1. #include "055-HeapSort.h"
2. 
3. void TestHeapSort()
4. {
5.  int arr[] = { 10,9,8,7 };
6.  HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
7.  Print(arr, sizeof(arr) / sizeof(arr[0]));
8. }
9. 
10. int main()
11. {
12.   TestHeapSort();
13. 
14.   return 0;
15. }

堆排序的特性总结：

（1）堆排序使用堆来选数，效率就高了很多。

（2）时间复杂度：O(N*logN)

（3）空间复杂度：O(1)

（4）稳定性：不稳定

【数据结构】排序-C语言版（一）

一、插入排序

二、选择排序

热门文章

最新文章

相关课程

相关电子书