快速排序

1. 介绍

快速排序是一种特殊的归并排序,它基于分治策略,
将数组分成左和右两部分,然后将他们分别独立排序。

数组的切分是很关键的

快速排序和归并排序在原理上的唯一不同就是,

快速排序的真正比较工作在 递归之前 完成,而归并排序在递归之后完成。

2. 切分

这是快速排序真正做比较的部分,也就是真正起作用的部分。

切分的目标是找到一个元素:

  1. 它的左边的所有元素都不大于它
  2. 它的右边的所有元素都不小于它

2.1 实现流程

一般来说,我们并不能找到这样的元素,所以我们进行以下的操作:

  1. 随机的选择元素

    通常来说,选择数组的第一个元素

  2. 从数组的两端同时开始扫描数组

    i, j 分别指向数组的两端;
    i 自增,直到 i 所指元素 a[i] 不小于切分元素 a[lo]
    j 自减,直到 j 所指元素 a[j] 不大于切分元素 a[lo]

  3. 如果元素不在正确的位置,那么就交换它

    上述的 i, j 都停止后,交换 a[i]a[j]

  4. 直到这两个指针相遇或者跨越对方,然后将切分元素放到相遇位置。

    事实上,此时 j 所指的元素就是不大于切分元素的元素;
    因此,将切分元素 a[lo]a[j] 交换即可让切分元素放入正确位置

The Partition

2.2 实现

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
private static int partition(Comparable[] a, int lo, int hi) {
int i = lo, j = hi + 1; // The scanner
Comparable v = a[lo];
while (true) {

// 指针 i 的扫描过程
while (less(a[++i], v)) {
if (i == hi) {
break;
}
}

// 指针 j 的扫描过程
while (less(v, a[--j])) {

// 实际上这个 if 是多余的,
// 因为我们的切分元素就在 lo 的位置,
// 当 j 位于 lo 的位置时,由于不满足条件,
// j 就会停止扫描
if (j == lo) {
break;
}
}

//两指针相遇,完成扫描过程
if (i >= j) {
break;
}

// 此时两指针停止,说明 a[i] 和 a[j] 都不在正确位置
// 所以将 a[i] 和 a[j] 交换
exch(a, i, j);
}

// 扫描完成,将切分元素放入正确位置
exch(a, lo, j);
return j;
}

2.3 注意事项

  1. 切分在原本的数组中发生

    事实上, 也可以使用一个辅助数组;
    但是这样就丧失了相对于归并排序的不需要额外空间的优势

  2. 不要越界

    注意检查扫描指针和边界的关系

  3. 注意保持随机性

    在快速排序中保持随机性是保证此算法性能的关键

  4. 注意循环的终止条件

    一个程序员常犯的错误就是没有考虑到数组可能包含与切分你元素的值相同的元素,从而导致了循环无法结束;
    所以在上面的实现中,即使扫描到相同元素也会停止扫描,保证了不会因为重复元素而影响性能

  5. 注意递归的终止条件

    如果你不能把切分元素放入到正确的位置(放入到了错误的位置),那么就有可能引起一个无法终止的递归,这是要极力避免的。

3. 基本实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Quick {
public static void sort (Comparable[] a) {
// Disable the dependency to the input String
// It's very important.
StdRandom.shuffle(a);
sort(a, 0, a.lenth - 1);
}

private static void sort (Comparable[] a, int lo, int hi) {
if (hi <= lo) return;

int j = partition(a, lo, hi);

sort(a, lo, j - 1);
sort(a, j + 1, hi);
}
}

可以看到,和归并排序一样,快速排序中真正做比较和交换的,实际上是切分这一个过程,而不是 sort() 方法

4. 性能

快速排序需要 2NlnN\sim 2NlnN 次的比较和 1/61/6 的交换
在最坏情况下,当输入数组本身就是有序时,快速排序需要 N2/2N^2 / 2 次的比较

但是通过打乱输入保证随机性可以防止这种情况的发生

5. 改进

5.1 切换到插入排序

对于一些小型数组,插入排序会比快速排序要快,这是由于快速排序使用了递归方法进行排序

