快速排序

本页面将简要介绍快速排序．

定义

快速排序（Quicksort），又称分区交换排序（partition-exchange sort），简称「快排」，是一种被广泛运用的排序算法．

基本原理与实现

过程

快速排序的工作原理是通过分治的方式来将一个数组排序．

快速排序分为三个过程：

将数列划分为两部分（要求保证相对大小关系）；
递归到两个子序列中分别进行快速排序；
不用合并，因为此时数列已经完全有序．

和归并排序不同，第一步并不是直接分成前后两个序列，而是在分的过程中要保证相对大小关系．具体来说，第一步是要把数列分成两个部分，然后保证前一个子数列中的数都不大于后一个子数列中的数．为了保证平均时间复杂度，一般是随机选择一个数 \(m\) 来当做两个子数列的分界．

之后，维护一前一后两个指针 \(p\) 和 \(q\)，依次考虑当前的数是否放在了应该放的位置（前还是后）．如果当前的数没放对，比如说如果后面的指针 \(q\) 遇到了一个比 \(m\) 小的数，那么可以交换 \(p\) 和 \(q\) 位置上的数，再把 \(p\) 向后移一位．当前的数的位置全放对后，再移动指针继续处理，直到两个指针相遇．

其实，快速排序没有指定应如何具体实现第一步，不论是选择 \(m\) 的过程还是划分的过程，都有不止一种实现方法．

第三步中的序列已经分别有序且第一个序列中的数都不大于第二个序列中的数，所以直接拼接起来就好了．

以下是固定选取主元的基础实现：非递归 C++ 实现选取当前子数组的末元素，递归 C++ 实现和 Python 实现选取首元素．它们没有随机化选取主元，在有序输入等情况下可能退化为 \(O(n^2)\)．

C++Python⁵

非递归实现⁵递归实现

struct Range {
  int start, end;

  Range(int s = 0, int e = 0) { start = s, end = e; }
};

template <typename T>
void quick_sort(T arr[], const int len) {
  if (len <= 0) return;
  vector<Range> r(len);
  int p = 0;
  r[p++] = Range(0, len - 1);
  while (p) {
    Range range = r[--p];
    if (range.start >= range.end) continue;
    T mid = arr[range.end];
    int left = range.start, right = range.end - 1;
    while (left < right) {
      while (arr[left] < mid && left < right) left++;
      while (arr[right] >= mid && left < right) right--;
      std::swap(arr[left], arr[right]);
    }
    if (arr[left] >= arr[range.end])
      std::swap(arr[left], arr[range.end]);
    else
      left++;
    r[p++] = Range(range.start, left - 1);
    r[p++] = Range(left + 1, range.end);
  }
}

template <typename T>
int partition(T A[], int low, int high) {
  T pivot = A[low];
  while (low < high) {
    while (low < high && pivot <= A[high]) --high;
    A[low] = A[high];
    while (low < high && A[low] <= pivot) ++low;
    A[high] = A[low];
  }
  A[low] = pivot;
  return low;
}

template <typename T>
void quickSort(T A[], int low, int high) {
  if (low < high) {
    int pivot = partition(A, low, high);
    quickSort(A, low, pivot - 1);
    quickSort(A, pivot + 1, high);
  }
}

template <typename T>
void quickSort(T A[], int len) {
  quickSort(A, 0, len - 1);
}

def quick_sort(alist, first, last):
    if first >= last:
        return
    mid_value = alist[first]
    low = first
    high = last
    while low < high:
        while low < high and alist[high] >= mid_value:
            high -= 1
        alist[low] = alist[high]
        while low < high and alist[low] < mid_value:
            low += 1
        alist[high] = alist[low]
    alist[low] = mid_value
    quick_sort(alist, first, low - 1)
    quick_sort(alist, low + 1, last)

性质

稳定性

快速排序是一种不稳定的排序算法．

时间复杂度

快速排序的最优时间复杂度和平均时间复杂度为 \(O(n\log n)\)，最坏时间复杂度为 \(O(n^2)\)．

对于最优情况，每一次选择的分界值都是序列的中位数，此时算法时间复杂度满足的递推式为 \(T(n) = 2T(\dfrac{n}{2}) + \Theta(n)\)，由主定理，\(T(n) = \Theta(n\log n)\)．

对于最坏情况，每一次选择的分界值都是序列的最值，此时算法时间复杂度满足的递推式为 \(T(n) = T(n - 1) + \Theta(n)\)，累加可得 \(T(n) = \Theta(n^2)\)．

