归并排序算法.pdf

归并排序算法:C语言算法之归并排序
疯狂代码 / ĵ:http:/
排序后两种排序思路方法中都没有使用链表为了能和前面讨论过排序作比较归并排序必须用个
a来存储元素集合E并在a中返回排序后元素序列为此按照下述过程来对图14-6伪代码进行细化:当集合E被化分成
两个子集合时可以不必把两个子集合元素分别复制到A和B中只需简单地在集合E中保持两个子集合左右边界即
可接下来对a中序列进行排序并将所得到排序序列归并到个新b中最后将它们复制到a中图14-6改进版见图14-7






template

MergeSort(Ta,left,right)

{//对a[left:right]中元素进行排序

(left<right){//至少两个元素

i=(left+right)/2;//中心位置

MergeSort(a,left,i);

MergeSort(a,i+1,right);

Merge(a,b,left,i,right);//从a合并到b

Copy(b,a,left,right);//结果放回a

}

}图14-7分而治的排序算法改进



可以从很多方面来改进图14-7性能例如可以容易地消除递归如果仔细地检查图14-7中就会发现其中递归只是简
单地重复分割元素序列直到序列长度变成1为止当序列长度变为1时即可进行归并操作这个过程可以用n为2幂来
很好地描述长度为1序列被归并为长度为2有序序列；长度为2序列接着被归并为长度为4有序序列；这个过程不
断地重复直到归并为长度为n序列图14-8给出n=8时归并(和复制)过程方括号表示个已排序序列首和尾



序列[8][4][5][6][2][1][7][3]

归并到b[48][56][12][37]

复制到a[48][56][12][37]

归并到b[4568][1237]

复制到a[4568][1237]

归并到b[12345678]

复制到a[12345678]

图14-8归并排序例子



另种 2路归并排序算法是这样:首先将每两个相邻大小为1子序列归并然后对上次归并所得到大小为2子序列进行
相邻归并如此反复直至最后归并到个序列归并过程完成通过轮流地将元素从a归并到b并从b归并到a可以虚拟地
消除复制过程 2路归并排序算法见14-3

14-3 2路归并排序

templatevoidMergeSort(Ta,n)

{//使用归并排序算法对a[0:n-1]进行排序

T*b=T[n];

s=1;//段大小

while(s<n){

MergePass(a,b,s,n);//从a归并到b

ss;

MergePass(b,a,s,n);//从b归并到a

ss;

}

}