深圳幻海软件技术有限公司 欢迎您！
更多

【数据结构】八大排序(二)

2023-05-18

int left end
😛作者：日出等日落📘专栏：数据结构在最黑暗的那段人生，是我自己把自己拉出深渊。没有那个人，我就做那个人。                

😛作者：日出等日落

📘 专栏：数据结构

在最黑暗的那段人生，是我自己把自己拉出深渊。没有那个人，我就做那个人。                                                                                                                                              ——中岛美嘉

😩快速排序：

Hoare版本(递归)：

基本思想：

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，这个排序很重要

其基本思想为：

任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

(官方语言，接下来请看详细解释)

动图演示：

基本思路： 

单趟排序，key一般选最左边或者最右边

★首先令key为最左边，右边先走找小，然后左边找大，然后交换位置继续，相遇则停止，相遇的值跟key对应的值交换

当左区间有序，右区间有序那整体就ok了，如果左右区间不有序，左右区间就是单趟的子问题

当区间只有一个值，就不排了，返回 

代码展示： 

  1. //快速排序
  2. void QuickSort(int* a, int begin, int end)
  3. {
  4. if (begin >= end)
  5. {
  6. return;
  7. }
  8.  
  9. int left = begin;
  10. int right = end;
  11. int keyi = left;
  12.  
  13. while (left < right)
  14. {
  15. //右边先走，找小
  16. while (left < right && a[right] >= a[keyi])
  17. {
  18. right--;
  19. }
  20. //左边找大
  21. while (left < right && a[left] <= a[keyi])
  22. {
  23. left++;
  24. }
  25. Swap(&a[left], &a[right]);
  26. }
  27. //相遇后随便一个下标，然后交换
  28. Swap(&a[left], &a[keyi]);
  29. keyi = left;
  30.  
  31. //左区间递归
  32. QuickSort(a, begin, keyi - 1);
  33. //右区间递归
  34. QuickSort(a, keyi + 1, end);
  37. }

可能就有小伙伴问为什么是key为最左边时，右边先走，最右边做key时，左边先走

原因是左边做key时，右边先走，可以保证相遇位置比key要小

此时有两种情况：

1.相遇时，left停住，right遇到left，相遇的位置是left停住的位置

2.相遇时，right停住，left遇到right，相遇的位置是right停住的位置

单趟排序的意义

1.分割出左右区间，左区间比key小，右区间比key大

2.key到了正确位置（排序后的最终位置）

优化方案：

三数取中：

在前面的快速排序中，

在理想情况下，我们每次进行完单趟排序后，key的左序列与右序列的长度都相同：

若每趟排序所选的key都正好是该序列的中间值，即单趟排序结束后key位于序列正中间，那么快速排序的时间复杂度就是O(NlogN)。

但事实上可能会遇到极端情况：就是我们每次取到的都是最大值或者最小值，那么快排的时间复杂度达到最低O（N^2）

那这样就和插入排序、冒泡排序时间复杂度一样了

这种情况下，快速排序的时间复杂度退化为O(N^2)。其实，对快速排序效率影响最大的就是选取的key，若选取的key越接近中间位置，则效率越高。

为了避免这种极端情况的发生，于是出现了三数取中：
 三数取中，当中的三数指的是：最左边的数、最右边的数以及中间位置的数。三数取中就是取这三个数当中，值的大小居中的那个数作为该趟排序的key。这就确保了我们所选取的数不会是序列中的最大或是最小值了。

代码实现：

  1. //三数取中
  2. int GetmidIndex(int* a, int begin, int end)
  3. {
  4. int mid = (begin + end) / 2;
  5. // a[begin]   a[mid]    a[end]
  6. // a[begin[ < a[mid[
  7. if (a[begin] < a[mid])
  8. {
  9. //a[begin] < a[mid] < a[end]
  10. if (a[mid] < a[end])
  11. {
  12. return mid;
  13. }
  14. //a[mid] > a[end] 再次判断
  15. else if (a[begin] > a[end])
  16. {
  17. return begin;
  18. }
  19. else
  20. {
  21. return end;
  22. }
  23. }
  24. // a[begin] > a[mid]
  25. else
  26. {
  27. //a[mid] > a[end]
  28. if (a[mid] > a[end])
  29. {
  30. return mid;
  31. }
  32. //a[mid] < a[end]
  33. else if (a[begin] < a[end])
  34. {
  35. return begin;
  36. }
  37. else
  38. {
  39. return end;
  40. }
  41. }
  42. }

