C++入门：排序（二）之快速排序

vlambda
2020-06-12

C++入门：排序（二）之快速排序

人生会经历N多的选择和循环，你设定的每一个条件都可能影响你人生的走向，甚至死循环，人生规划如同设计算法，算法的好坏将直接影响你人生的质量。

学编程算法、数据结构最重要，他们是各种语言，编程工具的基础，学扎实了至于用哪种语言看资源，有什么资源用什么资源，不必争论哪种语言更牛掰。

然而研究算法是枯燥的，但就和你练功一样，先练基本功，先扎马步，马步稳了，基本功扎实了，还怕不会码代码？

算法分析简介

对于一个给定的算法，通常我们要做几项分析。第一是从数学上证明算法的正确性，第二部就是分析算法的时间复杂度和空间复杂度，通过形式化证明的方法及相关推理模式证明算法的正确性和分析算法的优劣与否。

正确与否直接关系到算法的成立，时间复杂度则反映当数据量变化时，操作次数的多少，空间复杂度则指算法在计算机内执行时，所需额外开辟的空间。

还有一个稳定性问题，对于排序如果a原本在b前面，而a=b，排序之后a仍然在b的前面就是稳定的，如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面就是不稳定的。

对于常见的排序算法时间复杂度、空间复杂度以及稳定性见下表，指标含义后期慢慢解释。

排序算法可以说是一项基本功，解决实际问题中经常遇到，针对实际数据的特点选择合适的排序算法可以使程序获得更高的效率，有时候排序的稳定性还是实际问题中必须考虑的。

分治(Divide-and-Conquer)

学习快速排序前先熟悉一个词“分治”，分治的策略把一个序列（list）分为两个子序列（sub-lists），说白了就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

在计算机科学中，分治法就是运用分治思想的一种很重要的算法。分治法是很多高效算法的基础，在排序算法中常见的就是快速排序和归并排序。

分治从字面看一是divide，一是conquer，其实可以看做三个步骤：分、治、合。归并排序先将数组不断细分成最小的单位，然后每个单位分别排序，排序完毕后合并。快速排序是先选定一个基准元素，然后以该基准元素划分数组，再在被划分的部分重复以上过程，最后可以得到排序结果。都是利用分治的思想，代码都通过递归来实现，过程非常相似。

归并排序中元素位置变化只发生在向上合成阶段，由于合并是依次比较，没有破坏之前元素的相对位置，所以为稳定排序。而快速排序在最后交换基准元的步骤中，可能会破坏相同元素之间的相对位置，所以为不稳定排序算法。

前面已经介绍过，对于基础类型，因为相同值没有差别，排序前后相同值的相对位置并不重要，可以选择更为高效的快速排序；而对于非基础类型，排序前后相等实例的相对位置如果改变可能造成很多问题，所以需要选择稳定的排序方式。

快速排序（Quick Sort）

快速排序，又称划分交换排序（partition-exchange sort），是常用的排序算法之一，是C.R.A.Hoare于1962年提出的，它基于分治的思想，是冒泡排序的改进型。同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。

不同的是，冒泡排序在每一轮只把一个元素冒泡到数列的一端，而快速排序在每一轮挑选一个基准元素，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

从数列中挑出一个元素，称为 “基准”（pivot），

重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

左右指针法

快速排序算法常见有左右指针法、挖坑法、前后指针法等方法，上面模拟的是左右指针法。

表述一下上面的过程：

假设我们现在对上面“35 33 42 10 14 19 27 44 26 31”这个5个数进行排序。首先在这个序列中随便找一个数作为基准数（不要被这个名词吓到了，就是一个用来参照的数），这里可以随机选取一个数，习惯上会选第一个或最后一个数作为基准数。这里我们选择最后一个数31。

第一步：我们从数组的right位置取出该数（31）作为基准（pivot）。(如果是选取随机的，则找到随机的数之后，将它与第一个元素交换，开始普通的快排)

第二步：从数组的left位置向后找，一直找到比（pivot）大的数，从数组的right下一个位置向前找，一直找到比（pivot）小的数，如果找到，将此数位置对调，此时数组为：26 33 42 10 14 19 27 44 35 31。

第三步：重复上面的操作，直到left和right指针重合，最后将（pivot）与当前指针的数交换，此时数组值为：26 27 19 10 14 31 33 44 35 42至此完成一次排序。

