快速排序

/**
 * 快速排序
 * <ul>
 * <li>平均情况：O(nlog(2)n)</li>
 * <li>最好情况：O(nlog(2)n)</li>
 * <li>最坏情况：O(N^2)</li>
 * <li>辅助存储：O(nlog(2)n)</li>
 * <li>不稳定</li>
 * <ul>
 * 
 * @timestamp Mar 11, 2016 10:43:10 PM
 * @author smallbug
 */
public class QuickSort {
	private static int SCOPE = 5;

	public static void main(String[] args) {
		int[] data = DataUtil.getData(10000000);
		// System.out.println(Arrays.toString(data));
		long time = System.currentTimeMillis();
		quickSort(data);
		// System.out.println(Arrays.toString(data));
		System.out.println("speed " + (System.currentTimeMillis() - time) + " ms");
		System.out.println("排序是否成功：" + (DataUtil.verify(data, DataUtil.ASC) ? "是" : "否"));
	}

	private static void quickSort(int[] data) {
		sortPart(data, 0, data.length - 1);
		insertSort(data);
	}

	private static void sortPart(int[] data, int i, int j) {
		if (j - i < SCOPE || i == j)// 小于一定范围就返回，等待最后一遍插入排序扫尾
			return;
		int i_c = i;
		int j_c = j;// 缓存索引
		int media = (i + j) >>> 1;
		int temp = data[media];
		while (data[i++] <= temp && (i - 1) != j)
			;
		data[media] = data[--i];
		for (; i != j;) {
			while (data[j--] >= temp && i != (j + 1))
				;
			data[i] = data[++j];
			if (i == j)
				break;
			while (data[i++] <= temp && (i - 1) != j)
				;
			data[j] = data[--i];

		}
		data[i] = temp;
		sortPart(data, i_c, j - 1);
		sortPart(data, i + 1, j_c);
	}

	private static void insertSort(int[] data) {
		int temp;
		for (int i = 1; i < data.length; i++) {
			temp = data[i];// 保存待插入的数值
			int j = i;
			for (; j > 0 && temp < data[j - 1]; j--) {
				data[j] = data[j - 1];// 如果待插入的数值前面的元素比该值大，就向后移动一位
			}
			data[j] = temp;// 插入
		}
	}
}