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

三、交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

1.冒泡排序

基本思想：依次比较相邻的两个数，将较小数放在前面，较大数放在后面，如此继续，直到比较到最后的两个数，将小数放在前面，大数放在后面，重复步骤，直至全部排序完成

055-BubbleSort.h

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

055-BubbleSort.c

1. #include "055-BubbleSort.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 BubbleSort(int* a, int n)
23. {
24.   for (int i = 0; i < n; i++)
25.   {
26.     for (int j = 0; j < n - i - 1; j++)
27.     {
28.       if (a[i] > a[j])
29.       {
30.         Swap(&a[i], &a[j]);
31.       }
32.     }
33.   }
34. }

055-TestBubbleSort.c

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

冒泡排序的特性总结：

（1）冒泡排序是一种非常容易理解的排序

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

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

（4）稳定性：稳定

2.快速排序

是一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

（1）hoare版本

单趟排序：选出一个key，一般是最左边的，或者是最右边，key放到正确位置上去，目的是让key左边的比key小，key右边的比key大。

当让最左为key时，让 right先走，right找比key小的值，left找比key大的值，都找到后交换left和right位置的值直到相遇。

055-QuickSortHoare.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 QuickSort_hoare(int* a, int begin, int end);

055-QuickSortHoare.c

1. #include "055-QuickSortHoare.h"
2. 
3. //快速排序
4. void QuickSortHoare(int* a, int begin,int end)
5. {
6.  if (begin >= end)
7.  {
8.    return;
9.  }
10.   int left = begin,  right = end;
11.   int key = left;
12. 
13.   while (left < right)
14.   {
15.     //找小
16.     while (a[right] >= a[key] && left < right)
17.     {
18.       right--;
19.     }
20. 
21.     //找大
22.     while (a[left] <= a[key] && left < right)
23.     {
24.       left++;
25.     }
26. 
27.     Swap(&a[left], &a[right]);
28.   }
29. 
30.   int meeti = left;
31. 
32.   Swap(&a[meeti], &a[key]);
33. 
34.   QuickSort_hoare(a, begin, meeti - 1);
35.   QuickSort_hoare(a, meeti + 1, end);
36. }

055-TestQuickSortHoare.c

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

（2）挖坑法

key为左边第一个元素，把第一个元素挖出来，空出一个坑，left指向第一个元素，right指向最后一个元素，从右向左找比key小的元素放坑里，空出来一个坑，再从左向右找比key大的元素放坑里，如果left和right相遇，就把key放坑里，递归调用。

055-QuickSortHole.h

1. #pragma once
2. #include<stdio.h>
3. #include <stdlib.h>
4. 
5. //打印
6. void Print(int* a, int n);
7. 
8. //快速排序hole
9. void QuickSortHole(int* a, int begin, int end);

055-QuickSortHole.c

1. #include "055-QuickSortHole.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. //快速排序hole
15. void QuickSortHole(int* a, int left, int right)
16. {
17.   int begin = left, end = right;
18.   int key = a[left];
19. 
20.   while (left < right)
21.   {
22.     //找小
23.     while (a[right] >= key && left < right)
24.     {
25.       right--;
26.     }
27. 
28.     //放到左边的坑位中，右边就形成新的坑
29.     a[left] = a[right];
30. 
31.     //找大
32.     while (a[left] <= key && left < right)
33.     {
34.       left++;
35.     }
36. 
37.     //放到右边的坑位中，左边就形成新的坑
38.     a[right] = a[left];
39.   }
40. 
41.   a[left] = key;
42. 
43.   if (left - 1 > begin)
44.   {
45.     QuickSortHole(a, begin, left - 1);
46.   }
47.   if (end > left + 1)
48.   {
49.     QuickSortHole(a, left + 1, end);
50.   }
51. 
52. }

055-TestQuickSortHole.c

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

（3）前后指针法

指定第一个元素为key，prev指针指向第一个元素位置，cur指针指向第二个元素位置

（1）当cur位置的元素大于key时，cur指向下一个位置。

（2）当cur位置的元素小于key时，让prev指向下一个元素位置，再判断prev和cur的位置是否相等：

①如果相等就让cur指向下一个位置

②如果不相等就让cur和prev位置的元素进行交换。

055-QuickSortPointer.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 QuickSortPointer(int a, int begin, int end);

055-QuickSortPointer.c