完整快速排序代码：

  1. //Hoare 版本
  2. int PartSort1(int* a , int begin , int end)
  3. {
  4. int mid = GetmidIndex(a, begin, end);
  5. Swap(&a[begin], &a[mid]);
  6.  
  7. int left = begin;
  8. int right = end;
  9. int keyi = left;
  10.  
  11. while (left < right)
  12. {
  13. //右边先走，找小
  14. while (left < right && a[right] >= a[keyi])
  15. {
  16. right--;
  17. }
  18. //左边找大
  19. while (left < right && a[left] <= a[keyi])
  20. {
  21. left++;
  22. }
  23. Swap(&a[left], &a[right]);
  24. }
  25. //相遇后随便一个下标，然后交换
  26. Swap(&a[left], &a[keyi]);
  27. keyi = left;
  29. return keyi;
  30. }
  31.  
  32. //快速排序
  33. void QuickSort(int* a, int begin, int end)
  34. {
  35. if (begin >= end)
  36. {
  37. return;
  38. }
  39. if ((end - begin + 1) < 15)
  40. {
  41. //小区间用直接插入排序，减少递归调用次数
  42. InsertSort(a + begin, end - begin + 1);
  43. }
  44. else
  45. {
  46. int keyi = PartSort1(a, begin, end);
  47. //左区间递归
  48. QuickSort(a, begin, keyi - 1);
  49. //右区间递归
  50. QuickSort(a, keyi + 1, end);
  51. }
  53. }

挖坑法：

基本思想：

挖坑法的思想很简单：

一开始先将left下标对应的值保存起来，然后left位置空出来的位置就是一个坑位，右边先走，找大，找到后将右边的值的数据填进去，这个right的位置就是新的坑，左边找小，再将左边找到的填进坑位，这个left对应下标的位置就是新的坑位，最后left和right一定会在坑的位置相遇

代码展示： 

  1. //挖坑法
  2. int PartSort2(int* a, int begin, int end)
  3. {
  4. int mid = GetmidIndex(a, begin, end);
  5. Swap(&a[begin], &a[mid]);
  6.  
  7. int left = begin;
  8. int right = end;
  9. int key = a[left];
  10. int hole = left;
  11.  
  12. while (left < right)
  13. {
  14. //右边先走，找小于key的
  15. while (left < right && a[right] >= key)
  16. {
  17. right--;
  18. }
  19. a[hole] = a[right];
  20. hole = right;
  21. //左边找大于key的;
  22. while (left < right && a[left] <= key)
  23. {
  24. left++;
  25. }
  26. a[hole] = a[left];
  27. hole = left;
  28. }
  29. a[hole] = key;
  30. return hole;
  31. }
  32. //快速排序
  33. void QuickSort(int* a, int begin, int end)
  34. {
  35. if (begin >= end)
  36. {
  37. return;
  38. }
  39. if ((end - begin + 1) < 15)
  40. {
  41. //小区间用直接插入排序，减少递归调用次数
  42. InsertSort(a + begin, end - begin + 1);
  43. }
  44. else
  45. {
  46. int keyi = PartSort2(a, begin, end);
  47. //左区间递归
  48. QuickSort(a, begin, keyi - 1);
  49. //右区间递归
  50. QuickSort(a, keyi + 1, end);
  51. }
  53. }

前后指针法：

动图演示:

基本思路：

1、cur下标对应的值找比key小的，找到后停下来
2、然后++prev, 交换prev位置和cur位置的值

最后重复上述操作

