简介

快速排序算法是对冒泡排序算法的一种改进。平均时间复杂度$O(nlogn)$，最坏时间复杂度$O(n^2)$。

快速排序的基本思想：每趟排序选择一个基准值pivot，使得小于pivot的元素和大于pivot的元素分隔于pivot两侧，即每一趟确定了一个元素的位置。然后对基准值两侧的区间进行递归，以达到整个序列有序。

可以看出时间复杂度与递归的层数相关，提升效率的关键就在于partition，划分时的实现。

单路快排

最基础的实现版本，前后双指针法：

 1// 对左闭右开区间a[l, r)，单路快排，前后双指针法
 2void quickSort(int *a, int l, int r){
 3    if(l>=r) return;
 4
 5    int pivot = a[l];
 6    int j = l;
 7    for(int i=l+1; i<r; i++){
 8        if(a[i] < pivot)
 9            swap(a[++j], a[i]);
10    }
11    swap(a[l], a[j]);
12
13    quickSort(a, l, j);
14    quickSort(a, j+1, r);
15}

这种方法有许多缺陷，但胜在简短，而且简单修改就可以变成链表版本：

 1// 单链表采用直接交换数据区，修改指针的话没什么好想法
 2void quickSort(ListNode *head, ListNode *last){
 3    if(head==nullptr || head==last) return;
 4
 5    int pivot = head->val;
 6    ListNode *pre = head;
 7    for(ListNode *cur=head; cur->next!=last; cur=cur->next){
 8        if(cur->next->val < pivot){
 9            swap(cur->next->val, pre->next->val);
10            pre = pre->next;
11        }
12    }
13    swap(head->val, pre->val);
14
15    quickSort(head, pre);
16    quickSort(pre->next, last);
17}

双路快排

单路快排会使得与基准值pivot相等的元素总是归为一侧，存在大量相同元素时，时间复杂度退化为$ O(n^2) $。左右双指针法可以让与基准值相等的元素随机交换至两侧，但是还需处理。

 1// 左闭右开区间a[l, r)，双路快排，左右双指针法
 2void quickSort(int *a, int l, int r){
 3    if(l>=r) return;
 4
 5    int pivot = a[l];
 6    int i=l+1, j=r-1;
 7    while(i<=j){
 8        while(a[i]<pivot && i<r) i++;
 9        while(a[j]>pivot && j>l) j--;
10        if(i>j) break;
11        swap(a[i++], a[j--]);
12    }
13    swap(a[l], a[j]);
14
15    quickSort(a, l, j);
16    quickSort(a, j+1, r);
17}

三路快排

要真正优化存在大量相同元素情况下快排的效率时，还是需要使用三路快排，将序列分为小于pivot的 $ [l, lt) $ ， 等于pivot的 $ [lt, i] $ ， 大于pivot的 $ [rt, r) $ 三部分。

 1// 左闭右开区间a[l, r)，三路快排
 2void quickSort(int *a, int l, int r){
 3    if(l>=r) return;
 4
 5    int pivot = a[l];
 6    int lt = l, rt = r;
 7    for(int i=l+1; i<rt; ){
 8        if(a[i] < pivot)
 9            swap(a[i++], a[++lt]);
10        else if(a[i] > pivot)
11            swap(a[i], a[--rt]);
12        else
13            i++;
14    }
15    swap(a[l], a[lt]);
16
17    quickSort(a, l, lt);
18    quickSort(a, rt, r);
19}

更多优化

更多优化就可以参考STL::sort()函数的实现。例如，

在基准值pivot的选取中，如果每次选取的恰好是当前序列中的最大或最小元素，划分的结果是最坏情况，递归层数大大上升。对此，我们可以使用随机选取或者三数取中法。