以下期望分析假设键值互异，且每次从当前子数组等概率随机选取主元．

证明

下面我们来证明这种情况下算法的时间复杂度是 \(O(n\log n)\)．

引理 1： 当对 \(n\) 个元素的数组进行快速排序时，假设在划分元素时曾经比较的不同元素对数为 \(X\)，则快速排序的时间复杂度是 \(O(n + X)\)．

由于在每次划分元素的过程中，都会选择一个元素作为分界，所以划分元素的过程至多发生 \(n\) 次．又由于划分元素的过程中每对元素只比较常数次，比较工作量和其他基础操作的次数在一个数量级，所以总时间复杂度是 \(O(n + X)\) 的．

设 \(a_i\) 为原数组中第 \(i\) 小的数，定义 \(A_{i,j}\) 为 \(\{ a_i, a_{i+1}, \dots, a_j \}\)，\(X_{i,j}\) 是一个取值为 \(0\) 或者 \(1\) 的离散随机变量表示在排序过程中 \(a_i\) 是否和 \(a_j\) 发生比较．

显然每次选取的分界值是不同的，而元素只会和分界值比较，所以不同比较对数

\[ \begin{aligned} X = \sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {j = i + 1} ^ n X_{i,j} \end{aligned} \]

由期望的线性性，

\[ \begin{aligned} E[X] & = E \left[ \sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {j = i + 1} ^ n X_{i,j} \right] \\ & = \sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {j = i + 1} ^ n E[X_{i,j}] \\ & = \sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {j = i + 1} ^ n P(a_i\ \text{和}\ a_j\ \text{比较}) \end{aligned} \]

引理 2： \(a_i\) 和 \(a_j\) 比较的充要条件是 \(a_i\) 或 \(a_j\) 是集合 \(A_{i,j}\) 中第一个被选中的分界值．

先证必要性，即若 \(a_i\) 和 \(a_j\) 都不是集合 \(A_{i,j}\) 中第一个被选中的分界值，则 \(a_i\) 不和 \(a_j\) 比较．

若 \(a_i\) 和 \(a_j\) 都不是集合 \(A_{i,j}\) 中第一个被选中的分界值，则一定存在一个 \(x\) 满足 \(i < x < j\)，使得 \(a_x\) 是 \(A_{i,j}\) 中第一个被选中的分界值．在以 \(a_x\) 为分界值的划分中，\(a_i\) 和 \(a_j\) 被划分到数组的两个不同的子序列中，所以之后 \(a_i\) 和 \(a_j\) 一定不会比较．又因为元素只和分界值比较，所以 \(a_i\) 和 \(a_j\) 在此次划分前和划分中没有比较．所以 \(a_i\) 不和 \(a_j\) 比较．

再证充分性，即若 \(a_i\) 或 \(a_j\) 是集合 \(A_{i,j}\) 中第一个被选中的分界值，则 \(a_i\) 和 \(a_j\) 比较．

不失一般地，假设 \(a_i\) 是集合 \(A_{i,j}\) 中第一个被选中的分界值．由于 \(A_{i,j}\) 中没有其他数选为分界值，所以 \(A_{i,j}\) 中的元素都在数组的同一子序列中．在以 \(a_i\) 为分界值的划分中，\(a_i\) 和当前子序列中所有元素都进行了比较，所以 \(a_i\) 和 \(a_j\) 进行了比较．

考虑计算 \(P(a_i\ \text{和}\ a_j\ \text{比较})\)．在 \(A_{i,j}\) 中某个元素被选为分界值之前，\(A_{i,j}\) 中的元素都在数组的同一子序列中．所以 \(A_{i,j}\) 中每个元素都会被等可能地第一个被选为分界值．由于 \(A_{i,j}\) 中有 \(j - i + 1\) 个元素，由引理 2，

\[ P(a_i \text{和} a_j \text{比较}) = P(a_i \text{或} a_j \text{是集合} A_{i,j} \text{中第一个被选中的分界值}) = \dfrac{2}{j-i+1} \]

所以

\[ \begin{aligned} E[X] & = \sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {j = i + 1} ^ n P(a_i\ \text{和}\ a_j\ \text{比较}) \\ & = \sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {j = i + 1} ^ n \dfrac{2}{j - i + 1} \\ & = \sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {k = 2} ^ {n - i + 1} \dfrac{2}{k} \\ & = \sum \limits _ {i = 1} ^ {n - 1} O(\log n) \\ & = O(n \log n) \end{aligned} \]

