从零开始学算法：十种排序算法介绍(中)

《从零开始学算法：十种排序算法介绍(中)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、从零开始学算法：十种排序算法介绍（中）ProgramImpossible

2、2007-04-0613:52

3、15Comments

4、本文内容遵从CC版权协议转载请注明出自matrix67.com    本文被华丽的分割线分为了四段。对于O(nlogn)的排序算法，我们详细介绍归并排序并证明归并排序的时间复杂度，然后简单介绍堆排序，之后给出快速排序的基本思想和复杂度证明。最后我们将证明，O(nlogn)在理论上已经达到了最优。学过OI的人一般都学过这些很基础的东西，大多数OIer们不必看了。为了保持系列文章的完整性，我还是花时间写了一下。    首先考虑一个简单的问题：如何在线性的时间内将两个

5、有序队列合并为一个有序队列（并输出）？A队列：13579B队列：12789    看上面的例子，AB两个序列都是已经有序的了。在给出数据已经有序的情况下，我们会发现很多神奇的事，比如，我们将要输出的第一个数一定来自于这两个序列各自最前面的那个数。两个数都是1，那么我们随便取出一个（比如A队列的那个1）并输出：A队列：13579B队列：12789输出：1    注意，我们取出了一个数，在原数列中删除这个数。删除操作是通过移动队首指针实现的，否则复杂度就高了。    现在，A队列打头的数变成3了，B队列的队首仍然是1。此时，我们再比较3和1哪个大并输出小的那个数：A队列：13579B队列：1

6、2789输出：11    接下来的几步如下：A队列：13579        A队列：13579        A队列：13579          A队列：13579B队列：12789  ==>  B队列：12789  ==>  B队列：12789    ==>  B队列：12789    ……输出：112              输出：1123            输出：11235          输出：112357    我希望你明白了这是怎么做的。这个做法显然是正确的，复杂度显然是线性。    归并排序(MergeSort)将会用到上面所说的合并操作。给出一个数列，归并排序

7、利用合并操作在O(nlogn)的时间内将数列从小到大排序。归并排序用的是分治(DivideandConquer)的思想。首先我们把给出的数列平分为左右两段，然后对两段数列分别进行排序，最后用刚才的合并算法把这两段（已经排过序的）数列合并为一个数列。有人会问“对左右两段数列分别排序时用的什么排序”么？答案是：用归并排序。也就是说，我们递归地把每一段数列又分成两段进行上述操作。你不需要关心实际上是怎么操作的，我们的程序代码将递归调用该过程直到数列不能再分（只有一个数）为止。    初看这个算法时有人会误以为时间复杂度相当高。我们下面给出的一个图将用非递归的眼光来看归并排序的实际操作过程，供大

8、家参考。我们可以借助这个图证明，归并排序算法的时间复杂度为O(nlogn)。[3][1][4][1][5][9][2][7]  /    /    /    /[13]  [14]  [59]  [27]      /            /  [1134]      [2579]                /      [11234579]    上图中的每一个“/”表示的是上文所述的线性时间合并操作。上图用了4行来图解归并排序。如果有n个数，表示成上图显然需要O(logn)行。每一行的合并操作复杂度总和都是O(n)，那么logn行的总复杂度为O(nlogn)。这

9、相当于用递归树的方法对归并排序的复杂度进行了分析。假设，归并排序的复杂度为T(n)，T(n)由两个T(n/2)和一个关于n的线性时间组成，那么T(n)=2*T(n/2)+O(n)。不断展开这个式子我们可以同样可以得到T(n)=O(nlogn)的结论，你可以自己试试。如果你能在线性的时间里把分别计算出的两组不同数据的结果合并在一起，根据T(n)=2*T(n/2)+O(n)=O(nlogn)，那么我们就可以构造O(nlogn)的分治算法。这个结论后面经常用。我们将在计算几何部分举一大堆类似的例子。    如果你第一次见到这么诡异的算法，你可能会对这个感兴趣。分治是递归的一种应用。这是我们第一

10、次接触递归运算。下面说的快速排序也是用的递归的思想。递归程序的复杂度分析通常和上面一样，主定理(MasterTheory)可以简化这个分析过程。主定理和本文内容离得太远，我们以后也不会用它，因此我们不介绍它，大家可以自己去查。有个名词在这里的话找学习资料将变得非常容易，我最怕的就是一个东西不知道叫什么名字，半天找不到资料。    归并排序有一个有趣的副产品。利用归并排序能够在O(nlogn)的时间里计算出给定序列里逆序对的个数。你可