经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 程序设计 » C++ » 查看文章
[排序算法] 快速排序 (C++) (含三种写法)
来源：cnblogs　　作者：Amαdeus　　时间：2022/11/21 9:03:04　　对本文有异议

快速排序解释

快速排序 Quick Sort 与归并排序一样，也是典型的分治法的应用。 (如果有对 归并排序还不了解的童鞋，可以看看这里哟~ 归并排序)???

快速排序的分治模式

1、选取基准值，获取划分位置。将原数组 a[l, r] 划分为两个子数组 a[l, mid - 1] 和 a[mid + 1, r]。在前一个数组中所有元素都小于等于 a[mid]，后一个数组中所有元素都大于等于 a[mid]。而此时的 a[mid] 的值就是我们所取的基准值，mid 就每次划分的位置；

2、递归调用快速排序函数，分别对两个子数组 a[l, mid - 1] 和 a[mid + 1, r] 排序；

3、快速排序我们是在原数组上进行操作的，所以我们并不需要合并，最后 a[l, r] 已经有序。

快速排序的三种写法

快速排序比较普及的有三种写法，分别是 左右指针法 挖坑法 和 前后指针法。主要是取得划分位置实现的方法有所不同。
接下来会逐个介绍这三种快速排序的写法。


左右指针法

左右指针法步骤

1、首先 我们一般选取最左边的元素作为基准值 key。

2、然后我们需要定义两个变量 i 和 j。
其中 i 为左指针(其实不是指针啦，只是为了方便这么叫它??)，初始 i = 0。 j 为右指针，初始 j = r - 1，向左遍历不断找到小于基准值 key 的元素。

3、我们先动右指针 j 向左遍历直到找到小于当前基准值 key 的元素；然后我们再动左指针 i 向右遍历直到找到大于当前基准值 key 的元素。
当 i 和 j 分别找到它们要找的元素时，我们需要将两个元素进行位置交换。( 在这个过程中我们要保持 i < j )

4、重复步骤3，直到最后我们可爱的左右指针相遇，这时我们再将基准值 key，放到这两个指针指向的位置。此时我们就得到了当前划分的位置，基准值 key 也完成了归位。

左右指针法移动指针先后顺序问题

在上述步骤中，有些人会感到疑惑，那就是我们再移动指针时，每次都要 先移动右指针，再移动左指针。为什么呢？??????

在取基准值时，我们一般都是将序列的最左边位置的元素作为基准值。我们每次交换完元素后，左右指针都会继续寻找他们要找的值，观感上就是相互靠近。而问题就出在我们退出循环的那一刻。

我们一直保持 i < j，也就是说，我们会在 i == j 时退出循环。假设 在某次交换之后，此时 j 指向的是交换之后的一个大于基准值的元素，如果我们先动左指针 i 去寻找一个大于基准值的元素，然鹅还未找到就已经和右指针 j 相遇了，这个时候我们需要退出循环，交换基准值 key 到当前两个指针指向的位置。
但是!!!，此时 i 和 j 指向的是大于基准值的元素，那么我们进行交换基准值位置操作后，这个大于基准值的元素就被换到了序列的最左端，很明显，这时候出现了非常非常非常严重的错误。

那如果我们先动右指针 j，去寻找一个小于基准值的元素，然鹅没有找到就已经和左指针 i 相遇了，这个时候退出循环，i 和 j 指向的一定是一个小于等于基准值的值。

究其原因，这其实是我们取最左边的元素作为基准值导致的。我们需要保证每次交换过来的元素是小于等于基准值的，所以我们先动右指针，再动左指针。


左右指针法动态演示

我们以序列 [3,14,6,1,2,17,7] 为例进行动态演示。(后面还会有先动左指针的错误演示)

左右指针法正确演示

左右指针法错误演示


