合并排序算法思想

‘壹’ 归并排序

先考虑一个简单的问题：如何在线性的时间内将两个有序队列合并为一个有序队列（并输出）？

A队列：1 3 5 7 9
B队列：1 2 7 8 9

看上面的例子，AB两个序列都是已经有序的了。在给出数据已经有序的情况下，我们会发现很多神奇的事，比如，我们将要输出的第一个数一定来自于这两个序列各自最前面的那个数。两个数都是1，那么我们随便取出一个（比如A队列的那个1）并输出：

A队列：1 3 5 7 9
B队列：1 2 7 8 9
输出：1

注意，我们取出了一个数，在原数列中删除这个数。删除操作是通过移动队首指针实现的，否则复杂度就高了。
现在，A队列打头的数变成3了，B队列的队首仍然是1。此时，我们再比较3和1哪个大并输出小的那个数：

A队列：1 3 5 7 9
B队列：1 2 7 8 9
输出：1 1

接下来的几步如下：

A队列：1 3 5 7 9 A队列：1 3 5 7 9 A队列：1 3 5 7 9 A队列：1 3 5 7 9
B队列：1 2 7 8 9 ==> B队列：1 2 7 8 9 ==> B队列：1 2 7 8 9 ==> B队列：1 2 7 8 9 ……
输出：1 1 2 输出：1 1 2 3 输出：1 1 2 3 5 输出：1 1 2 3 5 7

我希望你明白了这是怎么做的。这个做法显然是正确的，复杂度显然是线性。

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

[3] [1] [4] [1] [5] [9] [2] [7]
\ / \ / \ / \ /
[1 3] [1 4] [5 9] [2 7]
\ / \ /
[1 1 3 4] [2 5 7 9]
\ /
[1 1 2 3 4 5 7 9]

上图中的每一个“ \ / ”表示的是上文所述的线性时间合并操作。上图用了4行来图解归并排序。如果有n个数，表示成上图显然需要O(logn)行。每一行的合并操作复杂度总和都是O(n)，那么logn行的总复杂度为O(nlogn)。这相当于用递归树的方法对归并排序的复杂度进行了分析。假设，归并排序的复杂度为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)的分治算法。这个结论后面经常用。我们将在计算几何部分举一大堆类似的例子。
如果你第一次见到这么诡异的算法，你可能会对这个感兴趣。分治是递归的一种应用。这是我们第一次接触递归运算。下面说的快速排序也是用的递归的思想。递归程序的复杂度分析通常和上面一样，主定理(Master Theory)可以简化这个分析过程。主定理和本文内容离得太远，我们以后也不会用它，因此我们不介绍它，大家可以自己去查。有个名词在这里的话找学习资料将变得非常容易，我最怕的就是一个东西不知道叫什么名字，半天找不到资料。

归并排序有一个有趣的副产品。利用归并排序能够在O(nlogn)的时间里计算出给定序列里逆序对的个数。你可以用任何一种平衡二叉树来完成这个操作，但用归并排序统计逆序对更方便。我们讨论逆序对一般是说的一个排列中的逆序对，因此这里我们假设所有数不相同。假如我们想要数1, 6, 3, 2, 5, 4中有多少个逆序对，我们首先把这个数列分为左右两段。那么一个逆序对只可能有三种情况：两个数都在左边，两个数都在右边，一个在左一个在右。在左右两段分别处理完后，线性合并的过程中我们可以顺便算出所有第三种情况的逆序对有多少个。换句话说，我们能在线性的时间里统计出A队列的某个数比B队列的某个数大有多少种情况。

A队列：1 3 6 A队列：1 3 6 A队列：1 3 6 A队列：1 3 6 A队列：1 3 6
B队列：2 4 5 ==> B队列：2 4 5 ==> B队列：2 4 5 ==> B队列：2 4 5 ==> B队列：2 4 5 ……
输出： 输出：1 输出：1 2 输出：1 2 3 输出：1 2 3 4