由此，快速排序的期望时间复杂度为 \(O(n \log n)\)．

随机选取主元能够降低遭遇最坏划分的概率．此外，快速排序的内存访问遵循局部性原理，这有助于其在实践中取得较好的性能．¹

优化

朴素优化思想

如果仅按照上文所述的基本思想来实现快速排序（或者是直接照抄模板）的话，那一般无法通过 P1177【模板】快速排序这道模板题，因为可以构造数据使朴素快速排序退化为 \(O(n^2)\)．

所以，我们需要对朴素快速排序思想加以优化．较为常见的优化思路有以下三种²．

通过 三数取中（即选取第一个、最后一个以及中间的元素中的中位数） 的方法来选择两个子序列的分界元素（即比较基准）．这样可以避免极端数据（如升序序列或降序序列）带来的退化．
当序列较短时，使用 插入排序 的效率更高．
每趟排序后，将与分界元素相等的元素聚集在分界元素周围，这样可以避免极端数据（如序列中大部分元素都相等）带来的退化．

下面列举了几种较为成熟的快速排序优化方式．

三路快速排序

定义

三路快速排序（3-way Quicksort）将元素按与主元的大小关系分成三部分．它的算法思想基于荷兰国旗问题的解法．

过程

与原始的快速排序不同，三路快速排序在随机选取分界点 \(m\) 后，将待排数列划分为三个部分：小于 \(m\)、等于 \(m\) 以及大于 \(m\)．这样做即实现了将与分界元素相等的元素聚集在分界元素周围这一效果．

性质

三路快速排序在处理含有多个重复值的数组时，效率远高于原始快速排序．其最佳时间复杂度为 \(O(n)\)．

实现

三路快速排序实现起来非常简单，下面给出三路快排的参考实现．

C++Python⁵

// 模板的 T 参数表示元素的类型，此类型需要定义小于（<）运算
template <typename T>
// arr 为需要被排序的数组，len 为数组长度
void quick_sort(T arr[], const int len) {
  if (len <= 1) return;
  // 随机选择基准（pivot）
  const T pivot = arr[rand() % len];
  // i：当前操作的元素下标
  // arr[0, j)：存储小于 pivot 的元素
  // arr[k, len)：存储大于 pivot 的元素
  int i = 0, j = 0, k = len;
  // 完成一趟三路快排，将序列分为：
  // 小于 pivot 的元素 | 等于 pivot 的元素 | 大于 pivot 的元素
  while (i < k) {
    if (arr[i] < pivot)
      swap(arr[i++], arr[j++]);
    else if (pivot < arr[i])
      swap(arr[i], arr[--k]);
    else
      i++;
  }
  // 递归完成对于两个子序列的快速排序
  quick_sort(arr, j);
  quick_sort(arr + k, len - k);
}

def quick_sort(arr, l, r):
    if l >= r:
        return
    random_index = random.randint(l, r)
    pivot = arr[random_index]
    arr[l], arr[random_index] = arr[random_index], arr[l]
    i = l + 1
    j = l
    k = r + 1
    while i < k:
        if arr[i] < pivot:
            arr[i], arr[j + 1] = arr[j + 1], arr[i]
            j += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[k - 1] = arr[k - 1], arr[i]
            k -= 1
        else:
            i += 1
    arr[l], arr[j] = arr[j], arr[l]
    quick_sort(arr, l, j - 1)
    quick_sort(arr, k, r)

内省排序

定义

内省排序（Introsort，Introspective sort）³是快速排序和堆排序的结合，由 David Musser 于 1997 年发明．内省排序其实是对快速排序的一种优化，保证了最差时间复杂度为 \(O(n\log n)\)．

性质

内省排序限制快速排序的划分深度，上限通常取 \(2\lfloor \log_2n \rfloor\)⁴，超过限制时就转换为堆排序．这样既保留了快速排序内存访问的局部性，又可以防止快速排序在某些情况下性能退化为 \(O(n^2)\)．

实现

从 2000 年 6 月起，SGI C++ STL 的 stl_algo.h 中 sort() 函数的实现采用了内省排序算法．

线性找升序下标为 k 的数

在下面的代码示例中，升序下标为 \(k\) 的数被定义为序列排成升序时，第 \(k\) 个位置上的数（编号从 0 开始）．

找升序下标为 \(k\) 的数（K-th order statistic），最简单的方法是先排序，然后直接找到升序下标为 \(k\) 的位置的元素．这样做的时间复杂度是 \(O(n\log n)\)，对于这个问题来说很不划算．