1// 左闭右开区间a[l, r)，随机选取
2srand(time(NULL));
3int pivot = a[rand()%(r-l)+l];
4
5// 左闭右开区间a[l, r)，三数取中法
6int pivot = a[l + (r-l)/2];
7if(pivot<a[l] && pivot<a[r]) pivot=min(a[l], a[r]);
8if(pivot>a[l] && pivot>a[r]) pivot=max(a[l], a[r]);

当序列较短时(<16)，可以采用直接插入排序，减少递归深度。

1// 还需要具体实现
2if(r-l < 16){
3    insertionSort(a, l, r);
4    return;
5}

当递归次数大于限制时，采用堆排序等。

代码

测试代码：

  1#include <bits/stdc++.h>
  2using namespace std;
  3
  4void showArray(int *a, int n){
  5    for(int i=0; i<n; i++){
  6        printf("%d ", a[i]);
  7    }
  8    printf("\n");
  9}
 10
 11// 单路快排，前后双指针法
 12void quickSort(int *a, int l, int r){
 13    if(l>=r) return;
 14
 15    int pivot = a[l];
 16    int j = l;
 17    for(int i=l+1; i<r; i++){
 18        if(a[i] < pivot)
 19            swap(a[++j], a[i]);
 20    }
 21    swap(a[l], a[j]);
 22
 23    quickSort(a, l, j);
 24    quickSort(a, j+1, r);
 25}
 26
 27// 双路快排，左右双指针法
 28void quickSort(int *a, int l, int r){
 29    if(l>=r) return;
 30
 31    int pivot = a[l];
 32    int i=l+1, j=r-1;
 33    while(i<=j){
 34        while(a[i]<pivot && i<r) i++;
 35        while(a[j]>pivot && j>l) j--;
 36        if(i>j) break;
 37        swap(a[i++], a[j--]);
 38    }
 39    swap(a[l], a[j]);
 40
 41    quickSort(a, l, j);
 42    quickSort(a, j+1, r);
 43}
 44
 45// 三路快排
 46void quickSort(int *a, int l, int r){
 47    if(l>=r) return;
 48
 49    int pivot = a[l];
 50    int lt = l, rt = r;
 51    for(int i=l+1; i<rt; ){
 52        if(a[i] < pivot)
 53            swap(a[i++], a[++lt]);
 54        else if(a[i] > pivot)
 55            swap(a[i], a[--rt]);
 56        else
 57            i++;
 58    }
 59    swap(a[l], a[lt]);
 60
 61    quickSort(a, l, lt);
 62    quickSort(a, rt, r);
 63}
 64
 65struct ListNode {
 66    int val;
 67    ListNode *next;
 68    ListNode(int x) : val(x), next(NULL) {}
 69};
 70
 71void showList(ListNode *head){
 72    ListNode *p = head;
 73    while(p!=nullptr){
 74        printf("%d ", p->val);
 75        p = p->next;
 76    }
 77    printf("\n");
 78}
 79
 80// 链表快排
 81void quickSort(ListNode *head, ListNode *last){
 82    if(head==nullptr || head==last) return;
 83
 84    int pivot = head->val;
 85    ListNode *pre = head;
 86    for(ListNode *cur=head; cur->next!=last; cur=cur->next){
 87        if(cur->next->val < pivot){
 88            swap(cur->next->val, pre->next->val);
 89            pre = pre->next;
 90        }
 91    }
 92    swap(head->val, pre->val);
 93
 94    quickSort(head, pre);
 95    quickSort(pre->next, last);
 96}
 97
 98int main()
 99{
100    int n = 10;
101    int a[11] = {4,1,7,6,9,2,8,0,3,5};
102
103    ListNode *h[10];
104    for(int i=0; i<n; i++){
105        h[i] = new ListNode(a[i]);
106        if(i) h[i-1]->next = h[i];
107    }
108    ListNode *head = h[0];
109
110    showArray(a, n);
111    quickSort(a, 0, n);
112    showArray(a, n);
113
114    showList(head);
115    quickSort(head, nullptr);
116    showList(head);
117
118    return 0;
119}