简单_快速排序

/** 快速排序方法 */
	public static void quickSort(int[] a, int lo0, int hi0) {
		int lo = lo0;
		int hi = hi0;

		if (lo >= hi)
			return;

		// 确定指针方向的逻辑变量
		boolean transfer = true;

		while (lo != hi) {
			if (a[lo] > a[hi]) {
				// 交换数字
				int temp = a[lo];
				a[lo] = a[hi];
				a[hi] = temp;
				// 决定下标移动，还是上标移动
				transfer = (transfer == true) ? false : true;
			}

			// 将指针向前或者向后移动
			if (transfer)
				hi--;
			else
				lo++;

			// 显示每一次指针移动的数组数字的变化

			for (int i = 0; i < a.length; ++i) {
				System.out.print(a[i] + ",");
			}
			System.out.print(" (lo,hi) = " + "(" + lo + "," + hi + ")");
			System.out.println("");
		}
		// 将数组分开两半，确定每个数字的正确位置
		lo--;
		hi++;
		System.out.println("一趟。。区间:["+lo0+","+lo+"]["+hi+","+hi0+"]");
		quickSort(a, lo0, lo);
		quickSort(a, hi, hi0);
	}

网上关于快速排序算法一大推，但仔细看了确发现都不是那么一回事，或许是我没找到对的吧！
还好在博客园找到了一篇http://www.cnblogs.com/yanzi629/archive/2010/11/20/1882863.html#commentform

对于快速排序我个人的理解是首先找出一个参照点设为p，排在p左边的都比p要小，右边的都比p要大，然后参照上面的方法把左右两边的数再一次进行排列一直到不能排了。
这是一种分治算法+递归的，容易理解，速度也很快，但是直观的用算法去描述没在网上找到好的描述算法，不过找到了一个基于此思想的更耳目一新的方法，该方法就是上面的代码，不过它是会设置参照点，而是基于机会相等的方法来缩小区间，这样减少了每个数字和其他数字比较的次数，代码中的指针transfer指示头索引和尾索引谁有机会向中间移动，当然这个机会是相等的，不相等要比相等理论上耗时。个人认为这个方法比设置基准点的描述算法好一些。


===============================================================================
2011-10-09 下午 编辑
java.util.Arrays.sort  的源码中对基本数据类型的排序实现是基于快排的

if (len < 7) {
	    for (int i=off; i<len+off; i++)
		for (int j=i; j>off && x[j-1]>x[j]; j--)
		    swap(x, j, j-1);
	    return;
	}

因为当数据量小的情况下快排就没有必要了，递归太浪费资源，一个递归就要入栈出栈，即便该方法什么也不做很浪费资源的，所以排序的数据小于7就用冒泡。
这里有个技巧，内部那个for循环是j--,也就是从高到低的循环，之所以这样写是因为如果你前面都进行了swap那么只用将条件x[j-1]>x[j]写到for的条件里面判断即可。

/**
     * Returns the index of the median of the three indexed integers.
     */
    private static int med3(int x[], int a, int b, int c) {
	return (x[a] < x[b] ?
		(x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
		(x[b] > x[c] ? b : x[a] > x[c] ? c : a));
    }

这个方法目的是寻找a,b,c的中间的那个数，a,b,c可以看成是数组的头、中间、尾三个地方。

快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。
于是就产生了几种变种,分别是：随机化快速排序、平衡快排、外部快排、三路基数快排。
jdk的源码选择的是平衡快排。

平衡快排：每次尽可能地选择一个能够代表中值的元素作为关键数据，然后遵循普通快排的原则进行比较、替换和递归。通常来说，选择这个数据的方法是取开头、结尾、中间3个数据，通过比较选出其中的中值。取这3个值的好处是在实际问题（例如信息学竞赛……）中，出现近似顺序数据或逆序数据的概率较大，此时中间数据必然成为中值，而也是事实上的近似中值。万一遇到正好中间大两边小（或反之）的数据，取的值都接近最值，那么由于至少能将两部分分开，实际效率也会有2倍左右的增加，而且利于将数据略微打乱，破坏退化的结构。