快速排序 C++

本文图示借鉴自清华大学邓俊辉老师数据结构课程。

快速排序是分治思想的典型应用。该排序算法可以原地实现，即空间复杂度为 O ( 1 ) O(1) O(1)，而时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn) 。

算法将待排序的序列 S S S 分为两个子序列 S L S_L SL​ 和 S R S_R SR​ ，随着这种子序列的划分，可以保证问题的规模在不断缩小，即有：
m a x ( ∣ S L ∣ , ∣ S R ∣ ) < n max(|S_L|,|S_R|) < n max(∣SL​∣,∣SR​∣) 并要求左侧子序列 S L S_L SL​ 中的最大值不大于右侧子序列 S R S_R SR​ 中的最小值，即有：
m a x ( S L ) ≤ m i n ( S R ) max(S_L)le min(S_R) max(SL​)≤min(SR​)
这样在递归地再对子序列进行划分之后，原序列自然有序。递归的终止条件为划分子序列的平凡情况，即子序列的规模为1。

我们将划分两个子序列的点成为 pivot（轴点） ，在轴点左侧的元素，均不比它更大；在轴点右侧的元素，均不比它更小。轴点的位置，即为该元素在最终排序完成的序列中的位置。

即将原序列按如下划分：
[   l , r   ) = [   l , p i v o t   ) + p i v o t + (   p i v o t , r   ] [ l, r )=[ l, pivot )+pivot+( pivot,r ] [ l,r )=[ l,pivot )+pivot+( pivot,r ]
但是对于待排序的序列，我们并不知道谁是轴点，甚至，有可能原序列中所有元素都不是轴点，比如将一个已排序的序列循环右移一位，则此时所有元素都不在自己的排序位置上，都不是轴点。

好在我们可以通过对待排序的序列的元素进行移动交换，从而使得某个元素成为轴点，在递归之后，所有元素都成为轴点，这时所有元素都位于自己的排序位置上，整个排序算法完成。

可以看到，整个算法的框架是递归地选取轴点并划分子序列，究竟怎样划分，怎样划分效率更高，是快排算法的关键之处。

我们先给出整个快排算法的递归框架，其中关键的 partition 划分函数我们会在后面详细介绍，整体框架是一个递归函数：

void quickSort(vector& vec, int l, int r) {
  if (l 
当 l 不小于 r 时，即 l 已经等于 r，此时即为递归退出的平凡情况：子序列只有一个元素。在此之前，我们都需要不断地执行 if 语句中的内容：得到传入序列的一个轴点，并分别递归地处理该轴点两侧的子序列。
 
最终当传入的子序列规模为1是，即 l 
partition 
版本1 
接下来我们来介绍最为关键的 partition 函数。
 
 
我们先任选一个元素作为轴点的 “培养对象” 并备份，在我们划分完毕之后，该元素可以 “名正言顺” 地位于自己应该处于的最终排序位置，不妨就取序列的最左端元素。
 
然后将两个指针分别放在整个序列的左右两端，分别向中间靠拢。
 
我们将
 
未确定区域称为 
     
      
       
        
         U
        
       
       
        U
       
      
     U （图中粉色部分），初始为全集
确定大于轴点的部分称为 
     
      
       
        
         G
        
       
       
        G
       
      
     G （图中蓝色部分），初始为空集
确定小于轴点的部分称为 
     
      
       
        
         L
        
       
       
        L
       
      
     L （图中绿色部分），初始为空集
 
交替地将左右两端的指针向中间移动，分别检查移动时当前元素与轴点 pivot 的大小关系，若小于轴点，则归入 
    
     
      
       
        L
       
      
      
       L
      
     
    L；若大于轴点，则归入 
    
     
      
       
        R
       
      
      
       R
      
     
    R 。
 
当左右两指针相等时，该位置即为我们的 “培养对象” 轴点应该处于的排序位置，将备份的轴点放入该位置即可。最后同样返回轴点位置。
 
整个过程中，左右指针所指的位置交替空闲。所谓空闲即是指其中元素可以被覆盖。一开始时，我们将 ”培养对象“ 备份，故其位置是 “空闲” 的，在随后的交还过程中，左右指针总有一个所指的位置是空闲的。
 
 
可以参考上图，图中紫色部分即为 “空闲” 的。红色的 lo、hi 分别对应我们描述中的左右指针。
 
代码实现如下：
 
int partition(vector& vec, int l, int r) {
    int pivot = vec[l];
    while(l < r) {
        while (l=vec[l]) l++;
        swap(vec[r], vec[l]);
    }
    vec[l] = pivot;
    return l;
}
 
版本2 
对于 partition 函数，还有一种实现的方式，可以称为 LGU 的方式，在这种方式中，L 仍旧排在原序列的最左端，而中间是 G ，最右端是 U。
 
 
同样可以选取最左端的元素作为 pivot 。
 
然后一根指针从序列的最左端遍历到最右端，分别判断每个当前元素与 pivot 的关系，并分别划分到 L 或 G 中。
 
如果是划分到 G 中，直接将 k++ 即可；而如果是划分到 L 中，则需要将 G 滚动后移一个元素，并将当前元素交换到 L 的末尾。
 
代码实现如下：
 
int partition(vector& vec, int l, int r) {
    int m = l, pivot = vec[l];
    for (int k=l+1; k<=r; k++) {
        if (pivot > vec[k])
            swap(vec[++m], vec[k]);
    }
    swap(vec[l], vec[m]);
    return m;
}
 
这里中间判断中的 if 分支是判断当前元素小于轴点 pivot ，需要将当前元素加入到 L 中，将当前元素 vec[k] 与 L 的最后一个元素 vec[++m] 互换，然后k++；而它对应的 else 分支，即当前元素小于轴点 pivot，需要将当前元素加入到 G 中，此时只需将 k++。两个分支都需要 k++，直接放在循环变量的更新中。
 
最后同样返回轴点位置。