每一次从B队列取出一个数时，我们就知道了在A队列中有多少个数比B队列的这个数大，它等于A队列现在还剩的数的个数。比如，当我们从B队列中取出2时，我们同时知道了A队列的3和6两个数比2大。在合并操作中我们不断更新A队列中还剩几个数，在每次从B队列中取出一个数时把当前A队列剩的数目加进最终答案里。这样我们算出了所有“大的数在前一半，小的数在后一半”的情况，其余情况下的逆序对在这之前已经被递归地算过了。

============================华丽的分割线============================

堆排序(Heap Sort)利用了堆(Heap)这种数据结构（什么是堆？）。堆的插入操作是平均常数的，而删除一个根节点需要花费O(log n)的时间。因此，完成堆排序需要线性时间建立堆（把所有元素依次插入一个堆），然后用总共O(nlogn)的时间不断取出最小的那个数。只要堆会搞，堆排序就会搞。堆在那篇日志里有详细的说明，因此这里不重复说了。

============================华丽的分割线============================

快速排序(Quick Sort)也应用了递归的思想。我们想要把给定序列分成两段，并对这两段分别进行排序。一种不错的想法是，选取一个数作为“关键字”，并把其它数分割为两部分，把所有小于关键字的数都放在关键字的左边，大于关键字的都放在右边，然后递归地对左边和右边进行排序。把该区间内的所有数依次与关键字比较，我们就可以在线性的时间里完成分割的操作。完成分割操作有很多有技巧性的实现方法，比如最常用的一种是定义两个指针，一个从前往后找找到比关键字大的，一个从后往前找到比关键字小的，然后两个指针对应的元素交换位置并继续移动指针重复刚才的过程。这只是大致的方法，具体的实现还有很多细节问题。快速排序是我们最常用的代码之一，网上的快速排序代码五花八门，各种语言，各种风格的都有。大家可以随便找一个来看看，我说过了我们讲算法但不讲如何实现。NOIp很简单，很多人NOIp前就背了一个快速排序代码就上战场了。当时我把快速排序背完了，抓紧时间还顺便背了一下历史，免得晚上听写又不及格。
不像归并排序，快速排序的时间复杂度很难计算。我们可以看到，归并排序的复杂度最坏情况下也是O(nlogn)的，而快速排序的最坏情况是O(n^2)的。如果每一次选的关键字都是当前区间里最大（或最小）的数，那么这样将使得每一次的规模只减小一个数，这和插入排序、选择排序等平方级排序没有区别。这种情况不是不可能发生。如果你每次选择关键字都是选择的该区间的第一个数，而给你的数据恰好又是已经有序的，那你的快速排序就完蛋了。显然，最好情况是每一次选的数正好就是中位数，这将把该区间平分为两段，复杂度和前面讨论的归并排序一模一样。根据这一点，快速排序有一些常用的优化。比如，我们经常从数列中随机取一个数当作是关键字（而不是每次总是取固定位置上的数），从而尽可能避免某些特殊的数据所导致的低效。更好的做法是随机取三个数并选择这三个数的中位数作为关键字。而对三个数的随机取值反而将花费更多的时间，因此我们的这三个数可以分别取数列的头一个数、末一个数和正中间那个数。另外，当递归到了一定深度发现当前区间里的数只有几个或十几个时，继续递归下去反而费时，不如返回插入排序后的结果。这种方法同时避免了当数字太少时递归操作出错的可能。