1
2
3
4
5
6
7
8
9
10
11
12
private static void sort (Comparable[] a, int lo, int hi) {

if (ho <= lo + M) {
Insertion.sort(a, lo, hi);
return;
}

int j = partition(a, lo, hi);

sort(a, lo, j - 1);
sort(a, j + 1, hi);
}

5.2 三取样切分

快速排序基于切分,如果切分元素选择的好,那么就可以减少切分所用的时间,从而提高算法性能
在实践中,我们一般使用三取样,然后取其中位数的形式来选取切分元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private static void sort (Comparable[] a, int lo, int hi) {

// 小数组使用插入排序
if (ho <= lo + M) {
Insertion.sort(a, lo, hi);
return;
}

// 三取样获取切分元素
int m = medianOf3(a, lo, lo + (hi - lo) / 2, hi);
swap(a, lo, m);

int j = partition(a, lo, hi);

sort(a, lo, j - 1);
sort(a, j + 1, hi);
}

三取样,即选取数组头部、尾部和中间位置的元素

6. 三向切分的快速排序

对于有大量重复性元素的数组,我们采用这个算法,实际上属于快速排序的一种改进形式。

6.1 实现原理

使用 2 个指针 (lt,gt)来维护数组的 3 个部分:

  1. 小于切分元素的

    指针 lolt 之间属于这个部分

  2. 等于切分元素的

    指针 ltgt 之间属于这个部分

  3. 大于切分元素的

    指针 gthi 之间属于这个部分

  • 指针 lt 的左边都是小于切分元素的元素
  • 指针 gt 的右边都是大于切分元素的元素
  • 指针 ltgt 之间都是等于切分元素的元素

6.2 实现过程

3way Quick Sort

指针 i 实际上的作用是进行数组扫描;

ltgt 的工作是进行数组区域的划分。

  1. 初始状态,lt 在数组头部,i 位于 lt 的后一个位置, gt 在数组尾部

  2. a[i] 小于切分元素时,交换 a[i]a[lt],并自增lti

    交换过后,i 所指的元素已经被检查过;
    而为了满足 lt 左边的元素都是小于切分元素的,所以 lt 要增加

  3. a[i] 大于切分元素时候,交换 a[i]a[gt],并自减 gt

    此时,由于 i 所指的元素是从数组尾部交换来的;
    并没有经过检查
    所以不能自增 i

  4. a[i] 等于切分元素时候,自增 i

    由于任何时候, i 都会在 lt 的前面;
    这种情况下,说明 a[i] 已经处于正确位置;
    不必进行交换操作

  5. igt 相遇时,切分完成

    此时,所有的元素都经过了 i 的检查,切分完成

6.3 具体实现

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
public class Quick3way {
private static void sort(Comparable a, int lo, int hi) {

if (hi <= lo) return;

int lt = lo, i = lo + 1, gt = hi;

Comararble v = a[lo]; // 切分元素

while (i <= gt) {

int cmp = a[i].compareTo(v);

if (cmp < 0) {
// i 比 v 小
exch(a, lt++, i++);
}
else if (cmp >0) {
// i 比 v 大
exch(a, i, gt--);
}
else {
i++;
}
}

sort(a, lo, lt - 1);
sort(a, gt + 1, hi);
}
}

6.4 性能

对于含有重复元素的数组,我们有一个值来描述这个数组的信息含量,它叫做香农信息量(HH)

H=(p1lgp1+p2lgp2++pklgpk)H = -(p_1lgp_1 + p2lgp_2 + \cdots + p_klgp_k)

HThe Shannon informationH - The \ Shannon\ information
piThe posibillty of the ith key was selectedp_i - The\ posibillty\ of\ the\ ith\ key\ was\ selected

对于含有重复元素的数组,不存在任何基于比较的排序算法能够保证在 NHNNH - N 次比较之中将 NN 个元素排序。其中 HH 是由主键值概率定义的香农信息量

所以,它证明了三向切分的快速排序是最好的基于比较的算法,信息量最优

事实上,对于拥有大量重复键值的数组来说,三向切分的快速排序的时间复杂度是 线性级别的

0%