问题描述:现有n个红白蓝三种不同颜色的小球,乱序排列在一起,请通过两两交换任意两个球,使得从左至右,依次是一些红球、一些白球、一些蓝球。

分析:根据三向切分快速排序中的 partition 的思路,将整个数组分成三个部分,对应三种颜色。维护三个指针,一个指针 lt ,使得 a[lo..lt-1] 都小于 v,维护一个指针 gt,使得 a[gt+1..hi] 都大于 v,a[i..gt] 中的元素都还未确定。

但是这个问题比较简单,数组的元素只有三种情况,只需要分别列出来。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void sort(int[] a) {
sort(a, 0, a.length - 1);
}

public static void sort(int[] a, int lo, int hi) {
int lt = lo, i = lo, gt = hi + 1;

while (i < gt) { // 注意
if (a[i] == 0) {
exch(a, lt++, i++);
} else if (a[i] == 1) {
i++;
} else if (a[i] == 2) {
exch(a, --gt, i);
}
}
}