算法之排序(中)

上一篇文章说了时间复杂度为O(n2)的冒泡、插入和选择三个排序方式，它们只适合在数据规模比较小的时候，接下来要说的是两个时间复杂度为O(nlogn)的算法，归并排序和快速排序，它们比较适合在大规模数据的时候使用，相比于前面的三个算法就更加常用。

首先来看归并排序（Merge Sort）

归并排序的操作还是比较简单的，它是将数组从中间分割为前后两部分，然后再将每一部分分割，直到分割到不能分为止，然后将数值两两排序合并，不断合并到最初的数组，就完成了排序的操作，它的示例图是这样的

归并排序使用的是分治思想，分而治之，也就是将大问题不断的分解，分解成一个个小问题，小问题都解决了，那大问题也就都解决了，这个跟前面说的递归是特别像的，分治是一种处理问题的思想，递归是具体的技巧，分治算法一般都是用递归来实现的。

既然是使用递归来实现的，那我们就要找到它的通用递归公式和递归终止条件，首先我们假设第一个数值用p表示，最后一个数值用r表示，既然要将数组从中间分割，那每次分割的下标就为q=(p+r)/2，即数组就分为了两段(p,q)和(q+1,r)。

那递归终止条件又该怎么定义？我们来看什么时候是我们需要截至的，当数组分解成单个字符的时候就停止了，那这个时候开始结束符号将一致，所以只需要在p>=r时结束就可以了。

分解结束之后就需要返回进行合并了，这个时候我们可以使用两个变量来帮助我们进行识别，这里用i和j两个变量来进行说明，将i和j分别指向(p,q)和(q+1,r)的第一个元素，同时比较这两个元素的大小，如果ai<aj，就将ai放到一个临时数组中，并将i后移一位；否则就将aj放到临时数组中，并将j后移一位，最后将临时数组拷贝回我们的数组就完成了排序操作。

说了这么多理解起来也比较困难，有一句话就很符合现在的情况，Talk is cheap. Show me the code（ 不要多BB,放码过来吧 ），代码在后一片文章在给出来。

那归并排序是不是原地排序算法呢，由于归并排序在每次合并数据的时候都需要额外申请一个空间来存放，在合并完成之后将会被释放掉，并且在任意时刻，CPU只会有一个函数在执行，也就只有一个临时的内存空间在使用，临时空间最大也超不过数据总和n，所以空间复杂度为O(n)，不是一个原地排序算法。

在合并过程中，如果(p,q)、(q+1,r)中存在相同的元素，那我们就可以先把(p,q)中的元素先放入到临时空间中，所以归并排序是一个稳定的排序算法。

接下来，我们来看快速排序（Quicksort），简称“快排”，它也是利用分治思想，虽然看起来跟归并排序有点像，但是它们的思路是完全不一样的。

快速排序是在p到r中任意选择一个pivot（分区点），然后遍历p到r的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，这样就将数组分成了三个区域，p到q-1是小于 pivot 的，q+1到r是大于 pivot 的，中间q是 pivot 。

然后不断的分治，直到区间缩小为1，所以它的递归终止条件也是p>=r。

在选取 pivot 的时候，一般选择最后一个数值，选择中间的数值作为 pivot 后，还需要将它移动到头或尾的位置，如果我们在进行分区的时候，不考虑空间大小的因素的话，分区操作其实是非常好写的，每一次分区都新申请两个空间，将小于 pivot 的放到一个空间，将大于 pivot 的放到另一个空间，然后再将两个空间合起来拷贝回前面的数组空间，这样的话快排就不是原地排序算法了，所以我们采取另外一种比较巧妙的办法。

这个操作有点类似上一篇文章中的选择排序，我们通过一个变量i，把数组分为前后两个区域，用选择排序中的叫法，前面是已排序区间，后面是未排序区间，我们每次都将未排序区间中的一个数值与 pivot 进行比较，如果小于 pivot 就将它放到已排序区间的末尾，也就是变量i所指向的位置，这个时候我们采取数组中用到的数据交换的方式，将需要调动的数据与i所指位置交换，这样涉及到的操作也就仅仅是数值交换的问题了，空间复杂度也就变成了O(1)，快速排序也就是一个原地排序算法了。

同时也因为其中直接使用了数据交换的方式，他也就改变了数据原来的顺序，也就不是一个稳定的排序算法了。

那快速排序和归并排序的区别到底在哪里，它们在于归并排序是自下而上的，先处理子问题，然后再合并；快速排序是自上而下的，先分区，然后再处理子问题。

参考文档

极客时间-数据结构与算法之美