[算法] 快速排序（单路、双路、三路）

思路

从数组中选择一个元素（如第一个元素），把它放到正确的位置上
对它前后两部分的数组不断重复这个过程，最终得到的数组就是有序的

实现

创建三个指针，l 指向第一个元素v，i 指向当前元素e，j 指向 <v 和 >v 的分界点
i 遍历到最后，交换 l 和 j ，整个数组分成 <v 和 >v 两部分
对 j 前后两部分的数组重复以上过程

代码

单路

 1 # include <iostream>
 2 # include <ctime>
 3 # include <algorithm>
 4 # include "InsertionSort.h"
 5 
 6 //对arr[l...r]部分进行partition操作
 7 // 返回p,使arr[l...p-1] < arr[p]; arr[p+1...r] > arr[p] 
 8 template <typename T>
 9 int __partition(T arr[], int l, int r){
10     // 随机选用一个元素作为标定（避免有序时退化为O(n^2)) 
11     swap( arr[l] , arr[rand()%(r-l+1)+l] );
12     T v = arr[l];
13     //arr[l+1...j] < v ; arr[j+1...i) > v
14     int j = l;
15     // 对整个数组遍历 
16     for( int i = l + 1; i <= r; i++ ){
17         //右侧 > v, 左侧 < v 
18         if(arr[i] < v){
19             swap( arr[j+1], arr[i] );
20             j ++;
21         }
22     }
23     // 把v放到中间 
24     swap( arr[l] , arr[j]);
25     return j;
26 }
27 
28 template <typename T>
29 void __quickSort(T arr[], int l ,int r){
30     if( l >= r)
31         return;
32     
33     int p = __partition(arr, l, r);
34     __quickSort(arr, l, p-1);
35     __quickSort(arr, p+1, r);
36 }
37 
38 template <typename T>
39 void quickSort(T arr[], int n){
40     srand(time(NULL));
41     __quickSort(arr, 0, n-1);
42 }

双路

 1 template <typename T>
 2 int __partition2(T arr[], int l, int r){
 3     swap( arr[l] , arr[rand()%(r-l+1)+l] );
 4     T v = arr[l];
 5     // 对整个数组扫描，保持如下性质 
 6     // arr[l+1...i) <= v; arr(j...r] >= v
 7     int i = l+1,j = r;
 8     while(true){
 9         while( i <= r && arr[i] < v ) i ++;
10         while( j >= l + 1 && arr[j] > v ) j --;
11         if( i > j ) break;
12         swap( arr[i] , arr[j] );
13         i ++;
14         j --;
15     }
16     swap( arr[l] , arr[j] );
17     return j;
18 }
19 
20 template <typename T>
21 void __quickSort2(T arr[], int l ,int r){
22     if( r - l <= 15 ){
23         insertionSort(arr,l,r);
24         return;
25     }     
26         
27     int p = __partition2(arr, l, r);
28     __quickSort2(arr, l, p-1);
29     __quickSort2(arr, p+1, r);
30 }
31 
32 template <typename T>
33 void quickSort2(T arr[], int n){
34     srand(time(NULL));
35     __quickSort2(arr, 0, n-1);
36 }

三路

 1 // 三路快速排序处理 arr[l...r]
 2 // 将arr[l...r]分为 <v ; ==v ; >v 三部分
 3 // 之后递归对 <v ; >v 两部分继续进行三路快速排序 
 4 template <typename T>
 5 void __quickSort3(T arr[], int l, int r){
 6     if(r - l <= 15){
 7         insertionSort(arr,l,r);
 8         return;
 9     }
10     
11     swap(arr[l], arr[rand()%(r-l+1)+l]);
12     
13     T v = arr[l];    // 取最左侧数据为标定 
14     
15     int lt = l;        // arr[l+1...lt] < v
16     int gt = r + 1;    // arr[gt...r] > v
17     int i = l + 1;    // arr[lt+1...i) == v
18     while( i < gt ){
19         if(arr[i] < v ){
20             swap( arr[i], arr[lt+1]);
21             i ++;        //i指向已处理元素，需处理 
22             lt ++;
23         }
24         else if( arr[i] > v){
25             swap( arr[i], arr[gt-1]);
26             gt --;        // i指向未处理元素，不用处理 
27         }
28         else{    // arr[i] == v
29             i ++;
30         }
31     }
32     
33     swap( arr[l] , arr[lt] );
34     
35     __quickSort3(arr, l, lt-1);
36     __quickSort3(arr, gt, r);
37 
38 }
39 
40 template <typename T>
41 void quickSort3(T arr[], int n){
42     srand(time(NULL));
43     __quickSort3(arr, 0, n-1);
44 }

应用

在O(n)内查找第k大元素

总结

非常快
原地排序，这点要好于递归
归并和快排都使用了分治算法
二者相比，归并的难点在于“合”，快排的难点在于“分”
树的实现也使用了分治思想