下面我们证明，快速排序算法的平均复杂度为O(nlogn)。不同的书上有不同的解释方法，这里我选用算法导论上的讲法。它更有技巧性一些，更有趣一些，需要转几个弯才能想明白。
看一看快速排序的代码。正如我们提到过的那种分割方法，程序在经过若干次与关键字的比较后才进行一次交换，因此比较的次数比交换次数更多。我们通过证明一次快速排序中元素之间的比较次数平均为O(nlogn)来说明快速排序算法的平均复杂度。证明的关键在于，我们需要算出某两个元素在整个算法过程中进行过比较的概率。
我们举一个例子。假如给出了1到10这10个数，第一次选择关键字7将它们分成了{1,2,3,4,5,6}和{8,9,10}两部分，递归左边时我们选择了3作为关键字，使得左部分又被分割为{1,2}和{4,5,6}。我们看到，数字7与其它所有数都比较过一次，这样才能实现分割操作。同样地，1到6这6个数都需要与3进行一次比较（除了它本身之外）。然而，3和9决不可能相互比较过，2和6也不可能进行过比较，因为第一次出现在3和9，2和6之间的关键字把它们分割开了。也就是说，两个数A(i)和A(j)比较过，当且仅当第一个满足A(i)<=x<=A(j)的关键字x恰好就是A(i)或A(j) （假设A(i)比A(j)小）。我们称排序后第i小的数为Z(i)，假设i<j，那么第一次出现在Z(i)和Z(j)之间的关键字恰好就是Z(i)或Z(j)的概率为2/(j-i+1)，这是因为当Z(i)和Z(j)之间还不曾有过关键字时，Z(i)和Z(j)处于同一个待分割的区间，不管这个区间有多大，不管递归到哪里了，关键字的选择总是随机的。我们得到，Z(i)和Z(j)在一次快速排序中曾经比较过的概率为2/(j-i+1)。
现在有四个数，2,3,5,7。排序时，相邻的两个数肯定都被比较过，2和5、3和7都有2/3的概率被比较过，2和7之间被比较过有2/4的可能。也就是说，如果对这四个数做12次快速排序，那么2和3、3和5、5和7之间一共比较了12*3=36次，2和5、3和7之间总共比较了8*2=16次，2和7之间平均比较了6次。那么，12次排序中总的比较次数期望值为36+16+6=58。我们可以计算出单次的快速排序平均比较了多少次：58/12=29/6。其实，它就等于6项概率之和，1+1+1+2/3+2/3+2/4=29/6。这其实是与期望值相关的一个公式。
同样地，如果有n个数，那么快速排序平均需要的比较次数可以写成下面的式子。令k=j-i，我们能够最终得到比较次数的期望值为O(nlogn)。

这里用到了一个知识：1+1/2+1/3+...+1/n与log n增长速度相同，即∑(1/n)=Θ(log n)。它的证明放在本文的最后。

在三种O(nlogn)的排序算法中，快速排序的理论复杂度最不理想，除了它以外今天说的另外两种算法都是以最坏情况O(nlogn)的复杂度进行排序。但实践上看快速排序效率最高（不然为啥叫快速排序呢），原因在于快速排序的代码比其它同复杂度的算法更简洁，常数时间更小。

快速排序也有一个有趣的副产品：快速选择给出的一些数中第k小的数。一种简单的方法是使用上述任一种O(nlogn)的算法对这些数进行排序并返回排序后数组的第k个元素。快速选择(Quick Select)算法可以在平均O(n)的时间完成这一操作。它的最坏情况同快速排序一样，也是O(n^2)。在每一次分割后，我们都可以知道比关键字小的数有多少个，从而确定了关键字在所有数中是第几小的。我们假设关键字是第m小。如果k=m，那么我们就找到了答案——第k小元素即该关键字。否则，我们递归地计算左边或者右边：当k<m时，我们递归地寻找左边的元素中第k小的；当k>m时，我们递归地寻找右边的元素中第k-m小的数。由于我们不考虑所有的数的顺序，只需要递归其中的一边，因此复杂度大大降低。复杂度平均线性，我们不再具体证了。
还有一种算法可以在最坏O(n)的时间里找出第k小元素。那是我见过的所有算法中最没有实用价值的算法。那个O(n)只有理论价值。

============================华丽的分割线============================

