排序（下）：如何用快排思想在 ○(n) 内查找第 k 大元素（归并排序与快速排序）
极客时间对应链接
上两篇学习到了冒泡排序、插入排序、选择排序这三种排序算法，他们的时间复杂度都是 ○(n²)，比较高，适合小规模的排序，此篇学习两种时间复杂度为 ○(nlogn) 的排序算法，归并排序和快速排序，这两种排序算法适合大规模的数据排序，在实际开发中会比较常用。
归并排序和快速排序都用到了 分治思想。我们可以借鉴这个思想来解决非排序的问题，比如： 如何在 ○(n) 的时间复杂度内查找一个无需数组中的第 k 大元素？
一、归并排序的原理
归并排序的核心思想：如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就有序了。
image
归并排序使用的就是 分治思想。分治，就是分而治之，将一个大问题分解成小的子问题（似曾相识。。。。。递归吗？？。。。），小的问题解决了，大问题也解决了。
没错，分治思想和前面学到的递归思想很像。分治算法一般都是由递归来实现的。 分治是一种解决问题的处理思想，递归是一种编程技巧， 这两者并不冲突。
那么 如何用递归来实现归并排序呢？
首先，要分析得出递推公式，然后找到边界也就是终止条件，最后将递推公式翻译成递归代码。
递推公式：
merge_sort(p...r) = merge(merge_sort(p...q),merge_sort(q+1...r));
终止条件：
q >= r （不需要再继续分解了）
merge_sort(p...r)：给下表从 p 到 r 之间的数组排序。我们将这个排序问题转换为了两个子问题：merge_sort(p...q) 和 merge_sort(q+1...r) ，其中下标 q 等于 p 和 r 的中间位置，也就是 (p+r)/2。当下标从 p 到 q 和从 q+1 到 r 这两个子数组都排好序之后，我们再将两个有序的子数组合并在一起，这样下标从 p 到 r 之间的数据就也排好序了。
/**
* 归并排序
*
* @param a 目标数组
* @param n 数组长度
*/
public static void mergeSort(int[] a, int n) {
mergeRecursion(a, 0, n - 1);
}
private static void mergeRecursion(int[] a, int from, int to) {
//判断递归终止条件
if (from >= to) {
return;
}
//取 from 和 to 的中间位置 middle
// int middle = (from + to) / 2; 可能会出现 from + to 的和大于int类型最大值的情况
int middle = from + (to - from) / 2;
//开始分治递归
mergeRecursion(a, from, middle);
mergeRecursion(a, middle + 1, to);
//将 [from...middle] 和 [middle + 1...to] 合并为 [from...to]
merge(a, from, middle, to);
}
private static void merge(int[] a, int from, int middle, int to) {
//初始化变量 i j k
int i = from;
int j = middle + 1;
int k = 0;
//申请一个大小跟 from...to 一样的数组
int[] temp = new int[to - from + 1];
while (i <= middle && j <= to) {
if (a[i] <= a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
//判断哪个子数组中有剩余的数据
int start = I;
int end = middle;
if (j <= to) {
start = j;
end = to;
}
//将剩余的数据拷贝到临时数组temp中
while (start <= end) {
temp[k++] = a[start++];
}
//将 temp 中的数组拷贝回 a[from...to]
for (int l = 0; l <= to - from; l++) {
a[from + l] = temp[l];
}
}
merge 方法是用来合并数组的，先申请一个临时数组 temp，大小与目标数字相同。使用游标 i 和 j，判断 a[i] <= a[j]，就把 a[i] 放入临时数组 temp 中，并且 i 后移一位，否则将 a[j] 放入到数组 temp 中，j后移一位。
继续上述比较过程，知道其中一个子数组中的所有数据都放入临时数组中，再把另一个数组中的数据依次加入到临时数组的末尾，这个时候，临时数组中存储的就是两个子数组合并之后的结果了。最后再把临时数组 temp 中的数据拷贝到原数组 a 中。
image
二、归并排序的性能分析
继续分析如下三个问题：
第一、归并排序是稳定的排序算法吗？
主要看 merge 函数的写法，若 a[from...middle] 和 a[middle+1...to] 之间有相同的元素，，我们在 merge 函数中，先把 a[from...middle] 中的元素放入 temp 数组中，这样就保证了值相同的元素，在合并前后的顺序不发生变化，所以归并排序是一个稳定的排序算法。
第二、归并排序的时间复杂度是多少？
归并排序设计递归，时间复杂度的分析比较复杂，正好也学习一下如何分析递归代码的时间复杂度。
递归的适用场景是，一个问题 a 可以分解为多个子问题 b、c，那求解问题 a 就可以分解为求解问题 b、c。问题 b、c 解决之后，再把 b、c 的结果合并成 a 的结果。
如果我们定义求解问题 a 的时间是 T(a)，求解 b、c 的时间分别是 T(b) 和 T(c)，那我们就可以得到这样的递推关系式：
T(a) = T(b) + T(c) + K
其中 K 就等于将两个子问题的结果合并成问题 a 的结果所消耗的时间。
由此可以得出一个很重要的结论：不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式。
我们假设 n 个元素进行归并排序需要的时间是 T(n)，那分解成的两个子数组排序的时间都是 T(n/2) 。我们知道，merge() 函数合并两个有序数组的时间复杂度是 ○(n) 。所以，套用前面的公式，归并排序的时间复杂度的计算公式就是：
T(1) = C； n=1时，只需要常量级的执行时间，用 C 表示
T(n) = 2T(n/2) + n； n>1 时（2倍的子数组排序的时间+合并所需的时间）
通过这个公式，我们来推导一下如何求解 T(n)：
image
所以，归并排序的时间复杂度为：○(nlogn)
第三，归并排序的时间复杂度是多少？
归并排序的时间复杂度在任何情况下都为 ○(nlogn) ，看起来非常优秀。但是，归并排序并没有像快排（快排最坏情况下时间复杂度也是 ○(n²)）那样，应用广泛，这是为什么呢？因为归并排序有一个致命弱点，那就是归并排序不是原地排序算法。
因为归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间。那归并排序的空间复杂度是多少呢？该如何分析呢？
如果按照刚才分析时间复杂度的方法，通过递推公式来求解，那整个归并过程需要的空间复杂度就是 ○(nlogn)，但按照分析时间复杂度的方式来分析空间复杂度，这个思路是正确的吗？
实际上，递归代码的空间复杂度并不能像时间复杂度那样累加，因为尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就是只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 ○(n)。
三、快速排序的原理
快速排序算法，我们习惯性把它简称为 快排。快排利用的也是分治思想。乍看起来，它有点像归并排序，但是思路其实完全不一样。
快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点），一般就选数组的最后一个元素作为分区点即可。
遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一系列步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。
分区示意图
那么根据分治、递归的思想，我们可以用递归来排序 下标从 p 到 q-1 之间的数据 和 下标从 q+1 到 r 之间的数据，直到区间[p,r]缩小为 1（在递归过程中，每次传入到递归方法中的参数 p 、r 是在变化的），就说明所有的数据都有序了。
那么递推公式就是：
quick_sort(p...r) = quick_sort(p...q-1) + quick_sort(q+1...r)
终止条件:
p >= r
实现1：
private static void quickSort(int[] a, int n) {
//从 0 到 数组中的最后一个元素
quickRecursion(a, 0, n - 1);
}
private static void quickRecursion(int[] a, int from, int to) {
//判断终止条件
if (from >= to) return;
//获取分区点
int partition = partition1(a, from, to);
quickRecursion(a, from, partition - 1);
quickRecursion(a, partition + 1, to);
}
/**
* 用来获取分区点
* 申请两个临时数组来进行分区操作
*
* @param a 目标数组
* @param from 区间起点
* @param to 区间终点
* @return 分区点的索引
*/
private static int partition1(int[] a, int from, int to) {
//约定使用to位置的元素作为分区点
//最多也就能装除了 最后一个元素的 所有元素
//所以此处的数组 长度设定为 to（也就是 a.length-1)
int[] lessThan = new int[to];
int[] moreThan = new int[to];
int lessIndex = 0;
int moreIndex = 0;
//a.length - 1 可以找到最后一个元素
//但是我们将最后一个元素作为分区点使用，所以在遍历的时候就不需要遍历它了
//只需要 0~ length-2 这些元素来与 分区点比较
//所以这里的循环条件为 i < to
for (int i = from; i < to; i++) {
//如果出现于分区点 相同的元素，我们默认将它放置在 小于数组 中
//此处按照循环顺序来添加，若出现两元素相等的情况，是不会影响到原顺序的
//也就是说是一个稳定排序算法
if (a[i] <= a[to]) {
lessThan[lessIndex++] = a[I];
}
if (a[i] > a[to]) {
moreThan[moreIndex++] = a[I];
}
}
for (int i = 0; i < lessIndex; i++) {
a[i] = lessThan[I];
}
a[lessIndex] = a[to];
for (int i = 0; i < moreIndex; i++) {
a[i + lessIndex + 1] = moreThan[I];
}
return to;
}
image
注意：
如果按照这种思路实现的话，partition1() 方法就需要很多额外的空间，所以快排就不是原地排序算法了。如果我们希望快排是原地排序算法，那么它的空间复杂度得是 ○(1)，那 partition1() 分区函数就不能占用太多额外的内存空间，我们就需要在 a 数组的原地完成分区操作。
新的分区函数 partition2() 的处理方式有点类似选择排序：
/**
* 第二种分区方法
* 使用两个游标来处理数据位置的交换
* @param a
* @param from 区间头端点
* @param to 区间尾端点
* @return 分区点的下标
*/
private static int partition2(int[] a, int from, int to) {
int pivot = a[to];
int i = from;
//循环过程中，游标 j 在不停的移动，游标 i 在某种情况下会移动
//当循环完毕时，j 的位置是区间的倒数第二个元素
// i 的位置就是 分区点应该处于的位置
for (int j = from; j <= to - 1; j++) {
if(a[j] <= pivot){
//交换 a[i] 与 a[j] 的值
int temp = a[I];
a[i] = a[j];
a[j] = temp;
//移动一位
I++;
}
}
//将分区点放在 i 的位置
//把 i 位置的元素放在 分区点原位置
int temp = a[I];
a[i] = a[to];
a[to] = temp;
return to;
}
image
这种写法的快速排序，是稳定的排序算法吗？
image
四、快排和归并排序的区别
image
可以发现，归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。
归并排序虽然是稳定的、时间复杂度为 ○(nlogn) 的排序算法，但是它是非原地排序算法。
归并排序之所以是非原地排序算法，主要原因是合并函数无法在原地执行。
快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。
五、快速排序的性能分析
快排是一种原地、不稳定的排序算法，现在我们来看看快排的时间复杂度。
快排也是用递归实现的，对于递归代码的时间复杂度，在前面推导归并排序的时间复杂度时，已经总结出一个公式。这里也还是适用的，如果每次分区操作，都能正好把数组分成大小接近相等的两个小区间，那快排的时间复杂度递推求解公式跟归并是相同的，所以快排的时间复杂度也是 ○(nlogn) 。
T(1) = C； n=1 时，只需要常量级的执行时间，所以表示为 C。
T(n) = 2*T(n/2) + n； n>1
但是要注意，公式成立的前提是每次分区操作，我们选择的 pivot 分区点 都很合适，正好能将大区间对等地一分为二。但实际上这很难实现。
image
所以，快排最好时间复杂度：○(nlogn) ，最坏时间复杂度：○(n²)
那么快排的平均时间复杂度是多少呢？
推导过程过于复杂，后续章节会学到，此处直接得知结论：在大部分情况下的时间复杂度都可以做到 ○(nlogn) ，只有在极端情况下，才会退化到 ○(n²) ，也有很多方法可以将这个概率降到很低。
网友评论