9.5 归并排序

南山隐士 2022年07月31日 55 0

要求掌握归并排序的基本思想和算法实现,针对给定的输入实例,写出归并排序的排序过程。

1.归并及其算法

(1)归并

将两个分别有序的序列合并成一个新的有序序列:

1 3 6 9 10

2 4 7 8

1 2 3 4 6 7 8 9 10

(2)归并算法的描述(下标指示法)及演示

两个有序序列存放在一维数组a中,设下标变量i,j 的初始值分别是两个序列的第一个元素的下标。

存放归并结果序列的数组order,下标变量k的初始值是order第一个元素的下标,设初值为1。

比较a[i]和a[j],若:

     a[i] <= a[j],则a[i]存入order[k], i++ ;k++ ;

     否则:

a[j]存入order[k],j++;k++;重复上述步骤,直至两个序列为空或其中一个序列为空,再把另一个序列的剩余部分依次放置于order数组的尾部 。

例如序列:1,12,13 和 2,14,25,40,50 的归并过程如图9-6所示。


图9‑­­­6 两个有序序列的归并

(3)归并算法

【算法9-8】 两个有序序列的归并

/已有两个记录序列分别存放在a[s],a[s+1],...,a[m]和a[m+1],a[m+2],...,a[n]中,它们已经是按记录的关键字有序,归并上述两个序列, 结果存放到b[s],b[s+1],...b[n]中/

void merge(NODE a[],int s,int m,int n,NODE order[])

{

int i=s,j=m+1,k=s; /初始化下标变量/

while((i<=m)&&(j<=n)) /直到至少一个序列被取完才结束循环/

if(a[i].key<=a[j].key)

order[k++]=a[i++];

else

order[k++]=a[j++]; /通过比较取小者存入结果数组/

if(i>m)

while(j<=n)

  order[k++]=a[j++];       /*拷贝剩余元素到结果数组尾部*/

else

while(i<=m)

  order[k++]=a[i++];

}

2.归并排序

归并排序(Merging Sort)是基于两个有序序列归并的一种排序算法,设待排序的序列有n 个记录,这n个记录可以看成是n个有序序列,可以每两个一组,分别进行两个长度为1的有序序列的归并,称它为(1,1)归并,这样原序列就成为若干个长度为2的有序序列(当元素个数为奇数时也可能有长度为1的有序序列,程序将另行处理)。再把长度为2的相邻的子序列每两个一组,进行(2,2)归并,得到若干个长度为4的有序序列。(也可能有长度小于4的有序序列,程序另行处理),接着进行(4,4)归并•••最后得到排好序的长度为n的序列。称上述过程中的一次归并为一趟归并。

例如有一组记录的关键子序列(30,25,45,15,60,90,20,60),采用归并排序算法对其排序,排序过程如图9-7所示:


图9-7 归并排序示例

【算法9-9】 一趟归并排序算法

/把a[0],a[1],....,a[n-1]中的记录序列按关键字进行一趟归并,其中每个子序列长度为s的(s,s)归并,结果存入数组order中/

mergepass(NODE a[],NODE order[],int s,int n)

{

int i=0;

while(i+2*s-1<=n-1)

/s为一趟归并中子序列的长度,在划分中只要够两个子序列就继续归并/

{

merge(a,i,i+s-1,i+2*s-1,order);

/*i和i+s-1分别为第一个序列开始和终止下标,i+2*s-1为第二个序列的终止下标,进行两个

 序列的归并*/

i=i+2*s;            /*下一段两个子序列的起始下标*/

}

if(i+s

merge(a,i,i+s-1,n-1,order);/*最后两个子序列中有一个长度不足s*/

else

while(i

  order[i++]=a[i++];   /*最后只剩下一个长度〈=s的子序列,直接拷贝到结果数组中*/

}

在一趟归并排序算法的基础上,就能完成对长度为n的整个序列的归并排序,具体做法是逐次进行(1,1)、(2,2)、(4,4)等归并,最终得到长度为n的有序序列。值得注意的是在一趟归并排序算法中作为形式参数的两个数组,一个是原始数组a,另一个是一趟归并后的结果order,在调用时,如果相应于它们的实参分别是数组a1和a2,则下一趟归并要把a2作为原始数组,a1作为结果数组,这样交替使用。

【算法9-10】 归并排序算法

/对存储在数组c1中,长度为n的记录序列按关键字进行归并排序,结果存放于数组c1中/

mergesort(NODE c1[],int n)

{

int i,s=1; /s中存放每一趟两两归并时,每个子序列的长度/

NODE c2[MAX]; /*MAX表示数组c2有足够大的长度,数组c1,c2轮换着作为原始

                 序列和一趟归并后的结果序列*/

while(s

{

mergepass(c1,c2,s,n); /*奇数次一趟归并后,结果存放于c2中*/

s=s*2;           /*每进行一趟归并子序列长度加倍*/

if(s

/*子序列长度不超过n,进行偶数次一趟归并,c2作为原始序列,结果存放于c1中*/

{

  mergepass(c2,c1,s,n);

  s=s*2;

}

else           /*如果子序列长度已等于n,证明已排序结束,且没有进行偶数次一趟

              归并,此时结果在C2中,从c2中把数据拷贝到c1中*/

{

  for(i=1;i<=n;i++)

  c1[i]=c2[i];

}

}

}

归并排序的时间复杂度是O(nlog2n),是一种稳定的排序方法。

例:已知序列{10,18,4,3,6,12,1,9,15,8},给出用归并排序法对序列作升序排列时的每一趟结果(n为偶数)。

初始:10,18,4,3,6,12,1,9,15,8

[10,18] [3,4 ] [6,12] [1,9 ] [8,15]

[3,4,10,18] [1,6,9,12] [8,15]

最后只剩下长度<= s的一个子序列

[1,3,4,6,9,10,12,18] [8,15]

两个子序列中只有一个长度不足

[1,3,4,6,8,9,12,15,18]
Last Updated: 2022/07/31 23:28:02
9小结 9.4 选择排序