什么是”三向切分”?

首先我们要了解“三向切分”这四个字是什么意思。
在以往的原地快速排序中,我们在对于处理数据量比较大且其中包含不定量的重复元素的时候,递归处理显而易见并不是最好的解决方案(仔细想一想为什么),我们是否有一个更好的解决方案呢? 如果我们将序列通过抽取一个参照物(切分元素),将序列分割成以下三个子序列:

  1. 包含小于参照物的元素的子序列
  2. 包含大于参照物的元素的子序列
  3. 等于参照物元素的子序列

这样我们就将不必要向下迭代的重复元素剔除出来了。
但是在“三向切分”快速排序中,我们需要同时维护三个指针:\(lt\)、\(i\)和\(gt\),我们假设现在有长度为\(N\)的序列\(a\),这三个指针分别的作用如下:

  1. \(lt\)使得\(a[lo \dots lt - 1 ]\)中的元素都小于参照物
  2. \(gt\)使得\(a[gt + 1 \dots hi]\)中的元素都大于参照物
  3. \(i\)使得\(a[lt \dots i - 1]\)中的元素都等于参照物

此时\(a[i \dots gt]\)中的元素是不确定的。这样进行切分一次之后,我们就可以有效的减少序列中的重复元素了,因为重复元素都被集中在\(a[lt \dots gt]\)这个区间中了,在下次递归的时候我们就不必再对这一部分进行分区了。

代码实现

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
package net.sunzhenyu.miscellaneous.dsa.sort;

public class QuickSort3Way implements Sort {

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

private void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) {
return;
}
int lt = lo, i = lo + 1, gt = hi;
Comparable v = a[lo];
while (i <= gt) {
int cmpr = a[i].compareTo(v);
if (cmpr < 0) {
exchange(a, lt++, i++);
} else if (cmpr > 0) {
exchange(a, i, gt--);
} else {
i++;
}
}
sort(a, lo, lt - 1);
sort(a, gt + 1, hi);
}

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