快速排序 - お前はどこまで見えている

【注】参考自教材「算法导论」。

1. 简介

快速排序是一种被广泛运用的排序算法，虽然其最坏情况下的时间复杂度为 $O(n^2)$ ，但其平均时间复杂度为 $(n\log_2 n)$ ，而且其常数因子非常小，所以实际情况下跑的很快。快速排序是不稳定的、原址的排序算法。

【注】实际上只要保证快排的每一层枢轴左右两边的序列大小的划分比不超过某一常数比（即与序列大小 $n$ 无关），那么最终快排的时间复杂度就为 $O(n \log_2 n)$ 。

2. 思想

以从小到大排序的快速排序为例，快速排序主要思想是：

首先在序列中选定一个元素作为枢轴
然后将序列中所有小于枢轴的元素都交换到枢轴左侧，所有大于枢轴的元素都交换到枢轴右侧
接着递归处理枢轴左侧的序列和右侧的序列

其中最重要的就是实现将小于枢轴的元素交换到枢轴左侧，将大于枢轴的元素交换到枢轴右侧。

2.1 基础快排

维护两个指针，分别从序列首部和尾部往相反方向扫过去
第一个指针停在扫到的第一个大于枢轴的元素位置，然后交换两个指针指向的元素；第二个指针停在扫到的第一个小于枢轴的元素位置，然后交换两个指针指向的元素

【注】基础快排在原序列完全有序的情况下的复杂度达到 $O(n^2)$ 。

影响快排效率的因素

快排效率的高低本质上取决于 $partition$ 划分的左右两部分是否均衡。

而划分是否均衡又和最开始选取的枢轴有关，对于有序序列，固定选取第一个元素作为枢轴会导致每层递归只能将序列长度减一，从而达到最坏复杂度 $O(n^2)$ 。

对于包含大量重复元素的序列，比如某个序列全为相同的元素，则此时也会导致每层递归只能将序列长度减一，从而达到最坏复杂度 $O(n^2)$ 。其实，在当前递归中，和枢轴相同的元素本质上都可以不需要再参与下一层的递归。

快排优化方法

对于由于选取枢轴不合理导致划分不平衡的问题，可以采用随机选取序列中的元素作为枢轴的方法，也可以分别选取序列的首、中、尾三个元素然后取它们的中位数作为枢轴。

对于由于重复元素导致重复处理的问题，可以采用三路快排的思想，将序列划分为连续的三部分：小于枢轴、等于枢轴、大于枢轴的三个部分。

其他优化：当序列长度较小（ $10 \sim 15$ ）时，插入排序的效率要高于快排，所以可以截断快排的递归而改用插入排序。

2.2 随机化快排

随机选取序列中的某一个元素作为枢轴，交换到第一个元素的位置。

2.3 三数取中快排

选取序列的首、中、尾三个元素然后取它们的中位数作为枢轴，交换到第一个元素的位置。

2.4 三路快排

设待排序的序列为 $a$ ，则在三路快排的每一层递归中：

维护三个指针： $lt,p,gt$ ，使得 $[0,lt)$ 均小于枢轴， $[lt,p)$ 均等于枢轴， $(gt,n-1]$ 均大于枢轴，而 $[p,gt]$ 为仍未处理的序列。
初始化枢轴 $x$ 为序列的首元素， $lt = 0, p = lt+1, gt = n-1$ 。
判断 $a[p]$ 和枢轴 $x$ 的关系：

如果 $a[p] \lt x$ ，则 $swap(a[lt++],a[p++])$ 。

如果 $a[p] \gt x$ ，则 $swap(a[p],a[gt--])$ 。

如果 $a[p] = x$ ，则 $p++$ 。

直到 $p \geq gt$ ，则成功将序列划分为三个部分： $[0,lt)$ 均小于枢轴， $[lt,gt]$ 均等于枢轴， $(gt,n-1]$ 均大于枢轴。
然后只需要递归处理 $[0,lt)$ 和 $(gt,n-1]$ 两部分即可。

