快速排序(英语:Quick Sort),又被称为划分交换排序(Partition Exchange Sort),简称快排,一种排序算法,最早由东尼·霍尔提出。

快速排序的中心思想

分而治之,各个击破。

快速排序主要使用“分治法”(归并排序运用的也是这个策略)策略来将序列一分为二,分成两个子序列,当这两个子序列有序之后,整个序列也就自然有序了。

快排的步骤

首先假设我们拥有一个长度为\(N\)的序列,我们对这个序列进行快排需要经过一下三个步骤:

  1. 首先我们从这个序列中挑出一个数值,作为“基准值”(Pivot)
  2. 重新排序序列,将所有比基准值小的元素放在基准值的左边,所有比基准值大的元素放在基准值的右边,在经过这样的分区操作结束之后,这个基准值应该位于序列的中间位置。这个操作被称为“切分”,也被成为“分区”(Partition)
  3. 递归地把小于基准值的子序列和大于基准值的元素进行排序。
    当递归到最底部的时候,子序列数量为\(1\)的时候,排序算法结束。此时整个序列是有序的。

举个栗子了解快速排序

前些天我在BiliBili上看到一个TED出的教育视频,里面很好的解释了快速排序是怎么样的一个原理。
首先假设我们是图书馆的管理员,今天下午闭馆之前来了一批书(这批书是杂乱无序的),书籍数量为\(1280\)本,我们图书馆假设不存在自动排序系统,需要我们自己手工去进行排序,而明天早上开馆之前这些书要经过我们精心排序且上架,要求在最快的时间内完成。
如果用快速排序来对书籍进行排序是怎么样的步骤呢?

  1. 首先,我们从这一堆书内随便找出一本书,作为“关键书籍”(可以理解为基准值),并且和每一本书做对比。
  2. 接着我们将书堆分成两半(除去关键书籍),比关键书籍小的都放在左边,比关键书籍大的都放在右边。
  3. 现在我们先只看左边的这部分书,以同样的方法再随机取出一本书作为关键书籍,再以前两步的方法将这部分书分成两个书堆。右边的书堆同样这么做。直到这\(1280\)本书变成一堆小书堆。
  4. 每个小书堆都用别的方法进行排序,然后我们再将这几本关键书籍放到正确的顺序的正确位置上。我们的对这\(1280\)本书就完成了排序。
    现在我们来分析一下,每轮关键书籍都要进行大概\(1280\)次对比(每轮指的是把整堆书籍一分二、二分四这样算作一轮),如果关键书籍在这堆书籍中分布均匀,那么把这堆书籍分成\(128\)个小堆,每堆\(10\)本,只需要\(7\)轮,得出\(128\times10\times7 = 8960\)秒,再把每个小堆进行排序,每堆排序需要\(22\)秒的时间,那么我们总共需要\(8960+(22\times128) = 11776 = 3.3 hours\)就可以将这些书籍进行排序了。

快速排序的时间复杂度与稳定性

前面归并排序的文章里写了算法稳定性的定义,快速排序不满足算法稳定性的定义,所以是不稳定算法。
时间复杂度上,快排在最坏的情况下是\(O(N^2)\),平均的时间复杂度为\(O(N\,log\,N)\)。
假设一下,被排序的序列中有\(N\)个数,遍历其一次的时间复杂度是\(O(N)\),那么需要遍历多少次呢?最少也得\(lg(N + 1)\)次,最多的话是\(N\)次。快速排序是采用“分治法”的策略来进行遍历的,那么我们可以将它看作成一颗二叉树,快排需要遍历的次数就是这颗二叉树的深度,而根据完全二叉树的定义,这棵树的深度最少也得是\(lg(N + 1)\)次,这棵树的深度最大为\(N\)。

原地快速排序的代码实现(In Place Quick Sort)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package net.sunzhenyu.miscellaneous.dsa.sort;