我们可以借助快速排序的思想解决这个问题．考虑快速排序的划分过程，在快速排序的「划分」结束后，数列 \(A_{p} \cdots A_{r}\) 被分成了 \(A_{p} \cdots A_{q}\) 和 \(A_{q+1} \cdots A_{r}\)，此时可以按照左边元素的个数（\(q - p + 1\)）和 \(k\) 的大小关系来判断是只在左边还是只在右边递归地求解．

和快速排序一样，该方法的时间复杂度依赖于每次划分时选择的分界值．如果采用随机选取分界值的方式，可以证明在期望意义下，程序的时间复杂度为 \(O(n)\)．

参考实现

// 模板的 T 参数表示元素的类型，此类型需要定义小于（<）运算
template <typename T>
// arr 为查找范围数组，rk 为需要查找的排名（从 0 开始），len 为数组长度
T find_kth_element(T arr[], int rk, const int len) {
  if (len <= 1) return arr[0];
  // 随机选择基准（pivot）
  const T pivot = arr[rand() % len];
  // i：当前操作的元素下标
  // arr[0, j)：存储小于 pivot 的元素
  // arr[k, len)：存储大于 pivot 的元素
  int i = 0, j = 0, k = len;
  // 完成一趟三路快排，将序列分为：
  // 小于 pivot 的元素 ｜ 等于 pivot 的元素 ｜ 大于 pivot 的元素
  while (i < k) {
    if (arr[i] < pivot)
      swap(arr[i++], arr[j++]);
    else if (pivot < arr[i])
      swap(arr[i], arr[--k]);
    else
      i++;
  }
  // 根据要找的排名与两条分界线的位置，去不同的区间递归查找升序下标为 k 的数
  // 如果小于 pivot 的元素个数比 k 多，则升序下标为 k 的元素一定是一个小于 pivot
  // 的元素
  if (rk < j) return find_kth_element(arr, rk, j);
  // 否则，如果小于 pivot 和等于 pivot 的元素加起来也没有 k 多，
  // 则升序下标为 k 的元素一定是一个大于 pivot 的元素
  else if (rk >= k)
    return find_kth_element(arr + k, rk - k, len - k);
  // 否则，pivot 就是升序下标为 k 的元素
  return pivot;
}

中位数中的中位数

中位数中的中位数（英文：Median of medians），提供了一种确定性的选择划分过程中分界值的方法，从而让「找升序下标为 \(k\) 的数」的算法在最坏情况下也能实现线性时间复杂度．

该算法的流程如下：

将序列划分为 \(\lceil n/5\rceil\) 组，每组至多五个元素，保留不足五个的尾组；
排序每组并取中位数，偶数长度时统一取较小的中位数；
递归选择这些中位数的中位数作为主元，按小于、等于、大于主元三路划分，只递归目标所在的严格小于或严格大于区间．

时间复杂度证明

设中位数的组数为 \(g=\lceil n/5\rceil\)．主元两侧（含等号）各有至少 \(\lfloor g/2\rfloor\) 个组中位数；排除尾组后，每个完整组至少贡献三个不大于或不小于主元的元素．因此两侧各有至少 \(3n/10-O(1)\) 个这样的元素，严格小于和严格大于区间的大小均至多 \(7n/10+O(1)\)．等值区不再递归．分组、求各组中位数和划分共花费 \(O(n)\)．综上，我们可以列出这样的不等式：

\[ T(n)\le T(\lceil n/5\rceil)+T(7n/10+O(1))+O(n). \]

取固定常数 \(a,b\)，使右边两个递归规模之和至多 \(9n/10+a\)，非递归成本至多 \(bn\)．当 \(n\ge20a\) 时，该和至多 \(19n/20\)．在归纳假设 \(T(m)\le cm\) 下，只需取 \(c\ge20b\) 并增大 \(c\) 以覆盖有限个基例，就有 \(T(n)\le19cn/20+bn\le cn\)．因此最坏时间复杂度为 \(O(n)\)．

参考资料与注释

C++ 性能榨汁机之局部性原理 - I'm Root lee ! ↩
三种快速排序以及快速排序的优化 ↩
introsort ↩
例如 libstdc++ 14.2.0：__introsort_loop 和 __sort．实际上将深度限制为 \(O(\log n)\) 并在达到上限时转用堆排序，即可保证总时间复杂度为 \(O(n\log n)\)． ↩
算法实现/排序/快速排序 - 维基教科书，自由的教学读本 ↩↩↩

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用