问题

对给定数组a[l ... r]排序.

方案

思路

分治. 先选一个数作为基准值, 然后小的放左边, 大的放右边.递归下去.

举个例子: 7 8 4 3 6 9 5 1 2

不妨选5作为基准值, 排一次成了这样: 4 3 1 2 5 7 8 6 9

由于左边<基准值<右边, 所以我们发现原来的问题变成了两个子问题, 即排序4 3 1 2和7 8 6 9.

递归求解即可.

基准值的选取

当然是中位数最优. 但找中位数本身很难. 所以我们选取位置在最左, 最右和中间的数的中位数来替代.

我们记这个值是v. 在上面的例子中, 即7 6 2的中位数’6’.

如何将数分在两侧

我们先把基准值和a[l]换一下位置.

记指针i代表a[l ... i - 1] < v,j代表a[j + 1 ... r] > v. 一开始取i = l, j = r.

再记’k’代表当前处理到了第k个元素, 并让k = l + 1(因为l处的元素就是基准值).

我们维护这样一件事:

l ... i - 1 小于v

i ... k - 1 等于v

k ... j 未处理

j + 1 ... r 大于v

那么当k > j时处理结束. 具体地:

如果a[k] > v, 把a[k]和a[j]互换位置, 并--j(把大的放到后面).

如果a[k] < v, 把a[k]和a[i]互换位置, 并++i, ++k(把小的放到前面).

如果a[k] == v, ++k.

这样便将数组里的数分在了基准值两侧.

递归过程

原来是l ... r, 现在只需要解决子问题l ... i - 1和j + 1 ... r.

l >= r时不再递归下去.

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
inline void cswap(int &a, int &b) { int c = a; a = b; b = c; }
inline void quick_sort(int *l, int *r)
{
	if (l >= r) return;
	int *i = l, *j = r, *k = l + ((r - l) >> 1);
	if (*k > *i) cswap(*i, *k);
	if (*k > *j) cswap(*j, *k);
	if (*i > *j) cswap(*i, *j);
	int v = *i; k = i + 1;
	while (k <= j)
	{
		if (*k > v) cswap(*j, *k), --j;
		else if (*k < v) cswap(*i, *k), ++i, ++k;
		else ++k;
	}
	quick_sort(l, i - 1);
	quick_sort(j + 1, r);
}