这个时候31（pivot）左右被分成两部分（注：这种情况时，left指针和right指针显然是重合的。因此在代码中，我们可以通过设置判定条件left必须小于right，如果不满足，则不用排序了）。然后分别对新的数组重复前面步骤进行排序。

下面看代码，再进一步理解过程：

#include <iostream>using namespace std;void quicksort(int a[],int left, int right){ int i,j,t,temp;  // 结束排序（左右两索引值见面，即相等，或者左索引>右索引） if(left>right)  return;  temp=a[right]; //temp中存的就是基准数  i=left;  j=right;  while(i!=j) {  //先找左边的  while(a[i]<=temp && i<j)  i++;  //再从右边开始找  while(a[j]>=temp && i<j)  j--;
 //交换两个数在数组中的位置  if(i<j) {  t=a[i];  a[i]=a[j];  a[j]=t;  }  }  //最终将基准数归位  a[right]=a[i];  a[i]=temp;  //下面分别递归处理  quicksort(a,left,i-1);//继续处理左边的，这里是一个递归的过程  quicksort(a,i+1,right);//继续处理右边的 ，这里是一个递归的过程 } int main(){ int a[] = {35,33,42,10,14,19,27,44,26,31}; quicksort(a, 0, sizeof(a) / sizeof(a[0]) - 1); //输出  for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++){ cout << a[i] << " "; } return 0;}

挖坑法

定义两个指针left指向起始位置，right指向最后一个元素的位置,然后指定一个基数 pivot （left）,作为坑。

left寻找比基数（pivot）大的数字，找到后将left的数据赋给right，left成为一个坑，然后right寻找比基数（pivot）小的数字，找到将right的数据赋给left，right成为一个新坑，循环这个过程，直到begin指针与end指针相遇，然后将pivot返回给那个坑（最终：pivot的左边都是比pivot小的数，pivot的右边都是比pivot大的数），然后进行递归操作。

#include <iostream>using namespace std;void quicksort(int a[],int left, int right){ int i,j,temp;  if(left>right)  return;  temp=a[left]; //temp中存的就是基准数  i=left;  j=right;  while(i<j) {  //先找左边的  while(a[j]>=temp && i<j)  j--;  if(i<j) { a[i]=a[j]; i++; //继续向后     } //再从右边开始找  while(a[i]<temp && i<j)  i++;  if(i<j) { a[j]=a[i]; j--; //继续向前     } }  //最终将基准数归位  a[i]=temp;  //下面分别递归处理  quicksort(a,left,i-1);//继续处理左边的，这里是一个递归的过程  quicksort(a,i+1,right);//继续处理右边的 ，这里是一个递归的过程 }  
int main(){ int a[] = {35,33,42,10,14,19,27,44,26,31}; quicksort(a, 0, sizeof(a) / sizeof(a[0]) - 1); //输出  for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++){ cout << a[i] << " "; } return 0;}

前后指针法

基本思路是定义两个指针，一前一后，cur（前）指向起始位置，prev（后）指向cur的前一个位置；选择数组最后一个元素作为key（right）

实现过程：cur找比key小的数，prev在cur没有找到的情况下，一直不动（即保证prev一直指向比key大的数）；直到cur找到比key小的数（+ +prev && prev != cur时）然后++cur,prev仍然不动。

直到cur走到right前一个位置，终止循环。最后++prev，交换prev和right的值。返回中间位置prev。最后再继续递归。

#include <iostream>using namespace std;void quicksort(int a[],int left, int right){ if(left>right)  return;  int cur = left;//cur指向序列的第一个元素 int prev = left - 1;//prev指向的是cur前边的一个元素 int key = a[right];//选择数组最后一个元素作为key（right） while (cur <= right){ if (a[cur] <= key){ prev++; if (prev != cur){ int temp = a[cur]; a[cur] = a[prev];        a[prev] = temp; //中间位置 } } cur++; } //下面分别递归处理  quicksort(a,left,prev-1);//继续处理左边的，这里是一个递归的过程  quicksort(a,prev+1,right);//继续处理右边的 ，这里是一个递归的过程 } 
int main(){ int a[] = {35,33,42,10,14,19,27,44,26,31}; quicksort(a, 0, sizeof(a) / sizeof(a[0]) - 1); //输出  for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++){ cout << a[i] << " "; } return 0;}