当前位置:   article > 正文

排序算法之快速排序(挖坑法)_快速排序挖坑法主代码

快速排序挖坑法主代码

挖坑法的思想:记第一个数为key,要调整key的位置,使得左边的都要比key的小,右边的数都比key的大。

记录下关键字key==begin,把28那个位置挖坑hole==begin

让end找到小于28(key)的数,把那个数放到hole坑中,然后让hole==end

再从左边begin找大于28(key)的数,把那个数放在hole中,然后让hole==begin

结束条件begin>=end调出循环。然后arr[hole]=key;

完成一趟的调整。

  1. //一趟挖坑
  2. int arr[]={5,3,2,6,7,4,9};
  3. int n=sizeof(arr)/sizeof(arr[0]);
  4. int begin=0;
  5. int end=n-1;
  6. while(begin<end
  7. {
  8. while(begin<end&&arr[end]>=key)
  9. {
  10. end--;
  11. }
  12. arr[hole]==arr[end];
  13. hole==end;
  14. while(begin<end&&arr[begin]<=key)
  15. {
  16. begin++;
  17. }
  18. arr[hole]==arr[begin];
  19. hole=begin;
  20. }
  21. arr[hole]==key;

分治思想,分成左边和右边。

用到分治递归,就要改变函数的参数,要有left和right

你们以为这样子快排就无敌了吗?不!当key每次取到的数都是最小或者最大,(也就是数组有序的情况下)它的时间复杂度会达到O(N^2)

那要怎么优化呢?三数取中法,就是创建一个函数,比较left,right,mid三个数,取大小是中等的数。然后把中等大小的数的下标返回出来,出来之后与begin(left)交换,为了确保不大改动原代码。

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

整体的代码如下:

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<stdio.h>
  3. int GetMidIndex(int* a, int left,int right)
  4. {
  5. int mid = (left + right) / 2;
  6. if (a[mid] > a[left])
  7. {
  8. if (a[mid] <= a[right])
  9. {
  10. return mid;
  11. }
  12. if (a[mid] > a[right])
  13. {
  14. if (a[right] >= a[left])
  15. {
  16. return right;
  17. }
  18. else
  19. {
  20. return left;
  21. }
  22. }
  23. }
  24. if(a[mid]<=a[left])
  25. {
  26. if (a[left] <= a[right])
  27. {
  28. return left;
  29. }
  30. if (a[left] > a[right])
  31. {
  32. if (a[right] > a[mid])
  33. {
  34. return right;
  35. }
  36. else
  37. {
  38. return mid;
  39. }
  40. }
  41. }
  42. }
  43. void Swap(int* a, int* b)
  44. {
  45. int tmp = *a;
  46. *a = *b;
  47. *b = tmp;
  48. }
  49. //1.挖坑法的快速排序
  50. void QuickSort(int* a,int left,int right)
  51. {
  52. if (left >= right)//不能写成pivot==left,pivot-1left不匹配,会报错
  53. {
  54. return;
  55. }
  56. int index = GetMidIndex(a, left, right);
  57. Swap(&a[index], &a[left]);
  58. int begin = left,end = right;
  59. int key = a[begin];//挖了一个关键字
  60. int pivot = begin;//挖了一个坑
  61. while (begin < end)
  62. {
  63. //右边找小,一定要先右边找小,放在pivot
  64. while (begin < end&&a[end] >= key)//在这里也要判断begin < end,因为这里面end--
  65. {
  66. end--;
  67. }
  68. //小的放在左边的坑里,然后形成新的坑位
  69. a[pivot] = a[end];
  70. pivot = end;
  71. //左边找大
  72. while (begin < end && a[begin] <= key)
  73. {
  74. begin++;
  75. }
  76. a[pivot] = a[begin];
  77. pivot = begin;
  78. }
  79. //begin==end
  80. a[pivot] = key;
  81. //[left,right]
  82. //[left,pivot-1] pivot [pivot+1,right]
  83. //如果左子区间和右子区间都有序,就全部有序。那就分治递归。
  84. QuickSort(a, left, pivot - 1);
  85. QuickSort(a, pivot+1, right);
  86. }
  87. void PRINT(int* a, int n)
  88. {
  89. for (int i = 0; i < n; i++)
  90. {
  91. printf("%d ", a[i]);
  92. }
  93. }
  94. int main()
  95. {
  96. int arr[] = { 5,6,8,9,3,1,4,7,5,1 };
  97. int n = sizeof(arr) / sizeof(arr[0]);
  98. QuickSort(arr, 0,n-1);
  99. PRINT(arr,n);
  100. return 0;
  101. }

注意:在QuickSort函数中,取到中等值的下标的时候,把中等值的位置与最左边的值交换一下。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/寸_铁/article/detail/1002819
推荐阅读
相关标签
  

闽ICP备14008679号