时间复杂度:O(NlogN) 

  1. //前后指针法
  2. int PartSort3(int* a, int begin, int end)
  3. {
  4. int prev = begin;
  5. int cur = begin + 1;
  6. int keyi = begin;
  7. while (cur <= end)
  8. {
  9. //cur 先走
  10. if (a[cur] <= a[keyi] && ++prev != cur)
  11. {
  12. Swap(&a[cur], &a[prev]);
  13. }
  14. cur++;
  15. }
  16. Swap(&a[prev], &a[keyi]);
  17. keyi = prev;
  18. return keyi;
  19. }
  20. //快速排序
  21. void QuickSort(int* a, int begin, int end)
  22. {
  23. if (begin >= end)
  24. {
  25. return;
  26. }
  27. if ((end - begin + 1) < 15)
  28. {
  29. //小区间用直接插入排序，减少递归调用次数
  30. InsertSort(a + begin, end - begin + 1);
  31. }
  32. else
  33. {
  34. int keyi = PartSort3(a, begin, end);
  35. //左区间递归
  36. QuickSort(a, begin, keyi - 1);
  37. //右区间递归
  38. QuickSort(a, keyi + 1, end);
  39. }
  41. }

非递归写法： 

基本思路：

借用栈来实现

通过非递归的方式实现递归的情况的话，快速排序递归是先排左区间再排右区间，以此类推，因此写非递归我们就需要反过来，因为栈是后入先出的。

借助栈的内存结构让先入的后出，所以要先压begin再压end，取出来的话就是先出end再出begin，然后先排右区间顺序再排左区间顺序。

代码实现： 

  1. //前后指针法
  2. int PartSort3(int* a, int begin, int end)
  3. {
  4. int prev = begin;
  5. int cur = begin + 1;
  6. int keyi = begin;
  7. while (cur <= end)
  8. {
  9. //cur 先走
  10. if (a[cur] <= a[keyi] && ++prev != cur)
  11. {
  12. Swap(&a[cur], &a[prev]);
  13. }
  14. cur++;
  15. }
  16. Swap(&a[prev], &a[keyi]);
  17. keyi = prev;
  18. return keyi;
  19. }
  20.  
  21. //快速排序(非递归)
  22. void QuickSortNonR(int* a, int begin, int end)
  23. {
  24. ST st;
  25. StackInit(&st);
  26. StackPush(&st, begin);
  27. StackPush(&st, end);
  28. while (!StackEmpty(&st))
  29. {
  30. int right = StackTop(&st);
  31. StackPop(&st);
  32. int left = StackTop(&st);
  33. StackPop(&st);
  34.  
  35. int keyi = PartSort3(a, left, right);
  36. // [left , keyi-1]  keyi  [keyi+1 , right]
  37. if (keyi + 1 < right)
  38. {
  39. StackPush(&st, keyi + 1);
  40. StackPush(&st, right);
  41. }
  42. if (keyi - 1 > left)
  43. {
  44. StackPush(&st, left);
  45. StackPush(&st, keyi - 1);
  46. }
  47. }
  48.  
  49. StackDestroy(&st);
  50. }

🤦‍♂️归并排序：

递归算法：

基本思想：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

动图演示：

代码实现：

  1.  
  2. void _MergeSort(int* a ,int begin ,int end,int* tmp)
  3. {
  4. if (begin >= end)
  5. return;
  6. int mid = (begin + end) / 2;
  7. //[begin , mid] [ mid +1 , end] 递归子区间有序
  8. _MergeSort(a, begin, mid, tmp);
  9. _MergeSort(a, mid + 1, end, tmp);
  10.  
  11. //归并
  12. int begin1 = begin;
  13. int end1 = mid;
  14. int begin2 = mid + 1;
  15. int end2 = end;
  16. int i = begin;
  17. while (begin1 <= end1 && begin2 <= end2)
  18. {
  19. if (a[begin1] <= a[begin2])
  20. {
  21. tmp[i++] = a[begin1++];
  22. }
  23. else
  24. {
  25. tmp[i++] = a[begin2++];
  26. }
  27. }
  28. while (begin1 <= end1)
  29. {
  30. tmp[i++] = a[begin1++];
  31. }
  32. while (begin2 <= end2)
  33. {
  34. tmp[i++] = a[begin2++];
  35. }
  36. memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
  37. }
  38.  
  39. //归并排序
  40. void MergeSort(int* a, int n)
  41. {
  42. int* tmp = (int*)malloc(sizeof(int) * n);
  43. if (tmp == NULL)
  44. {
  45. perror("malloc: fail ");
  46. exit(-1);
  47. }
  48.  
  49. _MergeSort(a, 0, n - 1, tmp);
  50. free(tmp);
  51. tmp = NULL;
  52. }