3. 模板

3.1 基础快排

原始版本

#include <bits/stdc++.h>
using namespace std;

#ifndef _QUICKSORT_
#define _QUICKSORT_
#define ll long long

// 比较函数
template <typename T>
bool compare(const T & t1, const T & t2) {
    return t1 < t2;
}
// PARTITION
template <typename T>
T* partition(T *s, T *t, bool (*cmp)(const T &, const T &)) {
    T x = *s;
    while(s < t) {
        while(s < t && !cmp(*t,x))   --t;
        swap(*s,*t);
        while(s < t && !cmp(x,*s))   ++s;
        swap(*s,*t); 
    }
    return s;
}
// 快速排序
template <typename T>
void quickSort(T *s, T *t, bool (*cmp)(const T &, const T &) = compare) {
    if(s < t) {
        T *mid = partition(s, t-1, cmp);
        quickSort(s, mid, cmp);
        quickSort(mid+1, t, cmp);
    }
}
#endif

其他版本

#include <bits/stdc++.h>
using namespace std;

#ifndef _QUICKSORT_
#define _QUICKSORT_
#define ll long long

// 比较函数
template <typename T>
bool compare(const T & t1, const T & t2) {
    return t1 < t2;
}
// PARTITION
template <typename T>
T* partition(T *s, T *t, bool (*cmp)(const T &, const T &)) {
    T *p = s;
    for(; s < t; ++s) {
        if(!cmp(*t,*s)) {
            swap(*s,*(p++));
        }
    }
    swap(*p,*t);
    return p;
}
// 快速排序
template <typename T>
void quickSort(T *s, T *t, bool (*cmp)(const T &, const T &) = compare) {
    if(s < t) {
        T *mid = partition(s, t-1, cmp);
        quickSort(s, mid, cmp);
        quickSort(mid+1, t, cmp);
    }
}
#endif

3.2 随机化版本

#include <bits/stdc++.h>
using namespace std;

#ifndef _QUICKSORT_
#define _QUICKSORT_
#define ll long long

// 比较函数
template <typename T>
bool compare(const T & t1, const T & t2) {
    return t1 < t2;
}
// PARTITION
template <typename T>
T* partition(T *s, T *t, bool (*cmp)(const T &, const T &)) {
    T *p = s + (rand()%(t-s+1));
    swap(*p,*s);
    T x = *s;
    while(s < t) {
        while(s < t && !cmp(*t,x))   --t;
        swap(*s,*t);
        while(s < t && !cmp(x,*s))   ++s;
        swap(*s,*t); 
    }
    return s;
}
// 快速排序（递归子过程）
template <typename T>
void QuickSort(T *s, T *t, bool (*cmp)(const T &, const T &)) {
    if(s < t) {
        T *mid = partition(s, t-1, cmp);
        QuickSort(s, mid, cmp);
        QuickSort(mid+1, t, cmp);
    }
}
// 快速排序（随机化版本）
template <typename T>
void quickSort(T *s, T *t, bool (*cmp)(const T &, const T &) = compare) {
    srand(time(NULL));
    QuickSort(s, t, cmp);
}
#endif

3.3 三数取中快排

#include <bits/stdc++.h>
using namespace std;

#ifndef _QUICKSORT_
#define _QUICKSORT_
#define ll long long