1. #include "055-QuickSortPointer.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. int PartSort(int* a, int left, int right)
16. {
17.   int key = a[left];
18.   int prev = left，cur = left+1;
19. 
20.   while (cur <= right)
21.   {
22.     //(a[cur] < key)&&(++prev!=cur) ===> Swap(&a[prev],&a[cur])
23.     if (a[cur] < key && ++prev != cur)
24.     {
25.       Swap(&a[cur], &a[prev]);
26.     }
27. 
28.     //(a[cur] > key)||((a[cur] < key) && (++prev==cur))  ===> cur++
29.     cur++;
30.   }
31.   //cur > end ===> Swap(&a[prev],&key)
32.   Swap(&a[prev], &a[left]);
33.   return prev;
34. }
35. 
36. 
37. void QuickSortPointer(int a, int begin, int end)
38. {
39.   if (begin >= end)
40.   {
41.     return;
42.   }
43. 
44.   int keyi = PartSort(a, begin, end);
45. 
46.   QuickSortPointer(a, begin, keyi - 1);
47.   QuickSortPointer(a, keyi + 1, end);
48. }

055-TestQuickSortPointer.c

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

（4）快速排序优化-三数取中法

快速排序的时间复杂度是O(N)，快排最理想的效率就是每次选择的key都是是下标为中位数的元素，即每次进行完单趟排序后，key的左序列与右序列的长度都相同，这时的时间复杂度为O(NlogN)。

效率最低的的情况就是数组有序，那么每次选取的key都是序列中最左或最右的元素。如果每次选择的key都是最大或最小的，会退化成选择排序，时间复杂度变成了O(N^2)。

由此可看出key越接近中间位置，效率越高。为了避开每次选择最大或最小的key，避免对数组有序的情况下使用快排排序，使用三数取中法：key取a[left]、a[mid]、a[right]三者进行比较后的值中居中的值，这就避免了每次选取的key不会是待排序数组中最大或最小值。

按照前面的代码，选取的key一般都是数组最左端的元素，如果上面拿到的居中值的位置不在最左端怎么办？将居中值和最左端元素a[left]交换一下即可，这就能保证a[left]一定是居中值，前面的代码也不需要改变。

055-QuickSortThreeNumberMid.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 QuickSortThreeNumberMid(int a, int begin, int end);

055-QuickSortThreeNumberMid.c

1. #include "055-QuickSortThreeNumberMid.h"
2. 
3. //选取a[left]、a[mid]、a[right]中的居中值
4. int GetMidIndex(int* a, int left, int right)
5. {
6.  int mid =left + (left + right)/2;
7. 
8.  if (a[left] < a[mid])
9.  {
10.     if (a[mid] < a[right])
11.     {
12.       return mid;
13.     }
14.     else if (a[left] > a[right])
15.     {
16.       return left;
17.     }
18.     else
19.     {
20.       return right;
21.     }
22.   }
23.   else
24.   {
25.     if (a[mid] > a[right])
26.     {
27.       return mid;
28.     }
29.     else if (a[left] < a[right])
30.     {
31.       return left;
32.     }
33.     else
34.     {
35.       return right;
36.     }
37.   }
38. 
39. }
40. 
41. //快排
42. int PartSort1(int* a, int left, int right)
43. {
44.     //找居中值
45.   int mid = GetMidIndex(a,left,right);
46.     //交换居中值和最左端元素
47.   Swap(&a[left], &a[mid]);
48. 
49.   int key = left;
50.   while (left < right)
51.   {
52.     //找小
53.     while (a[right] >= a[key] && left < right)
54.     {
55.       right--;
56.     }
57. 
58.     //找大
59.     while (a[left] <= a[key] && left < right)
60.     {
61.       left++;
62.     }
63. 
64.     Swap(&a[left], &a[right]);
65.   }
66. 
67.   Swap(&a[left], &a[key]);
68. 
69.   return left;
70. 
71. }
72. 
73. void QuickSortThreeNumberMid(int a, int begin, int end)
74. {
75.   if (begin >= end)
76.   {
77.     return;
78.   }
79. 
80.   int keyi = PartSort1(a, begin, end);
81. 
82.   QuickSortThreeNumberMid(a, begin, keyi - 1);
83.   QuickSortThreeNumberMid(a, keyi + 1, end);
84. }
85.

055-TestQuickSortThreeNumberMid.c

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

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

三、交换排序

热门文章

最新文章

相关课程

相关电子书