排序：快速排序
1 思路
假设对数组data进行排序，如果能够对data以元素v分割成左右两部分，
- 对于左边所有元素都比v小，
- 对于右边所有元素都比v要大。
那么只要我们不断的递归对左右两个子数组进行相同的过程，最终数组就都会有序。
快速排序
2 实现
因此，首先需要考虑的是，如何对一个数组进行分割？
如果我们要分割数组data[l, r]中的元素，首先需要选定一个标定点：这里我们选择最左边(l)的元素：
那么我们可以使用变量i循环遍历data[l+1, r]的区间，如果遇到比v小的，那么我们就放到j+1的位置，同时j要自增1，以表示<v的部分进行了扩容。如下图所示，操作i和j的目的是不断的缩小未处理部分，同时给<v和>=v的部分扩容。需要注意的是，需要考虑=v的元素，我们将其放在了右边部分。
partition过程
当整个未处理部分未空时，此时，我们只需要交换v和j处的元素，即完成了分割，分割方法实现如下：
// 将data[l, r]划分为三部分data[l, j-1]、data[j]、data[p+1, r]，其中，data[l, j-1]所有元素都比data[j]小，data[j+1, r]所有元素都比data[j]要大
private static <E extends Comparable<E>> int partition(E[] data, int l, int r) {
E v = data[l];
int j = l;
for (int i = l + 1; i <= r; i++) {
if (data[i].compareTo(v) < 0) {
j++;
Utils.swap(data, i, j);
}
}
Utils.swap(data, l, j);
return j;
}
已经有了分割方法，接下来实现递归，思路如下：
- 对数组以v进行分割
- 对<v的子数组进行排序
- 对>=v的子数组进行排序
- 递归之
实现代码如下：
public static <E extends Comparable<E>> void sort(E[] data) {
if (data == null || data.length <= 1) {
return;
}
sort(data, 0, data.length - 1);
}
// 宏观语义：该函数的功能用于对数组data的区间[l, r]进行排序
private static <E extends Comparable<E>> void sort(E[] data, int l, int r) {
// 最简单的情况
if (l >= r) {
return;
}
// 先解决更小的问题
int p = partition(data, l, r);
sort(data, l, p - 1);
sort(data, p + 1, r);
}
3 有序数组的退化
有序数组会使快排退化为O(n^2)的复杂度，这是因为，当数组有序的时候，每次partition后，左半区间将为空，而右半区间将为除v外的所有元素，这就违背了一分为二的分治思想，树的层次将由O(logn)变为了O(n)层。
解决的办法是，随机选择数组中的一个元素作为v，然后和第0个元素交换位置。
// 将data[l, r]划分为三部分data[l, j-1]、data[j]、data[p+1, r]，其中，data[l, j-1]所有元素都比data[j]小，data[j+1, r]所有元素都比data[j]要大
private static <E extends Comparable<E>> int partition(E[] data, int l, int r, Random random) {
int p = random.nextInt(r - l + 1) + l;
Utils.swap(data, l, p);
E v = data[l];
int j = l;
for (int i = l + 1; i <= r; i++) {
if (data[i].compareTo(v) < 0) {
j++;
Utils.swap(data, i, j);
}
}
Utils.swap(data, l, j);
return j;
}
4 双路快排
上面的算法还是有问题，当所有元素都相等时，还是会出现退化为O(n^2)复杂度的问题。这是因为，我们总是把等于v的元素都放到右边，因此还是会出现左半区间将为空，而右半区间将为除v外的所有元素这种情况。解决方法是把=v的元素分散在左右两半空间，具体思想如图示：
双路排序
做一些解释：
- 我们需要遍历的是未处理部分的区间，并将该区间的元素分散到左右两个区间中，该区间用[i, j]表示。
- 向后遍历i，一旦data[i]>=v的元素停止遍历
- 向前遍历j，一旦data[j]<=v的元素停止遍历
- i的起始值为l+1，此时未处理部分为除第l个元素的所有元素；终止值>j，此时表示没有未处理部分了。
- j的初始值为r；终止值为<i，此时表示没有未处理部分了。
- 如果，i和j处的元素需要交换，交换i和j处的元素。
private static <E extends Comparable<E>> int partition2(E[] data, int l, int r, Random random) {
int p = random.nextInt(r - l + 1) + l;
Utils.swap(data, l, p);
int i = l + 1;
int j = r;
while (true) {
while (i <= j && data[i].compareTo(data[l]) < 0) {
i++;
}
while (j >= i && data[j].compareTo(data[l]) > 0) {
j--;
}
if (i >= j) {
break;
}
Utils.swap(data, i, j);
i++;
j--;
}
Utils.swap(data, l, j);
return j;
}
5 复杂度分析
对于双路算法来说，其实还是存在某种情况，每次随机取得的值刚好可以使算法退化到O(n^2)，但这样的概率非常小，可以忽略不记；对于算法复杂度分析，有下面三条原则：
- 如果能找到一组数据能使算法100%恶化，此时是普通算法，看最差情况，例如单路排序。
- 如果没有一组数据能使算法100%恶化，此时是随机算法，看期望，例如双路排序。
- 如果算法中间会有多次调用，可以尝试均摊分析，例如数组的扩容
6 三路快排
如果一个数组中存在大量相同的元素，其实在遍历的时候就可以辨别出来，那么在partition过程中，就可以把那部分数据都放在中间，再一次递归就可以少递归很多元素，其大致思想如下图：
三路快排
做如下解释：
- 将数组分为五个部分，v, <v的部分，=v的部分，未处理部分，>v的部分
- 循环遍历未索引部分，由i来表示，如果i处的元素<v，则和lt后面的元素进行交换，扩容<v的部分，i后挪
- 如果i的元素>v，则和gt前面的元素进行交换，此时，由于交换到i处的元素还未被考察，因此i不变，gt需要向前挪
- i的终止条件是>=gt还要大，则表示没有可考察的元素了，未处理部分未空
private static <E extends Comparable<E>> void sort3ways(E[] data, int l, int r, Random random) {
// 最简单的情况
if (l >= r) {
return;
}
int lt = l, gt = r + 1, i = l;
// 维持循环不变量：data[l+1, lt] < v, data[lt+1, i-1]=v, data[gt, r]>v
while (i < gt) {
if (data[i].compareTo(data[l]) < 0) {
lt++;
Utils.swap(data, lt, i);
i++;
} else if (data[i].compareTo(data[l]) > 0) {
gt--;
Utils.swap(data, gt, i);
} else {
i++;
}
}
Utils.swap(data, l, lt);
//此时，data[l, lt-1] < v, data[lt, i-1]=v, data[gt, r]>v
sort3ways(data, l, lt - 1, random);
sort3ways(data, gt, r, random);
}
