Grimoire

# 快速排序

基本思想：

  • 数组中取出一个数作为基数
  • 遍历数组，将比基数大的放到右边，小的放到左边，遍历完成，数组分为左右两个区域
  • 将两个区域视为两个数组重复前面步骤

# 描述

快速排序也使用了分治法的思想。 下面是对一个典型的子数组 A[p,..,r]进行快速排序的三步分治过程：

  • 分解：将数组A[p,..,r]划分为两个子数组A[p,..,q-1]和A[q+1,..,r]，使得前一个子数组中每一个元素都小于等于A[q]，后面子数组中每一个元素都大于等于A[q]，其中，计算q也是划分过程的一部分。
  • 解决：通过递归调用快速排序，对子数组进行排序。
  • 合并：子数组是原址排序所有不需要合并。

下面的伪代码实现快速排序：

    QUICKSORT(A,p,r)

    if p<r
    	q=PARTITION(A,p,r)
    	QUICKSORT(A,p,q-1)
    	QUICKSORT(A,q+1,r)
1
2
3
4
5
6

下面的伪代码实现数组的划分：

    PARTITION(A,p,r)

    x=A[r]
    i=p-1
    for j=p to r-1
    	if A[j]<=x
    		i++
    		exchange A[i] with A[j]
    exchange A[i+1] with A[r]
    return i+1
1
2
3
4
5
6
7
8
9
10

JavaScript 版：

function quickSort(A, p, r) {
  if (p < r) {
    let q = Partition(A, p, r);
    quickSort(A, p, q - 1);
    quickSort(A, q + 1, r);
  }
}

function Partition(A, p, r) {
  let x = A[r];
  let i = p - 1; // i 之前的包含i都比x小
  for (let j = p; j < r; ++j) {
    if (A[j] <= x) {
      i++;
      [A[j], A[i]] = [A[i], A[j]];
    }
  }
  [A[i + 1], A[r]] = [A[r], A[i + 1]];
  return i + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 快速排序的性能

最坏情况

当划分产生的两个子问题分别包含了 n-1 个元素和 0 个元素时，时间复杂度是 O(n2)。此外在输入数组完全有序的时候，快速排序的时间复杂度依然是 O(n2)，而在同样的情况下，插入排序是 O(n)

最好情况

在可能的最平衡的划分中，得到的两个子问题的规模都不大于 n/2。在这种情况下，快速排序的性能非常好。时间复杂度是 O(nlog n)

平衡的划分

快速排序的平均时间更接近于最好情况。理解这一点的关键及时理解划分的平衡性是如何反映到描述运行时间的递归式上的。事实上，任何一种常数比例的划分都会产生深度为 O(log n)的递归树，其中每一层的代价都是 O(n)。因此，只要划分是常数比例的，算法的运行时间总会 O(nlog n)

← 归并排序 →