左右指针法核心代码

  1. //左右指针法  
  2. int Partition_Hoare(vector<int> &a, int left, int right){
  3.     int i = left;
  4.     int j = right;
  5.     int key = a[left];
  7.     while(i != j){
  8.         while(i < j && a[j] >= key)      	 //向左找到小于基准值的值的下标
  9.             j--;
  10.         while(i < j && a[i] <= key)      	 //向右找到大于基准值的值的下标
  11.             i++;
  12. 	swap(a[i], a[j]);
  13. 	}
  14.     /*   i等于j时跳出循环 当前基准值此时在下标为i的位置(合适的位置)   */
  15.     swap(a[left], a[i]);	                 //最左边的元素变为处于当前合适位置的元素,把基准值放在合适位置                                                 
  16.     return i;                                  //返回合适位置(i,j都可以)
  17. }

挖坑法

挖坑法步骤

挖坑法顾名思义，就是每次挖一个坑填入元素使其归位。和左右指针法一样，我们同样需要两个变量 i 和 j。
1、我们一般取最左边的元素为基准值，然后在基准值处挖空(挖坑)

2、先动右指针 j 向左找到一个小于基准值的元素，然后将其填入先前挖的坑中，同时 j 指向的位置也多出来一个坑位。

3、再动左指针 i 向右找到一个大于基准值的元素，然后将其填入先前挖的坑中，同时 i 指向的位置又多出来一个坑位。

4、重复上述操作，直到最后两个指针相遇，此时再在这个坑位上填入基准值，即完成了基准值的归位，也就是我们划分的位置。

(具体实现这个挖坑填坑的方式可以是元素值的覆盖，也可以是元素交换的形式，在后面的核心代码中会给出这两种方式)

挖坑法动态演示

我们以序列 [3,14,6,1,2,17,7] 为例进行动态演示。

图(1)

图(2)


挖坑法核心代码

  1. //挖坑法1  
  2. int Partition_DigI(vector<int> &a, int left, int right){
  3.     int i = left;
  4.     int j = right;
  5.     int key = a[left];
  7.     while(i != j){
  8. 	while(i < j && a[j] >= key)          //必须先动右边的 因为取的基准值在左边
  9. 	    j--;                             //向左寻找直到找到比基准值小的
  10. 	a[i] = a[j];                         //挖坑 填入比基准值小的值
  12. 	while(i < j && a[i] <= key)          //再动左边的
  13. 	    i++;                             //向右寻找直到找到比基准值大的 
  14. 	a[j] = a[i];                         //挖坑 填入比基准值大的值
  15.     }
  16.     /*   i等于j时跳出循环 下标为i的位置即为合适的插入位置   */
  17.     a[i] = key;                              //在i,j相遇的地方填入基准值
  18.     return i;
  19. }
  21. //挖坑法2 
  22. int Partition_DigII(vector<int> &a, int left, int right){
  23.     int i = left;                            //从左边开始
  24.     int j = right;                           //从右边开始
  25.     int key = a[left];                       //将最左边的数设为基准值	
  27.     while(i != j){                           
  28. 	while(i < j && a[j] >= key)          //必须先动右边的 因为取的基准值在左边
  29. 	    j--;                             //向左寻找直到找到比基准值小的
  30. 	swap(a[i], a[j]);                    //交换
  31. 	i++;                                 //看下一个（可以省略）
  33. 	while(i < j && a[i] <= key)          //再动左边的
  34. 	    i++;                             //向右寻找直到找到比基准值大的    
  35. 	swap(a[i], a[j]);                    //交换
  36. 	j--;                                 //看下一个（可以省略）
  37.     }  
  38.     /* 一轮循环后基准值所在位置左边的数都比基准值小,右边的都比基准值大 */
  39.     /*   i等于j时跳出循环 当前基准值此时在下标为i的位置(合适的位置)   */                       
  40.     return i;                                //返回基准值合适位置
  41. }

前后指针法

前后指针法步骤