非递归算法：

非递归算法需要注意的是越界问题：

1.end1越界 begin2越界end2越界

2.begin2越界end2越界

3.end2越界

代码实现： 

  1. //归并非递归排序
  2. void MergeSortNonR(int* a, int n)
  3. {
  4. int* tmp = (int*)malloc(sizeof(int) * n);
  5. if (tmp == NULL)
  6. {
  7. perror("malloc: fail ");
  8. exit(-1);
  9. }
  10.  
  11. // 归并每组数据个数，从1开始，
  12. //因为1个认为是有序的，可以直接归并
  13. int rangeN = 1;
  14. while (rangeN < n)
  15. {
  16. for (int i = 0; i < n; i += 2 * rangeN)
  17. {
  18. // [begin1,end1]  [begin2,end2] 归并
  19. int begin1 = i; 
  20. int end1 = i + rangeN - 1;
  21. int begin2 = i + rangeN;
  22. int end2 = i + 2 * rangeN - 1;
  23. int j = i;
  24.  
  25. //end1越界
  26. if(end1 >=n)
  27. {
  28. end1 = n - 1;
  29. begin2 = n;
  30. end2 = n - 1;
  31. }
  32. //begin2 , end2越界
  33. else if (begin2 >= n)
  34. {
  35. begin2 = n;
  36. end2 = n - 1;
  37. }
  38. //end2越界
  39. else if (end2 >= n)
  40. {
  41. end2 = n - 1;
  42. }
  43. while (begin1 <= end1 && begin2 <= end2)
  44. {
  45. if (a[begin1] <= a[begin2])
  46. {
  47. tmp[j++] = a[begin1++];
  48. }
  49. else
  50. {
  51. tmp[j++] = a[begin2++];
  52. }
  53. }
  54. while (begin1 <= end1)
  55. {
  56. tmp[j++] = a[begin1++];
  57. }
  58. while (begin2 <= end2)
  59. {
  60. tmp[j++] = a[begin2++];
  61. }
  62. memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
  63. }
  64. rangeN *= 2;
  65. }
  66. free(tmp);
  67. tmp = NULL;
  68. }

归并排序总结：

归并排序的特性总结：

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。

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

3. 空间复杂度：O(N)

4. 稳定性：稳定

😢计数排序：

计数排序是一种非比较排序。它的主要思想是建立一个临时数组 CountArr ，用来统计序列中每个元素出现的次数，

例如若序列元素 n 一共出现了 m 次，则使 CountArr [n] = m；统计完毕后。根据统计的结果，将序列按顺序插入到原数组中即完成排序。

代码实现： 

  1. //计数排序
  2. void CountSort(int* a, int n)
  3. {
  4. int max = a[0], min = a[0];
  5. //找出最大值，最小值
  6. for (int i = 1; i < n; ++i)
  7. {
  8. if (a[i] < min)
  9. min = a[i];
  10. if (a[i] > max)
  11. max = a[i];
  12. }
  13. //开一个数组
  14. int range = max - min + 1;
  15. int* countArr = (int*)calloc(range, sizeof(int) * range);
  16. if (countArr == NULL)
  17. {
  18. perror("calloc fail");
  19. exit(-1);
  20. }
  21. //1.统计次数
  22. for (int i = 0; i < n; ++i)
  23. {
  24. countArr[a[i] - min]++;
  25. }
  26. //2.排序
  27. int k = 0;
  28. for (int i = 0; i < range; ++i)
  29. {
  30. while (countArr[i]--)
  31. {
  32. a[k++] = i + min;
  33. }
  34. }
  35. free(countArr);
  36.  
  37. }

 

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览46513 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