[摘 要] 本文通过在运行时间和算法原理上，分析、比较插入排序和合并排序算法，在此基础上，吸收两种算法的优势；设计出新的混合排序算法，并对其最后运行时间进行分析。
　　[关键词] 插入排序 合并排序 混合排序
　　
　　一、前言
　　排序就是使一串记录按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。常见的排序算法有：冒泡排序、插入排序、合并排序、快速排序等等，在计算、空间复杂度上各有优劣。本文通过在运行时间和算法原理上，分析、比较插入排序和合并排序算法；在融合两者算法优势上，设计出新的混合排序算法，并对其最后运行时间进行分析。
　　二、插入排序算法
　　插入排序的基本操作就是将一个数据插入到已排好序的有序数列中,从而得到一个新的个数加一的有序数列。
　　用伪代码来表示插入排序为：
　　1、for j=2 to length[A] //length L[A]表示数列的长度
　　2、{key=A[j] //A[j]表示数列中的第j个元素 /* 下面的伪代码降插入A[j]到排好序的数列A[1..j-1]中 */
　　3、i=j-1
　　4、while(i>0 && A[i]>key)
　　5、{A[i+1]=A[i]
　　6、i=i-1}
　　7、A[i+1]=key}
　　该算法总的运行时间是每一条语句执行时间之和T(n)。其第i行语句执行时间ci和次数ni如下表：
　　若时数列正好逆序排列，则遇到该算法的最坏情况。我们需要将A[j]插入数列中，于是对a[1..j-1]中的每个元素比较，因而tj=j。此时
　　因此插入排序的时间花费是一个二次曲线，n值越大，时间消耗就成指数增长，其比较适合n值较小的排序。
　　三、合并排序算法
　　合并排序是采用分治法的典型应用。分治法是将问题划分成n个类似的子问题；用递归方式解决问题，然后合并这些子问题的解合得到原问题的解。合并排序算法是将数列A划分成n个子数列，再对n个子数列排序，再合并n个已经排序的子数列合并起来。其伪代码为：
　　MERGE-SORT(A,p,r){
　　If(p　　q=(p+r)/2 // (p+r)/2 去其整数部分
　　MERGE-SORT(A,p,q)
　　MERGE-SORT(A,q+1,r)
　　MERGE(A,p,q,r)｝}
　　MERGE(A,p,q,r){
　　n1=q-p+1n2=r–q
　　for(i=1;i<=n1;i++)//创建数组 L[1..n1+1]
　　L[i]=A[p+i-1]
　　for(j=1;j<=n2;j++) //创建数组 R[1..n2+1]
　　R[j]=A[q+j]
　　L[n1+1]=∞R[n1+1]=∞ i=1j=1
　　for(k=p;k<=r;k++)
　　if(L[i]<=R[j]){A[k]=L[i]i++}
　　else{A[k]=R[j] j++}}
　　对于合并排序算法，则a和b的值均为2；分解子问题时，只是求出中间位置，所需要时间为常量时间因此D(n)=O(1)，MERGE函数的运行时间为O(n)，则C(n)=O(n)=cn。因而得出合并排序算法的最坏情况下的运行时间为：
　　因而合并排序算法的运行时间为T(n)=O(n lg n)。由于对数函数的增长速度比任何线性函数增长都要慢，因此合并排序算法适合n规模比较大的数列排序。
　　四、混合排序算法
　　插入与合并算法各有所长，插入算法在n规模较小时，运行速度非常快，合并算法在n规模较大时，效率很高。混合排序算法是对两种算法取长补短，其原理是：在合并算法中，当子问题足够小时，使用插入算法来对子问题排序。假设每个子问题为k规模，其算法伪代码为：
　　MERGE-SORT(A,p,r,k){
　　If(r-p>k)｛
　　q=(p+r)/2 // (p+r)/2去其整數部分
　　MERGE-SORT(A,p,q)
　　MERGE-SORT(A,q+1,r)
　　MERGE(A,p,q,r)｝
　　else INSERT-SORT(A，p,r)}
　　INSERT-SORT(A，p,r) //与前面的插入排序伪代码一样
　　MERGE(A,p,q,r)//与前面MERGE函数的伪代码一样
　　在最坏的情况下，n/k个子问题可以在插入排序算法下n/k O(K2)=O(nk)时间下完成。这些子问题最坏情况下可以在O(nlg(n/k))时间内完成。因此混合排序算法在最坏情况下总的运行时间会是O(nk+n lg(n/k))。■
　　注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文