排序算法之快速排序
参考自算法（第四版），快速排序
算法思想
对数组中取一个切分元素，下文简称pivot
然后使得pivot的左边都<= pivot，右边都>=pivot，对于pivot元素，在数组中则是已经排定的，然后继续递归调用pivot左半部分及pivot右半部分，直到子数组中的元素只剩下一个元素时则停止递归
当左子数组<=pivot<=右子数组时，则这个数组就整体有序了
切分算法
快速排序的关键在于切分算法，这个过程使得数组满足下面三个条件
- 对于切分元素（pivot），在数组已经排定
- 数组a[lo..pivot-1]中的元素
<=pivot - 数组a[pivot+1..hi]中的元素
>=pivot
示例
假设我们对[6，1，2，7，9，3，4，5，10，8]数组进行切分，取第一个元素作为切分元素6
然后使用两个指针i,j分别从左右扫描数组，我们首先使用i指针从左开始，找到比6大于等于的元素，然后再使用j从右开始，找到比6小于等于的元素。
第一趟：i => 7，j => 5，交换i与j，
image
image
然后i，j继续刚刚的位置进行扫描
第二趟：i => 9，j => 4，交换i与j
image
image
第三趟：此时i => 9，j => 3，此时i >= j，停止交换i，j，
我们进行最后一次交换切分元素 <=> j
image
image
最后返回j的索引值5，切分结束
递归
此时第一次切分的元素索引为5，我们再递归地切分[0..4]与[6..9]子数组，直到子数组hi <= lo时停止递归
递归调用如下图：
image
图片参考自https://wiki.jikexueyuan.com/project/easy-learn-algorithm/fast-sort.html
代码实现
public class Quick {
public static void sort(Comparable[] array) {
shuffle(array);
sort(array, 0, array.length - 1);
}
private static void sort(Comparable[] array, int lo, int hi) {
if (hi <= lo) {
return;
}
int pivot = partition(array, lo, hi);
// 递归切分
sort(array, lo, pivot - 1);
sort(array, pivot + 1, hi);
}
private static int partition(Comparable[] array, int lo, int hi) {
int i = lo, j = hi + 1;
Comparable pivot = array[lo];
while(true) {
// i扫描找到 >= pivot
while(less(array[++i], pivot)) if (i == hi) break;
// j扫描找到 <= pivot
while(less(pivot, array[--j])) if (j == lo) break;
if (i >= j) {
break;
}
// 交换i，j
swap(array, i, j);
}
// 最后j的位置就是切分元素的位置，交换并返回
swap(array, lo, j);
return j;
}
// i 是否小于 j
private static boolean less(Comparable i, Comparable j) {
return i.compareTo(j) < 0;
}
// 排序前先进行一次打乱
private static void shuffle(Comparable[] array) {
Random random = new Random();
for(int i = array.lenth; i > 0; i--) {
swap(array, i - 1, random.nextInt(i));
}
}
// 交换元素
private static void swap(Comparable[] array, int i, int j) {
Comparable temp = array[i];
array[i] = array[j];
array[j] = array[temp];
}
}