// 比较函数
template <typename T>
bool compare(const T & t1, const T & t2) {
    return t1 < t2;
}
// PARTITION
template <typename T>
T* partition(T *s, T *t, bool (*cmp)(const T &, const T &)) {
    if(s < t) {
        T *mid = s + (t-s)/2;
        if(cmp(*t,*s)) {
            swap(*t,*s);
        }
        if(cmp(*mid,*s)) {
            swap(*mid,*s);
        }
        if(cmp(*t,*mid)) {
            swap(*mid,*t);
        }
        swap(*mid,*s);
    }
    T x = *s;
    while(s < t) {
        while(s < t && !cmp(*t,x))   --t;
        swap(*s,*t);
        while(s < t && !cmp(x,*s))   ++s;
        swap(*s,*t); 
    }
    return s;
}
// 快速排序
template <typename T>
void quickSort(T *s, T *t, bool (*cmp)(const T &, const T &) = compare) {
    if(s < t) {
        T *mid = partition(s, t-1, cmp);
        quickSort(s, mid, cmp);
        quickSort(mid+1, t, cmp);
    }
}
#endif

3.4 三路快排

#include <bits/stdc++.h>
using namespace std;

#ifndef _QUICKSORT_
#define _QUICKSORT_
#define ll long long

// 比较函数
template <typename T>
bool compare(const T & t1, const T & t2) {
    return t1 < t2;
}
// 快速排序
template <typename T>
void quickSort(T *s, T *t, bool (*cmp)(const T &, const T &) = compare) {
    if(s < t-1) {
        T *p = s + 1;
        T *lt = s, *gt = t-1;
        T x = *s;
        while(p <= gt) {
            if(cmp(*p,x)) {
                swap(*(lt++),*(p++));
            } else if(cmp(x,*p)) {
                swap(*(gt--),*p);
            } else {
                p++;
            }
        }
        quickSort(s, lt, cmp);
        quickSort(gt+1, t, cmp);
    }
}
#endif

3.5 随机化 + 三路快排

#include <bits/stdc++.h>
using namespace std;

#ifndef _QUICKSORT_
#define _QUICKSORT_
#define ll long long

// 比较函数
template <typename T>
bool compare(const T & t1, const T & t2) {
    return t1 < t2;
}
// 快速排序
template <typename T>
void QuickSort(T *s, T *t, bool (*cmp)(const T &, const T &)) {
    if(s < t-1) {
        // 随机化
        swap(*(s + (rand()%(t-s))),*s);
        // 三路快排
        T *p = s + 1;
        T *lt = s, *gt = t-1;
        T x = *s;
        while(p <= gt) {
            if(cmp(*p,x)) {
                swap(*(lt++),*(p++));
            } else if(cmp(x,*p)) {
                swap(*(gt--),*p);
            } else {
                p++;
            }
        }
        QuickSort(s, lt, cmp);
        QuickSort(gt+1, t, cmp);
    }
}
// 快速排序（随机化版本）
template <typename T>
void quickSort(T *s, T *t, bool (*cmp)(const T &, const T &) = compare) {
    srand(time(NULL));
    QuickSort(s, t, cmp);
}
#endif

3.6 三数取中 + 三路快排

#include <bits/stdc++.h>
using namespace std;

#ifndef _QUICKSORT_
#define _QUICKSORT_
#define ll long long

// 比较函数
template <typename T>
bool compare(const T & t1, const T & t2) {
    return t1 < t2;
}
// 快速排序
template <typename T>
void quickSort(T *s, T *t, bool (*cmp)(const T &, const T &) = compare) {
    if(s < t-1) {
        // 三数取中
        T *mid = s + (t-1-s)/2;
        if(cmp(*(t-1),*s)) {
            swap(*(t-1),*s);
        }
        if(cmp(*mid,*s)) {
            swap(*mid,*s);
        }
        if(cmp(*(t-1),*mid)) {
            swap(*mid,*(t-1));
        }
        swap(*mid,*s);
        // 三路快排
        T *p = s + 1;
        T *lt = s, *gt = t-1;
        T x = *s;
        while(p <= gt) {
            if(cmp(*p,x)) {
                swap(*(lt++),*(p++));
            } else if(cmp(x,*p)) {
                swap(*(gt--),*p);
            } else {
                p++;
            }
        }
        quickSort(s, lt, cmp);
        quickSort(gt+1, t, cmp);
    }
}
#endif

