归并排序算法论文

归并排序算法解决排序问题

目录

1引言 ...................................................................................................... 2

2.归并排序的基本思想 ........................................................................... 2

3.归并排序算法不同的方式 ................................................................... 3

1.归并排序基本算法 ......................................................................... 3

1.实现过程 .................................................................................. 3

2.性能分析： .............................................................................. 4

2.递归二路归并排序 ......................................................................... 5

1.算法过程 .................................................................................. 5

2.性能分析： .............................................................................. 6

3.归并排序算法的改进算法 ............................................................. 7

1.引理 .......................................................................................... 7

2.应用例子 .................................................................................. 7

3.时间复杂性的分析 ................................................................... 8

4.总结 ...................................................................................................... 9

5.参考文献 .............................................................................................. 9

1引言

从归并排序的概念上进行分析，该算法的思想比 较容易理解，并且也能够直观的感知其实质是利用存储空间的归并。在实现的过程中，可以有多种方法， 画出归并过程示意图后，随即可以得出其算法的代码。但是我们在利用递归思想实现归并排序的教学程中，一定要让学生分清是用递归还是用回归进行的归并，画出图形区分这两种不同的归并过程。通过这一环节，我们不但能够理解稳定的归并排序，而且还让学生认清递归和回归是解决这一问题两种不同的操作过程。

2.归并排序的基本思想

归并排序主要是二路归并排序，它的基本思想是：设n个 数据，初始时把他们看成n个长度为l的有序子数组，然后从 第—个子数组开始，把相邻的子数组两两归并，得到n／2个长 度为2的新的有序子数组(当n为奇数是最后—个新的有序子 数组长度为1)；对这些新的有序子数组再两两归并；如此重复， 直到得到—个长度为n的有序数组为止”。 归并排序有两种实现方法：自顶向下和自底向上，前者定 义是自底向上，

3.归并排序算法不同的方式

1.归并排序基本算法

1.实现过程

当初次理解归并概念的时候，我们可以列举下列 一组数据的归并过程。 例如：

70 83 100 65 10 32 7 65 9

第一次：【70 83】【65 100】【10 32】【7 65】【9】

第二次：【65 70 83 100】【7 10 32 65】【9】

第三次：【7 10 32 65 65 70 83 100】【9】

第四次：【7 9 10 32 65 65 70 83 100】

具体程序代码如下：

函数：void merge(int e[]，int n)

形参说明：e是已知待排序的数组，n是数组中元素的个数，下标从0开始。

void merge(int e[]，int n)

