This doc has been marked needs-review. Following information are in upcoming update plan.

mooyyu

O1 - 快速排序

c++11 sort utility functional 

template< class type, class Comp >
void quick_sort(type *v, int l, int r, Comp cmp) {
	static int i, j;
	static type x;
	if (l >= r-1) return ;
	i = l-1, j = r;
	x = v[(l+r)>>1u];
	while (i < j) {
		while (cmp(v[++i], x)) ;
		while (cmp(x, v[--j])) ;
		if (i < j) swap(v[i], v[j]);
	}
	quick_sort(v, l, i, cmp);
	quick_sort(v, i, r, cmp);
}

Usage

如果不是自定义比较函数, 一般cmp只能是less<>()和greater<>().

Notes

  • l, r的意义类似于begin(), end()
  • 注意边界问题, 此模版中x不可取值为v[l]
  • i, j两个指针向中间逼近时必须使用严格的大于(小于)比较, 这样能保证指针不越界
  • 取中值或随机(位置)值优于取左(右)值

快速排序的应用

查找rank_k 
template< class type, class Comp >
type seek_kth(type *v, int l, int r, int k, Comp cmp) {
	static int i, j;
	static type x;
	i = l-1, j = r;
	x = v[(l+r)>>1u];
	while (i < j) {
		while (cmp(v[++i], x)) ;
		while (cmp(x, v[--j])) ;
		if (i < j) swap(v[i], v[j]);
	}
	if (v[i] == x && i == k) return x;
	if(k < i) return seek_kth(v, l, i, k, cmp);
	else return seek_kth(v, i, r, k, cmp);
}