前后指针法同样需要两个指针，一个是 pre，一个是 curr。pre 最后找到的是划分后左半部分最后一个小于基准值的元素。
1、一开始我们一般将前指针 pre 指向待排序序列的第一个元素，后指针 curr 指向 pre 后面的一个元素。

2、然后我们让 后指针 curr 去寻找小于当前基准值的元素，若找到这个元素，此时需要将这个小于基准值的元素和当前 前指针 pre 后一个的位置的元素进行交换，即与 pre + 1 位置的元素进行交换，同时前指针 pre 也往后移动一步。

3、在上述过程中我们需要保持 curr <= r，当 curr > r 退出循环时，需要将当前 pre 所指向的元素和基准值进行交换。最后返回这个pre，即为我们划分的位置。


前后指针法动态演示

我们以序列 [3,14,6,1,2,17,7] 为例进行动态演示。

图(1)

图(2)


前后指针法核心代码

  1. //前后指针法  
  2. int Partition_PreAndCurr(vector<int> &a, int left, int right){
  3.     int pre = left;                          //pre最后找到左半部分最后一个小于基准值的元素
  4.     int curr = pre + 1;                      //curr找到pre指向元素之后的下一个小于基准值的元素
  5.     int key = a[left];
  7.     while(curr <= right){
  8. 	if(a[curr] < key && ++pre != curr)   //当a[curr]>=key时pre保持不动,直到最后curr找到下一个小于基准值的元素
  9. 	    swap(a[curr], a[pre]);           //pre往后移动到其下一个位置,并交换前后指针指向的元素
  10. 	curr++;
  11.     }
  12.     swap(a[left], a[pre]);                   //最后将基准值和此时处于pre位置的小于基准值的元素交换
  13.     return pre;
  14. }

快速排序时间复杂度

假设时间复杂度为 T(n)。在进行取得划分位置上我们需要消耗 O(n) 的时间，在递归调用快速排序函数上，最好情况下如果每次我们取得的划分位置为n/2的位置，即消耗了 2T(n/2) 的时间。最坏情况下如果每次我们取得的划分位置为首或尾的位置，即消耗 T(n-1)+T(0)的时间。
故时间复杂度如下

最优时间复杂度

最坏时间复杂度


取基准值优化

如何高效取基准值

对于取基准值，我们发现 如果当前所取的基准值恰好是当前序列中最小的数或者最大的数，那么我们的划分位置必然是首或尾的位置，如果每次都这个亚籽，我们消耗的时间会非常的多，这显然就是最坏情况下的时间复杂度的状况。

那么我们如何尽量地避免这件事呢？??????

我们自然会想到随机取数，这固然是一个很好的办法，但是这个世界充满了无限可能性。假如我们原先最左边的元素并不是最小或最大的一个元素，但是随机取到的元素却恰好是那个最小或最大的元素呢？

(当然随机取数这个方法也是值得尝试的，后续程序中我不会用这个方式实现取基准值的优化，如果有需要，只需要把取基准值的几行代码改成如下就可以了)

  1. int random = rand() % (right - left + 1) + left;  
  2. swap(a[random], a[left]);
  3. int key = a[left]

为了避免这种充满戏剧性的情况，我们采取 三数取中 的方法取基准值。

三数取中，就是取序列中的最左边，中间，以及最右边三个数进行比较，以这三个数大小为中的元素作为基准值。这样可以更大程度上避免划分位置不好的情况，即使其并不能彻底避免，但是是一个很好的办法。


取基准值优化核心代码

  1. int GetMid(int a[], int left, int right){
  2. 	int mid = (left + right)>>1;   
  3. 	if(a[left] < a[mid])
  4. 	    if(a[mid] < a[right])
  5. 		return mid;                      //mid为中间值
  6. 	    else
  7. 		if(a[left] < a[right])
  8. 		    return right;                //right为中间值
  9. 		else
  10. 		    return left;                 //left为中间值
  11. 	else
  12. 	    if(a[mid] > a[right])
  13. 		return mid;                      //mid为中间值
  14. 	    else
  15. 		if(a[left] > a[right])
  16. 		    return right;                //right为中间值
  17. 		else
  18. 		    return left;                 //left为中间值
  19. }

