快速排序

快排的主要思想就是：
1. 指定一个基准值（枢纽， 可以为第一个， 最后一个， 中值 或者 随即值）
2. 双向扫描， 发现高位有值小于基准值， 将高位值赋给低位， 并将低位加1； 发现低位值大于高位， 则将地位值赋给高位， 并将高位减1； 直到高低位重合。
3. 将基准值赋给当前低位或高位（重合了）。
4. 对当前低位或高位分开的两个子区间运用以上1到3步即可。

上代码：

private static void qSort(int[] source, int from, int to) {
	if (from < to) {
		int pivot = source[from];

		int low = from, high = to;
		while (low < high) {
			while (low < high && source[high] >= pivot)
				high--;
			source[low] = source[high];
			while (low < high && source[low] < pivot)
				low++;
			source[high] = source[low];
		}
		source[low] = pivot;

		qSort(source, from, low - 1);
		qSort(source, low + 1, to);
	}
}

评论

1 楼 huhu_long 2011-10-20  

简单说,取第一个作为参考pivot值,while(low<high)
先从高位开始扫,碰到比pivot小的停下并把值赋给当前地位
接下来从低位扫,碰到比pivot大的停下并把值赋给当前高位
等结束while循环，把pivot的值赋给当前低位，此时左边都比pivot小，右边都比pivot大。

最后就是递归[from, low - 1] 和 [low + 1, high] 自区间。

记得每个while循环都应该判断 low < high, 否则容易出错。