我们前面证明过，仅仅依靠交换相邻元素的操作，复杂度只能达到O(n^2)。于是，人们尝试交换距离更远的元素。当人们发现O(nlogn)的排序算法似乎已经是极限的时候，又是什么制约了复杂度的下界呢？我们将要讨论的是更底层的东西。我们仍然假设所有的数都不相等。
我们总是不断在数与数之间进行比较。你可以试试，只用4次比较绝对不可能给4个数排出顺序。每多进行一次比较我们就又多知道了一个大小关系，从4次比较中一共可以获知4个大小关系。4个大小关系共有2^4=16种组合方式，而4个数的顺序一共有4!=24种。也就是说，4次比较可能出现的结果数目不足以区分24种可能的顺序。更一般地，给你n个数叫你排序，可能的答案共有n!个，k次比较只能区分2^k种可能，于是只有2^k>=n!时才有可能排出顺序。等号两边取对数，于是，给n个数排序至少需要log2(n!)次。注意，我们并没有说明一定能通过log2(n!)次比较排出顺序。虽然2^5=32超过了4!，但这不足以说明5次比较一定足够。如何用5次比较确定4个数的大小关系还需要进一步研究。第一次例外发生在n=12的时候，虽然2^29>12!，但现已证明给12个数排序最少需要30次比较。我们可以证明log(n!)的增长速度与nlogn相同，即log(n!)=Θ(nlogn)。这是排序所需要的最少的比较次数，它给出了排序复杂度的一个下界。log(n!)=Θ(nlogn)的证明也附在本文最后。
这篇日志的第三题中证明log2(N)是最优时用到了几乎相同的方法。那种“用天平称出重量不同的那个球至少要称几次”一类题目也可以用这种方法来解决。事实上，这里有一整套的理论，它叫做信息论。信息论是由香农(Shannon)提出的。他用对数来表示信息量，用熵来表示可能的情况的随机性，通过运算可以知道你目前得到的信息能够怎样影响最终结果的确定。如果我们的信息量是以2为底的，那信息论就变成信息学了。从根本上说，计算机的一切信息就是以2为底的信息量(bits=binary digits)，因此我们常说香农是数字通信之父。信息论和热力学关系密切，比如熵的概念是直接从热力学的熵定义引申过来的。和这个有关的东西已经严重偏题了，这里不说了，有兴趣可以去看《信息论与编码理论》。我对这个也很有兴趣，半懂不懂的，很想了解更多的东西，有兴趣的同志不妨加入讨论。物理学真的很神奇，利用物理学可以解决很多纯数学问题，我有时间的话可以举一些例子。我他妈的为啥要选文科呢。
后面将介绍的三种排序是线性时间复杂度，因为，它们排序时根本不是通过互相比较来确定大小关系的。

附1：∑(1/n)=Θ(log n)的证明
首先我们证明，∑(1/n)=O(log n)。在式子1+1/2+1/3+1/4+1/5+...中，我们把1/3变成1/2，使得两个1/2加起来凑成一个1；再把1/5,1/6和1/7全部变成1/4，这样四个1/4加起来又是一个1。我们把所有1/2^k的后面2^k-1项全部扩大为1/2^k，使得这2^k个分式加起来是一个1。现在，1+1/2+...+1/n里面产生了几个1呢？我们只需要看小于n的数有多少个2的幂即可。显然，经过数的扩大后原式各项总和为log n。O(logn)是∑(1/n)的复杂度上界。
然后我们证明，∑(1/n)=Ω(log n)。在式子1+1/2+1/3+1/4+1/5+...中，我们把1/3变成1/4，使得两个1/4加起来凑成一个1/2；再把1/5,1/6和1/7全部变成1/8，这样四个1/8加起来又是一个1/2。我们把所有1/2^k的前面2^k-1项全部缩小为1/2^k，使得这2^k个分式加起来是一个1/2。现在，1+1/2+...+1/n里面产生了几个1/2呢？我们只需要看小于n的数有多少个2的幂即可。显然，经过数的缩小后原式各项总和为1/2*logn。Ω(logn)是∑(1/n)的复杂度下界。

附2：log(n!)=Θ(nlogn)的证明
首先我们证明，log(n!)=O(nlogn)。显然n!<n^n，两边取对数我们得到log(n!)<log(n^n)，而log(n^n)就等于nlogn。因此，O(nlogn)是log(n!)的复杂度上界。
然后我们证明，log(n!)=Ω(nlogn)。n!=n(n-1)(n-2)(n-3)....1，把前面一半的因子全部缩小到n/2，后面一半因子全部舍去，显然有n!>(n/2)^(n/2)。两边取对数，log(n!)>(n/2)log(n/2)，后者即Ω(nlogn)。因此，Ω(nlogn)是log(n!)的复杂度下界。

今天写到这里了，大家帮忙校对哦
Matrix67原创
转贴请注明出处

‘贰’ 常见的几种排序算法总结

对于非科班生的我来说，算法似乎对我来说是个难点，查阅了一些资料，趁此来了解一下几种排序算法。
首先了解一下，什么是程序