3.7 随机化 + 三路快排 + 插入排序截断

#include <bits/stdc++.h>
using namespace std;

#ifndef _QUICKSORT_
#define _QUICKSORT_
#define ll long long
#define _M_ 10

// 比较函数
template <typename T>
bool compare(const T & t1, const T & t2) {
    return t1 < t2;
}
// 插入排序
template <typename T>
void insertSort(T *s, T *t, bool (*cmp)(const T &, const T &)) {
    T *p, *q;
    for(p = s+1; p < t; ++p) {
        T t = *p;
        for(q = p-1; q >= s && cmp(*p,*q); --q) {
            *(q+1) = *q;
        }
        *(q+1) = t;
    }
}
// 快速排序
template <typename T>
void QuickSort(T *s, T *t, bool (*cmp)(const T &, const T &)) {
    if(s < t-_M_) {
        // 随机化
        swap(*(s + (rand()%(t-s))),*s);
        // 三路快排
        T *p = s + 1;
        T *lt = s, *gt = t-1;
        T x = *s;
        while(p <= gt) {
            if(cmp(*p,x)) {
                swap(*(lt++),*(p++));
            } else if(cmp(x,*p)) {
                swap(*(gt--),*p);
            } else {
                p++;
            }
        }
        QuickSort(s, lt, cmp);
        QuickSort(gt+1, t, cmp);
    } else {
        // 插入排序截断
        insertSort(s, t, cmp);
    }
}
// 快速排序（随机化版本）
template <typename T>
void quickSort(T *s, T *t, bool (*cmp)(const T &, const T &) = compare) {
    srand(time(NULL));
    QuickSort(s, t, cmp);
}
#endif

3.8 随机化 + 三数取中 + 三路快排 + 插入排序截断

#include <bits/stdc++.h>
using namespace std;

#ifndef _QUICKSORT_
#define _QUICKSORT_
#define ll long long
#define _M_ 12

// 比较函数
template <typename T>
bool compare(const T & t1, const T & t2) {
    return t1 < t2;
}
// 插入排序
template <typename T>
void insertSort(T *s, T *t, bool (*cmp)(const T &, const T &)) {
    T *p, *q;
    for(p = s+1; p < t; ++p) {
        T t = *p;
        for(q = p-1; q >= s && cmp(*p,*q); --q) {
            *(q+1) = *q;
        }
        *(q+1) = t;
    }
}
// 快速排序
template <typename T>
void QuickSort(T *s, T *t, bool (*cmp)(const T &, const T &)) {
    if(s < t-_M_) {
        // 随机化 + 三数取中
        T *x = s + (rand()%(t-s));
        T *y = s + (rand()%(t-s));
        T *z = s + (rand()%(t-s));
        if(cmp(*z,*x)) {
            swap(*x,*z);
        }
        if(cmp(*y,*x)) {
            swap(*x,*y);
        } 
        if(cmp(*z,*y)) {
            swap(*y,*z);
        }
        swap(*y,*s);
        // 三路快排
        T *p = s + 1;
        T *lt = s, *gt = t-1;
        T pivot = *s;
        while(p <= gt) {
            if(cmp(*p,pivot)) {
                swap(*(lt++),*(p++));
            } else if(cmp(pivot,*p)) {
                swap(*(gt--),*p);
            } else {
                p++;
            }
        }
        QuickSort(s, lt, cmp);
        QuickSort(gt+1, t, cmp);
    } else {
        // 插入排序截断
        insertSort(s, t, cmp);
    }
}
// 快速排序（随机化版本）
template <typename T>
void quickSort(T *s, T *t, bool (*cmp)(const T &, const T &) = compare) {
    srand(time(NULL));
    QuickSort(s, t, cmp);
}
#endif

Technique ACM 算法排序

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

算法时间复杂度上一篇

快速排序下一篇