[TOC]

12 | 排序（下）：如何用快排思想在O(n)内查找第K大元素？

归并排序的原理

归并排序的核心还是蛮简单的。如果要排序一个数组，我们先把数组中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就有序了。

归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也解决了。

从我刚才的描述，你有没有感觉到，分治思想跟我们前面讲的递归思想很像。是的，分治算法一般都是用递归来实现的。 分治是一种解决问题的处理思想，递归是一种编程技巧， 这两者并不冲突。

**如何用递归代码来实现归并排序。**

递推公式：
meger_sort(p...r) = merge(meger_sort(p...q), meger_sort(q+1,r))

终止条件
p>=r 不用再继续分解

merge_sort(p…r)表示，给下标p到r之间的数组排序。

复杂度分析

同样三个问题：

**第一、归并排序是稳定的排序算法么？**

结合图和代码，应该能发现归并排序稳不稳关键要看merge()函数。也就是将两个有序子数组合并成一个有序数组的那部分代码。

在合并过程中，如果A[p…q]和A[q+1…r]之间有值相同的元素，归并后元素的相对位置是不变的。所以，归并排序是一个稳定的排序算法。

**第二、归并排序的时间复杂度是多少？**

归并排序涉及递归，时间复杂度稍微有点复杂。我们正好借此机会来学习一下，如何分析递归代码的时间复杂度。

递归的适用场景是，一个问题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等于将两个子问题b、c的结果合并成问题a的结果说消耗的时间。

从刚刚的分析，我们可以得到一个重要的结论： **不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式。**

套用这个公式，如何来求解T(N)呢？还不够直观？那我们再进一步分解一下计算过程。

T(n) = 2*T(n/2) + n
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
     ......
     = 2^k * T(n/2^k) + k * n
     ......

通过这样一步一步分解推导，我们可以达到 T(n) = 2^kT(n/2^k)+kn。

当T(n/2^k) = T(1)时，也就是n/2^k = 1，我们得到k=$log_2n$。将k值带入上面的懂事，得到$T(n)=Cn+nlog_2n$。如果用大O法标记来表示的话，$T(n)=O(nlogn)$。所以归并排序的时间复杂度是$O(nlogn)$。

从我们原理的分析和伪代码可以看出，归并排序的执行效率与要排序的数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是$O(nlogn)$。

**第三、归并排序的空间复杂度是多少？**

从伪代码中可以看出，空间复杂度是O(n)。算法的实现可以在merge函数中定义临时数组，也可以在一开始就定义一个临时数组。如果在merge函数中定义临时数组，按照递归的时间复杂度分析方法，空间复杂度就是nlog(n)，但实际不是这样的。

实际上，递归代码的工具复杂度并不能像时间复杂度那样累加。刚刚我们忘记了最重要的一点，那就是，尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的空间就被释放掉了。任意时刻，CPU只会有一个函数在执行，也就是只会有一个临时的内存空间在使用。临时内存空间最大也不会超过n个数据的大小，所以空间复杂度是O(n)。

快速排序的原理

快速排序算法，我们习惯性把它称为“快排”。快排利用的也是分治思想。乍看起来，它有点像归并排序，但是思路其实完全不一样。

快排的思想是这样的：如果要排序数组中下标从p到r之间一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点）。

我们遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放到右边，将pivot放到中间。经过这一步骤之后，数组的p到r中间的数据就被分成了三部分，前面p到q-1中间都是小于pivot的，中间是pivot，后面的q+1到r之间的是大于pivot的。

课后思考

现在你有 10 个接口访问日志文件，每个日志文件大小约 300MB，每个文件里的日志都是按照时间戳从小到大排序的。你希望将这 10 个较小的日志文件，合并为 1 个日志文件，合并之后的日志仍然按照时间戳从小到大排列。如果处理上述排序任务的机器内存只有 1GB，你有什么好的解决思路，能“快速”地将这 10 个日志文件合并吗？

先构建十条io流，分别指向十个文件，每条io流读取对应文件的第一条数据，然后比较时间戳，选择出时间戳最小的那条数据，将其写入一个新的文件，然后指向该时间戳的io流读取下一行数据，然后继续刚才的操作，比较选出最小的时间戳数据，写入新文件，io流读取下一行数据，以此类推，完成文件的合并， 这种处理方式，日志文件有n个数据就要比较n次，每次比较选出一条数据来写入，时间复杂度是O（n），空间复杂度是O（1）,几乎不占用内存，这是我想出的认为最好的操作了。