关于排序算法通常我们所说的往往指的是内部排序算法，即数据记录在内存中进行排序。
排序算法大体可分为两种：
一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。
另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等

冒泡排序它重复地走访过要排序的元素，一次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。

选择排序类似于冒泡排序，只不过选择排序是首先在未排序的序列中找到最小值（最大值），放到序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾，以此类推，直到所有元素均排序完毕。

插入排序比冒泡排序和选择排序更有效率，插入排序类似于生活中抓扑克牌来。
插入排序具体算法描述，以数组[3, 2, 4, 5, 1]为例。

前面三种排序算法只有教学价值，因为效率低，很少实际使用。归并排序（Merge sort）则是一种被广泛使用的排序方法。
它的基本思想是，将两个已经排序的数组合并，要比从头开始排序所有元素来得快。因此，可以将数组拆开，分成n个只有一个元素的数组，然后不断地两两合并，直到全部排序完成。
以对数组[3, 2, 4, 5, 1] 进行从小到大排序为例，步骤如下：

有了merge函数，就可以对任意数组排序了。基本方法是将数组不断地拆成两半，直到每一半只包含零个元素或一个元素为止，然后就用merge函数，将拆成两半的数组不断合并，直到合并成一整个排序完成的数组。

快速排序（quick sort）是公认最快的排序算法之一，有着广泛的应用。
快速排序算法步骤

参考：
常用排序算法总结(一)
阮一峰-算法总结

‘叁’ 归并排序算法原理

.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono"弊租培,"lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px} 排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内型答部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是归并排序算法：

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）； 自下租唯而上的迭代；
在《数据结构与算法 JavaScript 描述》中，作者给出了自下而上的迭代方法。但是对于递归法，作者却认为：

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

然而，在 JavaScript 中这种方式不太可行，因为这个算法的递归深度对它来讲太深了。

说实话，我不太理解这句话。意思是 JavaScript 编译器内存太小，递归太深容易造成内存溢出吗？还望有大神能够指教。

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。
2. 算法步骤
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

设定两个指针，最初位置分别为两个已经排序序列的起始位置；

比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

重复步骤 3 直到某一指针达到序列尾；