完整程序源代码

  1. #include<iostream>
  2. #include<vector>
  3. #include<time.h>
  4. using namespace std;
  6. /*                               1                                  */
  7. //左右指针法  
  8. int Partition_Hoare(vector<int> &a, int left, int right){
  9. 	int i = left;
  10. 	int j = right;
  11. 	int key = a[left];
  13. 	while(i != j){
  14. 	    while(i < j && a[j] >= key)      	 //向左找到小于基准值的值的下标
  15.                 j--;
  16.             while(i < j && a[i] <= key)      	 //向右找到大于基准值的值的下标
  17.                 i++;
  18. 	    swap(a[i], a[j]);
  19. 	}
  20. 	/*   i等于j时跳出循环 当前基准值此时在下标为i的位置(合适的位置)   */
  21. 	swap(a[left], a[i]);	                 //最左边的元素变为处于当前合适位置的元素,把基准值放在合适位置                                     
  22. 	return i;                                //返回合适位置(i,j都可以)
  23. }
  27. /*                                 2                                */
  28. //挖坑法1  
  29. int Partition_DigI(vector<int> &a, int left, int right){
  30.     int i = left;
  31.     int j = right;
  32.     int key = a[left];
  34.     while(i != j){
  35. 	while(i < j && a[j] >= key)          //必须先动右边的 因为取的基准值在左边
  36. 	    j--;                             //向左寻找直到找到比基准值小的
  37. 	a[i] = a[j];                         //挖坑 填入比基准值小的值
  39. 	while(i < j && a[i] <= key)          //再动左边的
  40. 	    i++;                             //向右寻找直到找到比基准值大的 
  41. 	a[j] = a[i];                         //挖坑 填入比基准值大的值
  42.     }
  43.     /*   i等于j时跳出循环 下标为i的位置即为合适的插入位置   */
  44.     a[i] = key;                              //在i,j相遇的地方填入基准值
  45.     return i;
  46. }
  48. //挖坑法2 
  49. int Partition_DigII(vector<int> &a, int left, int right){
  50.     int i = left;                            //从左边开始
  51.     int j = right;                           //从右边开始
  52.     int key = a[left];                       //将最左边的数设为基准值	
  54.     while(i != j){                           
  55. 	while(i < j && a[j] >= key)          //必须先动右边的 因为取的基准值在左边
  56. 	    j--;                             //向左寻找直到找到比基准值小的
  57. 	swap(a[i], a[j]);                    //交换
  58. 	i++;                                 //看下一个（可以省略）
  60. 	while(i < j && a[i] <= key)          //再动左边的
  61. 	    i++;                             //向右寻找直到找到比基准值大的    
  62. 	swap(a[i], a[j]);                    //交换
  63. 	j--;                                 //看下一个（可以省略）
  64. 	}  
  65. 	/* 一轮循环后基准值所在位置左边的数都比基准值小,右边的都比基准值大 */
  66.     /*   i等于j时跳出循环 当前基准值此时在下标为i的位置(合适的位置)   */                       
  67.     return i;                                //返回基准值合适位置
  68. }
  72. /*                               3                                  */
  73. //前后指针法  
  74. int Partition_PreAndCurr(vector<int> &a, int left, int right){
  75.     int pre = left;                          //pre最后找到左半部分最后一个小于基准值的元素
  76.     int curr = pre + 1;                      //curr找到pre指向元素之后的下一个小于基准值的元素
  77.     int key = a[left];
  79.     while(curr <= right){
  80. 	if(a[curr] < key && ++pre != curr)   //当a[curr]>=key时pre保持不动
  81. 	    swap(a[curr], a[pre]);           //pre往后移动到其下一个位置,并交换前后指针指向的元素
  82. 	curr++;
  83.     }
  84.     swap(a[left], a[pre]);                   //最后将基准值和此时处于pre位置的小于基准值的元素交换
  85.     return pre;
  86. }
  90. /*                               4                                  */
  91. //取基准值的优化    三数取中
  92. int GetMid(int a[], int left, int right){
  93. 	int mid = (left + right)>>1;   
  94. 	if(a[left] < a[mid])
  95. 	    if(a[mid] < a[right])
  96. 		return mid;                      //mid为中间值
  97. 	    else
  98. 		if(a[left] < a[right])
  99. 		    return right;                //right为中间值
  100. 		else
  101. 		    return left;                 //left为中间值
  102. 	else
  103. 	    if(a[mid] > a[right])
  104. 		return mid;                      //mid为中间值
  105. 	    else
  106. 		if(a[left] > a[right])
  107. 		    return right;                //right为中间值
  108. 		else
  109. 		    return left;                 //left为中间值
  110. }
  113. //左右指针法 三数取中优化
  114. int Partition_Better(vector<int> &a, int left, int right){
  115.     int pos = GetMid(a, left, right);
  116.     swap(a[pos], a[left]);                   //将取得的基准值和第一个位置交换
  118.     int i = left;
  119.     int j = right;
  120.     int key = a[left];
  121. 	
  122.     while(i != j){
  123. 	while(i < j && a[j] >= key)
  124. 	    j--;
  125. 	while(i < j && a[i] <= key)
  126. 	    i++;
  127. 	swap(a[i], a[j]);
  128.     }
  130.     swap(a[i], a[left]);
  131.     return i;
  132. }
  136. /*******************************************************************/
  137. void Quick_Sort(vector<int> &a, int left, int right){
  138.     if( left >= right )
  139. 	return;   
  141.     //int i = Partition_Hoare(a, left ,right); //分割    C(n) = n - 1
  142.     //int i = Partition_DigI(a, left, right);
  143.     //int i = Partition_DigII(a, left, right);
  144.     //int i = Partition_PreAndCurr(a, left, right);
  146.     int i = Partition_Better(a, left, right);   
  147.     Quick_Sort(a, left, i - 1);              //递归左边的部分   
  148.     Quick_Sort(a, i + 1, right);             //递归右边的部分  
  149. }  
  152. void show(vector<int> &v){
  153.     for(auto &x : v)
  154. 	cout<<x<<" ";
  155.     cout<<endl;
  156. }
  159. main(){
  160.     vector<int> v;
  161.     srand((int)time(0));
  162.     int n = 50;
  163.     while(n--)
  164. 	v.push_back(rand() % 100 + 1);
  165.     show(v);
  167.     Quick_Sort(v, 0, v.size() - 1);
  169.     cout<<endl<<endl;
  170.     show(v);
  171. }

程序运行结果图

原文链接：https://www.cnblogs.com/MAKISE004/p/16909610.html

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

C++热门文章

  • C/C++编程笔记：编写不会在C ++中编译的C程序，我教你呀！
  • 洛谷 P2085 最小函数值
  • 使用C++界面框架ImGUI开发一个简单程序
  • C++ Json解析CJsonObject的详细使用
  • C++编译错误杂记
  • 二分法（二）：采用二分法解决“最小化最大值问题”
  • C++实现json字符串与map的转换
  • C++借助curses库实现俄罗斯方块
  • 长乐培训Day5
  • 【OpenFOAM】——OpenFOAM入门算例学习

    • C++推荐文章

  • #8. 「模板」树链剖分
  • 预设型 DP
  • Standard Template Libary or C++ Standard Library
  • 一种优秀的虚拟机内存架构 - AQ
  • 如何让 MGR 不从 Primary 节点克隆数据？
  • TLScanary：Pwn中的利器
  • c++临时对象导致的生命周期问题
  • C++(Qt)-GIS开发-简易瓦片地图下载器
  • 逆向通达信 x 逆向微信 x 逆向Qt
  • C++面向对象

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号