public class QuickSort implements Sort {

@Override
public void sort(Comparable[] c) {
sort(c, 0, c.length - 1);
}

private void sort(Comparable[] c, int lo, int hi) {
if (hi <= lo) {
return;
}
// 进行切分获取基准值
int j = partition(c, lo, hi);
// 将[lo...j-1]部分排序
sort(c, lo, j - 1);
// 将[j+1...hi]部分排序
sort(c, j + 1, hi);
}

private int partition(Comparable[] a, int lo, int hi) {
// 进行切分,假设初始的基准值为a[lo], j为序列最右边元素的索引
int i = lo, j = hi + 1;
// 找到基准值索引位置所在的元素
Comparable partitionElement = a[lo];
while (true) {
// 持续从基准值位置向右扫描是否有小于基准值位置的元素,如果有就结束扫描并交换元素
while (less(a[++i], partitionElement))
if (i == hi)
break;
// 持续从最右边(序列边界)向左扫描是否有小于基准值位置的元素,如果有就结束扫描并交换
while (less(partitionElement, a[--j]))
if (j == lo)
break;
// 从最右边(序列边界)直到扫描到基准值的位置
if (i >= j)
break;
exchange(a, i, j);
}
// 将基准值元素放到正确位置
exchange(a, lo, j);
// 返回基准值
return j;
}

private void exchange(Comparable[] c, int i, int j) {
Comparable oldValue = c[i];
c[i] = c[j];
c[j] = oldValue;
}
}

快速排序的优化

快速排序在\(1960\)年被发明之后,就不断的有人提出了改进的方案,但并不是所有的改进想法都是可行的,因为快排的平衡性已经非常好了。
但往往在实际工作当中,一个算法总有不足以更好的解决问题的时候,下来我们来提出三个可以对快速排序进行改进的方案。

  1. 和大多数的递归算法一样,改进快排的一个最简单的方案也是最实用的方案就是在对于长度较短的序列排序时,采用其他在解决小数据量方面比较擅长的算法,这里我们可以在对于序列长度为\(5\thicksim15\)之间的序列采用插入排序算法。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    private void sort(Comparable[] c, int lo, int hi) {
    if (hi <= lo + SORT_CAPACITY) {
    insertionSort(c, lo, hi + 1);
    return;
    }
    // 进行切分获取基准值
    int j = partition(c, lo, hi);
    // 将[lo...j-1]部分排序
    sort(c, lo, j - 1);
    // 将[j+1...hi]部分排序
    sort(c, j + 1, hi);
    }
  2. 在取基准值的时候,我们是采用选取序列中的第一个数作为基准值,这样会导致在切分的过程中可能会导致出现一种极端的情况:比如切分了\(1\)和\(N - 1\)两个序列,这样会导致算法处于最坏情况下。这时我们可以采用三取样切分法来改进算法,通过取序列中最左、中间、最右三个数值的中间值作为中位数来切分,代价则是我们需要计算出中位数。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    private int partitionWithMedian(Comparable[] a, int lo, int hi) {
    int n = hi - lo + 1;
    // 求出a[lo], a[lo + n / 2], a[hi]三个索引位置的数值的中位数
    int m = median(a, lo, lo + n / 2, hi);
    // 将中位数位置的值与a[lo]交换
    exchange(a, m, lo);

    int i = lo;
    int j = hi + 1;
    Comparable k = a[lo];

    // 假设k是整个序列中唯一大的数值
    while (less(a[++i], k)) {
    if (i == hi) {
    exchange(a, lo, hi);
    return hi;
    }
    }

    // 假设k是整个序列中唯一小的数值
    while (less(k, a[--j])) {
    if (i == lo + 1) {
    return lo;
    }
    }

    while (i < j) {
    exchange(a, i, j);
    while (less(a[++i], k));
    while (less(k, a[--j]));
    }

    exchange(a, lo, j);
    return j;
    }
  3. 上面我们采用了三取样切分法来改进我们的快速排序算法,但在实际情况中,如果序列中包含了大量的重复元素,上面的三取样切分法对于这种数据的处理还是存在缺陷。为了解决这种情况,我们可以通过切分元素将序列切分为三个部分,分别对应于小于、大于和等于切分元素的序列元素。这种方法将比我们一直采用的“分治法”更为复杂。
    此处的优化方法待更新,将会单独开文章更新并在此连接过去。