{ int +p=(int+)malloc(Sizeof(int)+n)； ／*开辟一块实现交替归并空间*／

int len=l，f=0； ／*len为归并单元宽度，f是一个标识，实现交替归并*／

while(1en

{

if(f==0)merge pass(e，P，n，len)； ／*交替进行归并*／

else merge．pass(p，e，n，fen);

len*=2； ／*扩大归并单元宽度*／

f=l—f；

}

if(f) ／*将最终结果存放的指定数 据域中*／

for(f=0;f

free(p);

}

Void merge_pass(int e[]，int a[]，int n，int

len)

{

int f _S，s_end；／*f_ s存放即将归并的第一个单元起始下标*／

f _s=0； ／*S_end存放即将归并的第二个单元末下标*／

while(f_s+ len

{ s_end2=f_s+2*len- 1；

if(S end>=n)s end=n一1; ／*确定真正末下 标位置*／

merg_step(e，a，f_s，f_s+len-1，s_end)； ／*实现将两个单元合并*／

f_s=S_end+l;

}

if(f_s

for(；f_s

a[f_s]=e[f S]；

}

void merge step(int e[]，int a[]，int s， int m，int n)

{ ／*实现将两部分单元归并，m为分界点下标，即为第一单元的末下标*／

int i，J，k； k=i=s；J=m+1；

while(i

if(e[i]

else a[k++]=e[j++];

while(i

while(j

2.性能分析：

利用最基本的方法实现归并排序，我们需要利用三个函数，在实现的过程中，程序的可读较高。但是在程序执行的过程中，函数之间需要频繁的进行嵌套调用，数据的交替归并也显得比较麻烦，所以在正确的实现归并算法的基础上，我们引入了递归序列的方法。

2.递归二路归并排序

1.算法过程

利用递归的思想可以掩盖上一方法的频繁嵌套调用，而利用递归的真正目的还可以解决上一方法中数据的交替归并，其方法是它将数组分解成两部分 a[1]，⋯，a[m]和a[m+1]，⋯，a[r]来排序数组a [l]，⋯，a[r]。这两个子数组部分独立排序(通过递归调用)，而且将 生成的有序予文件归并得到最后的所有文件。进而可以得到一个原形化的分治递归程序。在分解过程中我们可以参照下面的数据分解图。 例如：一组数据为：70、83、100、65、10、32、7、65、9共9个元素，由元素的个数我们可以画出二分递归图形。

令函数内部第一次递归调用左半部分，可以得出 归并的过程：

[70 83] 100 65 10 32 7 65 9

[70 83 100] 65 10 32 7 65 9

[70 83 100] [10 65]32 7 65 9

[10 65 70 83 100] 32 7 65 9

[10 65 70 83 100] [7 32] 65 9

[10 65 70 83 100] [7 32] [9 65]

[10 65 70 83 100] [7 9 32 65]

[7 9 10 32 65 65 70 83 100]

Void merge(int sr[],int tr[],int I,int m,int n)

Int j2=m+1,j1=I,k=I;

if(sr[j1]

else tr[k++]=sr[j2++]；

while(j1

tr[k++]=sr[jl++]；

while(j2

tr[k++]=sr[J2++]；

for(k=i；k

sr[k]=tr[k]；

) ·

Void msort(int sr[]，int tr[]，int S，int t)

t int m；

if(s==t)

tr[s]=sr[S]；

else (m=(s+t)／2；

msort(sr，tr，s，m)；

msort(sr，tr，m+l，t)；

merge(sr，tr，s，m，t)；)

)

2.性能分析：

由于本次二路归并排序算法是通过递归划分有序段的，且递归的深度恰好与n个结点的完 全二叉树的深度相同，每个有序段的长度不超过n， 所以两个有序段的合并算法时间数量级不会超过 O(n)。因此，对n个记录进行归并排序的时间性能 T(n)--O(nl092n)。空间上，需要两个与待排序记录序 列空间等长的辅助空间及递归时深度为l092n的栈空 间，因此，总的空间需求为S(n)=O(n+l092n)。

对于每个递归程序都有一个对应的非递归程序，虽然等价，但它可以按不同的顺序来执行。作为分治算法设计思想的一个原型，归并排序的递归与非递归的区别值得我们详细加以研究。

请看递归算法完成的归并序列。如下所示，一个共有9个元素的序列通过如下归并序列进行排序： (n+m表示n个元素与m个元素进行归并)

1+1 2+1 1+1 3+2 1+1 1+1 2+2 5+4

归并的顺序由算法的递归结构决定。但如果采用 的是非递归的方法，各子序列被独立处理，归并则可 以按不同的结合序列来完成。如下显示了第一次的非 递归策略进行排序，其中的归并序列为：

l+1 1+1 1+1 1+1 2+2 2+2 4+4 8+1

在这两种情况下，递归的结合形式是：4个1+1， 1个2+1，1个2+2，1个3+2，1个5+4，而非递归的结合形式是：4个1+1，2个2+2，1个4“，1个 8+1。不但归并的完成顺序不同，而且归并元素的分配也是不同的。递归方法的分配方式是在单方向递归的过程中分配好归并的次序，当单个递归结束后，进 行回归的时候，开始进行真正的归并，在归并的过程 中还要确保右边的归并集合也是有序的，进而在回归的过程中还要进行右边归并集合的归并操作，如此不断地进行，最后则达到有序整体。

3.归并排序算法的改进算法

1.引理

设有p个数据，若用下列方法分组，X ϵGl(tl，2，⋯，P) 满足：t=1+[(x-min)/(max-min)X (p-1)] .其中，min，max是这P个数的最小值和最大值。则对任意xxϵG。yϵG x≤s。 排序的体算法： 设有n个数据序列，m=[n/2]前m个数据的最小值为min， 最大值为max。

(1)若rain=max，则执行(4)。

(2)用引理方法分组。

(3)若组Gl中的元素多于—个，则需要用递归再次调用本排序算法。

(4)对于后m=n-[n/2]个数据，令其最小值为min，最大值为 max，若min=max则执(7)。

(5)用下列方法对该m个数据分组，x∈G。，满足：I=【n，2】+l+[(x—min)/(max-min)]。

(6)若Gi中数据元素多于—个，则利用递归继续排序。

(7)应用两路归并算法，将已有序列的前[n/2]个与n-[n/2]个数据归并成—个长度为n的完整排序序列。

该算法对“散列型”数据序列排序较优，而对“密集型” 数列排序要增加一些存储空间。

2.应用例子

数列X={3．5,7．0,4．3，5．0，10．0．4．0．6．0．4。8,8．0，1．o} 利用该算法排序过程为

(1)n=10，[n/2]=5，在前五个数据中

min--3．5,max=10.0

(2)分组Gl={3．5，4．3，5．0}，G2{}，G3={7．0}，G4={}，G5={10．0}。

递归(2)：n=3，在[n/2]=1的第—个数据中min=3．5，max=3．5， 而单个G2=[3．5]有序。而后3-1=2个数据分组G2=(4．3，5．0)中 min=4．3，max=5．0又进行递归：[2/2]=1得G2=[4．3]，G3=[5．0].归并G1，G2，G3后得有序子序列{3．5，4．3，5．0)，因此可得前五个有 序子序列为f3．5，4．3，5．0,7．0，10．oJ。

(3)n=10的后五个数据中min=1．0，max=8．0递归步骤(1)和 (2)后得G1{1．0}，G2={},G3={4．0}，G4=(4．8，6．0)，G5= {8．0}。 递归步骤(2)：n=2，这两个数据的前一个数据 min=4．8，max=4．8，则这单个数据序列{4．8}有序。 这两个数据后—个数据的max=min=6．0单个{6．0)有序,归并后得有序子序列(1．0，4．0，4．8，6．0，8．0)。

(4)最后得两个长度为5的子序列归并为长度为10的有序序列，此为排序的结果。

3.时间复杂性的分析

命题：n个数据归并排序改进算法的时间复杂性为

T(n)=O(nlogn)

证明：设n个关键字排序的算法所需时间为M(n)，最坏情 况下， [n，2]个数据全部被分配到同一组中，而求出In/21个数据 的最大值和最小值所需的时间是n的线性函数，而两路归并排 序所需的时间也是n的线性函数，因此有：

M(n)=cn+2M([n/2]) 将n个数据项排序所需的时T(n)展开成：

T(n) 1 T(n)=Co n=l

其中C1和c0均为某个正常数，c,n表示递归划jI【d-3第—步所需要的时间，因为M(r1)时间是线性的，所以上述公式可近似地表示为：

T(n)≤cn+2T([11，2]) n>1

T(n)=co n=1 其中C也是某个正常数，由此可得递归方程的解为：

T(n)=cnlogn+O(n) 所以在最坏的情况下，该算法的时间复杂度为

T(n)=O(nlogn)

4.总结

总之，以上几种归并排序的实现形式，是两个基 本的归并排序算法，均以归并两个有序序列为一个有 序序列的运算为基础。这两个算法紧密相关，而且实 际上，当排序元素个数为2的幂时，它们执行着相 同的归并集合，但它们却并不相等，因为归并集合 的结合顺序是不一样的，非递归的方法容易理解， 但是递归的方法更能够加深我们对归并排序实现过 程的理解。

5.参考文献

[1]徐孝凯，贺桂英．《教据结构》[M]．北京：清华大学出版社，2004．

[2]廖荣贵．《数据结构与算法》[M]．北京：清华大学出版社，2004．

[3]现[美] Robert Sedgewick．周良惠译．《c算法》[M]．北京：人民邮电出版社，2004．

[4]王刚．《数据结构》[M]．北京：清华大学出版社，2004．

[5]朱战立．《数据结构》[M]．高等教育出版社，2004．

[6]黄刘生．《数据结构》[M]．经济科学出版社，2000．

[7]严蔚敏，吴伟民．《数据结构》[M]．清华大学出版社，1997．

引证文献

1.罗国明 《冒泡排序动态演示算法设计》[期刊论文]-福建电脑 2013(1)