本节讲两个时间复杂度为O(nlogn)的排序算法：归并排序和快速排序，它们都用到了分治的思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决，小的子问题解决了，大问题也就解决了。

        这两种排序算法适合大规模的数据排序，比上节课讲的三种排序方法要更常用。

    1归并排序

        归并排序的核心思想是将要排序的数组从中间分成前后两部分，然后对两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。如下图所示：

        分治思想和我们前面讲的递归很像，其实，分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧。（后面再展开来讲分治算法的思想，这节课还是以排序算法为主）

        如何用递归代码来实现归并排序呢？

        1）写出递推公式：merge_sort(p...r)=merge(merge_sort(p...q),merge_sort(q+1...r))

        2）找到终止条件：p>=r

        3）将递推公式翻译成递归代码。

        Merge函数的实现思路：

        代码如下：

        运行结果：

        总结一下：

        第一，归并排序是稳定的排序算法。归并排序稳不稳定关键要看Merge函数，在合并的过程中，如果 A[p…q] 和 A[q+1…r] 之间有值相同的元素，那我们可以像伪代码中那样，先把 A[p…q] 中的元素放入tmp数组，这样就保证了值相同的元素，在合并前后的先后顺序不变。

        第二，归并排序的时间复杂度是O(nlogn)。一个问题a分解为多个子问题b和c，如果我们定义求解a问题的时间是T(a)，求解b、c问题的时间是T(b)和T(c)，那我们就可以得到这样的递推公式：T(a)=T(b)+T(c)+K,其中K等于将两个子问题b、c的结果合并成问题a的结果所消耗的时间。

        我们假设对n个元素进行归并排序需要的时间是 T(n)，那分解成两个子数组排序的时间都是 T(n/2)。我们知道，merge() 函数合并两个有序子数组的时间复杂度是 O(n)。所以，套用前面的公式，归并排序的时间复杂度的计算公式就是：

        我们再进一步分解一下计算过程。

        通过这样一步一步分解推导，我们可以得到 T(n) = 2^kT(n/2^k)+kn。当 T(n/2^k)=T(1) 时，也就是 n/2^k=1，我们得到 k=log2n 。我们将k 值代入上面的公式，得到 T(n)=Cn+nlog2n。如果我们用大 O 标记法来表示的话，T(n) 就等于 O(nlogn)。所以归并排序的时间复杂度是 O(nlogn)。

        归并排序的执行效率与要排序的原始数组的有序成都无关，所以它的时间复杂度是非常稳定的，不管最好情况、最坏情况、还是平均情况，时间复杂度都是O(nlogn)。

        第三，归并排序的空间复杂度是O(n)。归并排序有一个致命的弱点，就是它不是原地排序算法。它在合并两个有序数组为一个有序数组时，需要借助额外的存储空间，但是，尽管每次合并操作都需要申请额外的存储空间，但是在合并完成之后，临时开辟的内存空间就被释放掉了，在任意时刻，CPU只会有一个函数在执行，也就是只会有一个临时的内存空间在使用，而这个临时内存空间最大也不会超过n，所以空间复杂度是O(n)。

    2快速排序

        快排的思想是这样的：如果要排序数组中下标从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之间的数据，直到区间缩小为1，就说明所有的数据都有序了。

        1）递推公式：quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)

        2）终止条件：p >= r

        代码：

        其中的partition()分区函数就是随机选择一个元素作为pivot（一般情况下，可以选择p到r区间的最后一个元素），然后对A[p...r]分区，函数返回pivot的下标。

        如果我们不考虑空间消耗的话，partition() 分区函数可以写得非常简单。我们申请两个临时数组 X 和 Y，遍历 A[p…r]，将小于 pivot 的元素都拷贝到临时数组 X，将大于 pivot 的元素都拷贝到临时数组 Y，最后再将数组X 和数组 Y 中数据顺序拷贝到 A[p…r]。

        但是，如果按照这种思路实现的话，partition() 函数就需要很多额外的内存空间，所以快排就不是原地排序算法了。如果我们希望快排是原地排序算法，那它的空间复杂度得是 O(1)，那 partition() 分区函数就不能占用太多额外的内存空间，我们就需要在 A[p…r] 的原地完成分区操作。

        原地分区函数的实现思路的伪代码，也就是我们最后的实现思路：

        图片版的思路：

        总结一下：

        第一，快速排序是一种原地排序算法。

        第二，快速排序是一种不稳定的排序算法。

        第三，快速排序的时间复杂度是O(nlogn)。如果每次分区操作，都能正好把数组分成大小接近相等的两个小区间，那么快排的时间复杂度递推求解公式跟归并是相同的，但是这种情况是很难实现的。举一个极端情况的例子，如果数组中的数据原来已经是有序的了，比如，1,3,5,7,9，如果我们每次都选择最后一个元素作为pivot，那么每次分区得到的两个区间都是不均等的，我们需要进行大约n次分区操作，才能完成整个快排的过程。每次分区我们平均要扫描大约n/2个元素，这种情况下快排的时间复杂度就退化成了O(n^2)。但是，快排在大部分情况下的时间复杂度都可以做到O(nlogn)，只有在极端情况下才会退化成O(n^2)。

    3归并排序和快速排序有什么区别？

        可以发现，归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排的处理过程是由上到下的，先分区，再处理子问题。归并虽然是稳定的、时间复杂度也和快排相同，但是它不是原地排序算法，因为它的合并函数无法在原地执行。而快排可以实现原地排序，解决了归并排序占用太多内存的问题。

        （遗留了一个怎样找到一个数组中第K大元素的问题，下次复习的时候解决~）

    内容小结

        归并排序和快速排序是两种稍微复杂的排序算法，它们用的都是分治的思想，代码都是通过递归来实现，过程非常相似。理解归并排序的重点是理解递推公式和merge()合并函数，理解快排的重点是理解递推公式和partition()分区函数。归并排序在任何情况下时间复杂度都比较稳定，但它不是原地排序算法，空间复杂度比较高，所以没有快排应用广泛。快排虽然最快情况下的时间复杂度比较高，但是平均情况下时间复杂度和归并排序一样，而且它退化到最坏情况时间复杂度的概率非常小，并且有避免的办法。

        戳这里查看源代码。