将另一序列剩下的所有元素直接复制到合并序列尾。
3. 动图演示
代码实现 JavaScript 实例 function mergeSort ( arr ) {   // 采用自上而下的递归方法
    var len = arr. length ;
    if ( len

‘肆’ 归并排序算法是什么

归并排序算法定义如下：

归并排序算法就是利用分治思想将数组分成两个小组A，B，再将A，B小组各自分成两个小组，依次类推，直到分出来的小组只有一个数据时，可以认为这个小组已经是有序的了，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数组，再合并数组，就完成了归并排序。

归并排序算法特点：

由于归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结果以及递归时深度为log2n(2为底)的栈空间。

因此空间复杂度为O(n+logn)，Merge函数中if(SR[i] < SR[j])语句说明需要两两比较，不存在跳跃，因此归并排序是一种稳定的排序算法，归并排序是一种比较占用内存，但却效率高且稳定的算法。

‘伍’ 1,请简述归并排序算法的基本思想;假设有如下数列:50 ,31, 28, 19, 56, 45, 11, 8,

把待排序的数组分成两组
递归排序锋厅每个数组使数组有序
合并两个有序数组
50 ,31, 28, 19, 56, 45, 11, 8,
每个数单独作为一组有序
一次合并
31 50 19 28 45 56 8 11
二次合枣伏并
19 28 31 50 8 11 45 56
三次银岩隐合并
8 11 19 28 31 45 50 56

‘陆’ 归并排序的算法原理是什么

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，归并排序将两个已排序的表合并成一个表。
归并排序基本原理

通过对若干个有序结点序列的归并来实现排序。
所谓归并是指将若干个已排好序的部分合并成一个有序的部分。

归并排序基本思想

设两个有序的子序列(相当于输入序列)放在同一序列中相邻的位置上：array[low..m]，array[m + 1..high]，先将它们合并到一个局部的暂存序列 temp (相当于输出序列)中，待合并完成后将 temp 复制回 array[low..high]中，从而完成排序。

在具体的合并过程中，设置 i，j 和 p 三个指针，其初值分别指向这三个记录区的起始位置。合并时依次比较 array[i] 和 array[j] 的关键字，取关键字较小（或较大）的记录复制到 temp[p] 中，然后将被复制记录的指针 i 或 j 加 1，以及指向复制位置的指针 p加 1。重复这一过程直至两个输入的子序列有一个已全部复制完毕(不妨称其为空)，此时将另一非空的子序列中剩余记录依次复制到 array 中即可。

‘柒’ 军刀合并算法是什么

军刀合并算法（Mergesort）是一种基友拍于分治思想的常见排序悉告衫算法。它将待排序的数组从中间分成两个子数组，然后对每个子数组递归地应用归并排序算法，最终将两个有序子数组合并为一个有序的数组。
具体实现过程如下：
1.将待排序数组从中间分成两个子数组；
2.对左右两个子数组进行递归操作，直到每个子数组只剩下一个元素；
3.将相邻的子数组进行合并，形成新的有序子数组，直到整个数组排好序为止。
该算法时间复睁腔杂度为O(nlogn)，虽然时间复杂度较好，但空间复杂度较高，需要额外的存储空间来存储临时数据。

‘捌’ 常见排序算法归纳

排序算法一般分类：

比较两个相邻的元素，将值大的元素交换至右端。

依次比较两个相邻的数，将小数放到前面，大数放到后面

即在第一趟：首先比较第1个数和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此一直继续下去，直到比较最后两个数，将小数放前，大数放后。然后重复第一趟步骤，直到所有排序完成。

第一趟比较完成后，最后一个数一定是数组中最大的一个数，所以第二趟比较的时候最后一个数不参与比较。

第二趟完成后，倒数第二个数也一定是数组中第二大的数，所以第三趟比较的时候最后两个数不参与比较。

依次类推......

输出结果：

冒泡排序的优点： 每进行一趟排序，就会少比较一次，因为每进行一趟排序都会找出一个较大值。如上例：第一趟比较之后，排在最后的一个数一定是最大的一个数，第二趟排序的时候，只需要比较除了最后一个数以外的其他的数，同样也能找出一个最大的数排在参与第二趟比较的数后面，第三趟比较的时候，只需要比较除了最后两个数以外的其他的数，以此类推……也就是说，没进行一趟比较，每一趟少比较一次，一定程度上减少了算法的量。

用时间复杂度来说：

从一个数组中随机选出一个数N，通过一趟排序将数组分割成三个部分，1、小于N的区域 2、等于N的区域 3、大于N的区域，然后再按照此方法对小于区的和大于区分别递归进行，从而达到整个数据变成有序数组。

如下图：

假设最开始的基准数据为数组的第一个元素23，则首先用一个临时变量去存储基准数据，即 tmp=23 ，然后分别从数组的两端扫描数组，设两个指示标志： low 指向起始位置， high 指向末尾。

首先从后半部分开始，如果 扫描到的值大于基准数据 就让 high-1 ，如果发现有元素比该基准数据的值小，比如上面的 18 <= tmp ，就让 high位置的值赋值给low位置 ，结果如下：

然后开始从前往后扫描，如果扫描到的值小于基准数据就让 low+1 ，如果发现有元素大于基准数据的值，比如上图 46 >= tmp ，就再将 low 位置的值赋值给 high 位置的值，指针移动并且数据交换后的结果如下：

然后再开始从前往后遍历，直到 low=high 结束循环，此时low或者high的下标就是 基准数据23在该数组中的正确索引位置 ，如下图所示：

这样一遍遍的走下来，可以很清楚的知道，快排的本质就是把比基准数据小的都放到基准数的左边，比基准数大的数都放到基准数的右边，这样就找到了该数据在数组中的正确位置。

然后采用递归的方式分别对前半部分和后半部分排序，最终结果就是自然有序的了。

输出结果：

最好情况下快排每次能恰好均分序列，那么时间复杂度就是O(nlogn)，最坏情况下，快排每次划分都只能将序列分为一个元素和其它元素两部分，这时候的快排退化成冒泡排序，时间复杂度为O(n^2)。

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。

将一个数据插入到 已经排好序的有序数据 中

第一趟排序：

用数组的第二个数与第一个数( 看成是已有序的数据 )比较

第二趟排序：

用数组的第三个数与已是有序的数据 {2,3} (刚才在第一趟排的)比较

在第二步中：

...

后面依此类推

输出结果：

选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

举例：数组 int[] arr={5,2,8,4,9,1}

第一趟排序 ： 原始数据： 5 2 8 4 9 1

最小数据1，把1放在首位，也就是1和5互换位置，

排序结果： 1 2 8 4 9 5

第二趟排序 ：

第1以外的数据 {2 8 4 9 5} 进行比较，2最小，

排序结果： 1 2 8 4 9 5

第三趟排序 ：

除 1、2 以外的数据 {8 4 9 5} 进行比较，4最小，8和4交换

排序结果： 1 2 4 8 9 5

第四趟排序 :

除第 1、2、4 以外的其他数据 {8 9 5} 进行比较，5最小，8和5交换

排序结果： 1 2 4 5 9 8

第五趟排序：

除第 1、2、4、5 以外的其他数据 {9 8} 进行比较，8最小，8和9交换

排序结果： 1 2 4 5 8 9

输出结果：

归并排序（merge sort）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

比如我们对 [8,4,5,7,1,3,6,2] 这个数组进行归并排序，我们首先利用分治思想的“分”将数组拆分。

输出结果：

‘玖’ 求归并排序算法！

归并排序。

1.这里，在把数组暂时复制到临时数组时，将第二个子数组中的顺序颠倒了一下。这样，两个子数组从两端开始处理，使得他们互相成为另一个数组的“检查哨”。 这个方法是由R.Sedgewick发明的归并排序的优化。

2.在数组小于某一阀值时，不继续归并，而直接使用插入排序，提高效率。这里根据Record的结构，将阀值定位 16。

#define THRESHOLD 16

typedef struct _Record{
int data; //数据
int key; //键值
}Record;

//供用户调用的排序 函数
void Sort(Record Array[], Record TempArray, int left, int right){
TwoWayMergeSort(Array, TempArray, left, right);
}

//归并排序
void TwoWayMergeSort(Record Array[], Record TempArray[],
int left, int right)
{
if(right <= left) return; //如果只含一个元素，直接返回
if( right-left+1 ){ //如果序列长度大于阀值，继续递归
int middle = (left + right)/2;
Sort(Array, TempArray, left, middle); //对左面进行递归
Sort(Array, TempArray, left, right, middle); //对右面进行递归
Merge(Array, TempArray, left, right, middle); //合并
}
else{
//如果序列长度小于阀值，采用直接插入排序，达到最佳效果
ImproveInsertSorter(&Array[left], right-left+1);
}
}

//归并过程
void Merge(Record Array[], Record TempArray[],
int left, int right, int middle)
{
int index1, index2; //两个子序列的起始位置
int k;

复制左边的子序列
for(int i=1; i<=middle; i++){
TempArray[i] = Array[i];
}

//复制右边的子序列，但顺序颠倒过来
for(int j=1; j<=right-middle; j++){
TempArray[right-j+1] = Array[j+middle];
}

//开始归并
for(index1=left, index2=right, k=left; k<=right; k++){
if(TempArray[index1].key<TempArray[index2].key){
Array[k] = TempArray[index++];
}
else{
Array[k] = TempArray[index2--];
}
}
}

//当长度小于阀值时 使用的直接插入排序的代码
void ImproveInsertSorter(Record Array[], int size){
Record TempRecord; //临时变量

for(int i=1; i<size; i++){
TempRecord = Array[i];
int j = i-1;
//从i开始往前寻找记录i的正确位置
while(j>=0 && TempRecord.key<Array[j].key){
Array[j+1] = Array[j];
j = j-1;
}

Array[j+1] = TempRecord;
}
}

终于敲完了。。。 第一次回答问题， 只是觉得好玩`

‘拾’ 常见算法4、合并(归并)排序 Merge sort

归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

假如如我这里有一组数据，归并排序过程如下：

通俗点来说，就是先分割，再合并。分割的过程中其实可理解为就是以二分法将数组分割成最小单元，然后再按顺序合并起来。

1、Python 3 ：

2、PHP：