王朝网络
分享
 
 
 

[算法,排序]归并排序算法,实现,比较与测试

王朝other·作者佚名  2006-02-01
宽屏版  字体: |||超大  

[算法,排序]归并排序算法,实现,比较与测试

(Merge Sorting: Implement, Compare and Testing with C)

By EmilMatthew

2005/9/07

归并排序是高级排序算法的一种,所以掌握它是我们继续前进的基础.

要说到归并排序,得谈两件事:

第一件:合并两张已排好序的表(数组),相信这对你来说是一件相当轻松的事情,我们把这个过程叫做merge:

void merge(Type* arr,long left,long mid,long right)

{ //*******attention right=len-1;so,if you want to stand for the len********

//you have to use right+1;

long p1,p2;//pointer for pre half arr and post half arr.

long k;//the pointer for them copy arr

long i;//iterator num

Type* arrCopy;

assertF(arr!=NULL,"in merge,pass in arrList is null\n");

assertF(left<=right,"in merge,left>right\n");

assertF(left<=mid&&mid<=right,"in merge left>mid || mid>right\n");

p1=left;

p2=mid+1;

k=0;

arrCopy=(Type*)malloc(sizeof(Type)*(right+1));

while(p1<=mid&&p2<=right)

{

if(arr[p1]<=arr[p2])

{

arrCopy[k]=arr[p1];

p1++;

k++;

}

else

{

arrCopy[k]=arr[p2];

p2++;

k++;

}

}

assertF((p1==mid+1&&p2!=right+1)||(p1!=mid+1&&p2==right+1),"in merge ,out of while abnormal\n");

if(p1==mid+1)//attenction.

{ for(i=p2;i<=right;i++)

{

arrCopy[k]=arr[i];

k++;

}

}

else if(p2==right+1)

{

for(i=p1;i<=mid;i++)

{

arrCopy[k]=arr[i];

k++;

}

}

/*copy arrCopy data to arr original*/

listArrCopy2(arrCopy,arr,0,left,right-left+1);

free(arrCopy);

}

不难吧. J

2接下来,就要说实现关键了,那又是一个老生常谈的话题---分治思想(Conquer and Divide),主要考虑就是自底向上的进行merge,第一次为每组两个元素的merge,第二次每组4个元素的merge…直至对最后全元素进行一次merge.(全体元素此时已被分成有序的两部分)

a)先说一下递归的版本1:

void mergeSort(Type* inArr,long left,long right)

{ //attention,that here the right=len-1;

long mid;

assertF(inArr!=NULL,"in mergerSort,inArr=null\n");

if(left<right)

{

mid=(left+right)/2;

mergeSort(inArr,left,mid);

mergeSort(inArr,mid+1,right);

merge(inArr,left,mid,right);

}

else return;

}

这个递归的版本和quickSort长得很像(大家的思想一样吗---分治),递归深度优先到底,然后自底向上开始做merge.我们把它叫做Recursive Version1

有个具体的图图,参:

http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.5.1.3.htm

这个递归版本在测试中表现的相当低效(见最后的测试列表),原因在于我在每个merge中大量使用了拷贝数组元素的动作.

于是,对这个拷贝动作做了一些改进,改成在外层的MergeSort中做拷贝,结果速运行效率果然提高不少:

这个改进版的merge和mergeSort(递归版)

b)

void mergeSort2(Type* inArr,long left,long right)

{

//attention,that here the right=len-1;

long mid,len;

Type* bArr;

assertF(inArr!=NULL,"in mergerSort,inArr=null\n");

len=right-left+1;

bArr=(Type*)malloc(sizeof(Type)*len);

if(left<right)

{

mid=(left+right)/2;

mergeSort2(inArr,left,mid);

mergeSort2(inArr,mid+1,right);

merge2(inArr,bArr,left,mid,right);

listArrCopy2(bArr,inArr,0,left,len);

}

free(bArr);

return;

}

/*Recursive Version of mergeSort2*/

void merge2(Type* arr,Type* arrCopy,long left,long mid,long right)

{ //*******attention right=len-1;so,if you want to stand for the len********

//you have to use right+1;

long p1,p2;//pointer for pre half arr and post half arr.

long k;//the pointer for them copy arr

long i;//iterator num

assertF(arr!=NULL,"in merge2,pass in arrList is null\n");

assertF(arrCopy!=NULL,"in merge2,pass in arrList is null\n");

assertF(left<=right,"in merge2,left>right\n");

assertF(left<=mid&&mid<=right,"in merge2, left>mid || mid>right\n");

p1=left;

p2=mid+1;

k=0;

while(p1<=mid&&p2<=right)

{

if(arr[p1]<=arr[p2])

{

arrCopy[k]=arr[p1];

p1++;

k++;

}

else

{

arrCopy[k]=arr[p2];

p2++;

k++;

}

}

assertF((p1==mid+1&&p2!=right+1)||(p1!=mid+1&&p2==right+1),"in merge ,out of while abnormal\n");

if(p1==mid+1)//attenction.

{ for(i=p2;i<=right;i++)

{

arrCopy[k]=arr[i];

k++;

}

}

else if(p2==right+1)

{

for(i=p1;i<=mid;i++)

{

arrCopy[k]=arr[i];

k++;

}

}

}

c)最后给出的是一个非递归的版本,其实,它的想法也是很好理解的,但我实现它却花了不少时间.我看了书,以为理解了,兴奋的合上书,以自己的理解去编制这个非递归版本,可是发现它就是不对,原因在于我对于最后的多余的,不是正好是2^(n-1)的个数的元素处理不到位.

再回过头去看一下书,才发现这里还是很巧妙的,不细加分析一下是很容易出错的.

因为在第j次迭代中,最后需要处理的多余的还没有排好序的剩余元素只有2^j-1至2^j个,所以,在有多余元素的时候,处理的技巧便决定了整个程序正确的关键,而主迭代过程还是好理解的:

/*Unrecursive version of mergeSort*/

void mergeSort3(Type* inArr,long left,long right)

{

long t,i;

assertF(inArr!=NULL,"in mergeSort3,inArr=null\n");

assertF(left<=right,"in mergeSort3,left>right\n");

/*init the data*/

t=1;//currrent width.

while(t<right+1)

{

t*=2;

i=0;//current point

while(i+t-1<=right)

{

merge(inArr,i,i+t/2-1,i+t-1);

i+=t;

}

if(i+t/2-1<right)

{

// assertF(i+t-1>right,"in mergeSort3 adjusting,i+t>=right\n");

merge(inArr,i,i+t/2-1,right);

}

}

}

接下来是对这个mergeSort进行的针对生成的随机数数组进行的排序测试,虽然它们的运算效率书上都有了理论值(O(n*log(n))),但只有你亲自去尝试,才会知道这里面还是有差别的.

这里的三个版本的mergeSort,只有第二个非改进过的递归版的mergeSort表现出了高性能(略低于理论运行效率相同的quickSort)别的版本的mergeSort的运行效率就不敢恭维了,其中的原因,就在一这个mergeSort中包含了大量的数组元素的拷贝(我用的当然已经是十分高效的指针了,但数组元素一多之后还是招架不住啊~~~)

测试结果如下:

MergeSort系列测试(时间单位:s)

MergeSort(Recursive Version1)

10,000个随机数

100,000个随机数

1,000,000个随机数

10,000,000个随机数

test1

0.094

16.047

未做

未做

test2

0.094

18.265

未做

未做

test3

0.079

19.266

未做

未做

MergeSort(Recursive Version2)

10,000个随机数

100,000个随机数

1,000,000个随机数

10,000,000个随机数

test1

0.031

0.234

2.547

27.437

test2

0.016

0.235

2.594

26.422

test3

0.016

0.234

2.532

26.125

MergeSort(UnRecursive Version)

10,000个随机数

100,000个随机数

1,000,000个随机数

10,000,000个随机数

test1

0.094

18.232

未做

未做

test2

0.078

17.375

未做

未做

test3

0.094

15.234

未做

未做

为了便于做个比较,给出上次做的quickSort(参

http://blog.csdn.net/EmilMatthew/archive/2005/09/04/471018.aspx

)的测试结果表,可以看出,第二个改进的递归版本的mergeSort的运行效率还是不错的.(注:quickSort的测试中,没做一万个元素的数组的测试)

Quick Sort

100,000个随机数

1,000,000个随机数

10,000,000个随机数

Test1

0.047000s

0.562000s

10.344000s

Test2

0.047000s

0.578000s

10.860000s

Test3

0.047000s

0.562000s

10.282000s

Random Quick Sort

100,000个随机数

1,000,000个随机数

10,000,000个随机数

Test1

0.218000s

2.578000s

30.812000s

Test2

0.219000s

2.562000s

31.156000s

Test3

0.218000s

2.594000s

30.956000s

我所写的程序的源码下载:

http://free3.e-168.cn/as2forward/downloads/mergeSort.rar

//如果上面这个链接无法响应下载(有可能是被网站给屏蔽掉了),则可使用下载工具(如迅雷等)下载

我所写的程序的源码下载:

http://free3.e-168.cn/as2forward/downloads/mergeSort.rar

//如果上面这个链接无法响应下载(有可能是被网站给屏蔽掉了),则可使用下载工具(如迅雷等)下载

另,有些网站也介绍归并排序的内容,有兴趣的请访问:

http://www.d263.com/netxiao/computer/shuiping/200504/netxiao_20050420185107.htm

http://ds.ytu.edu.cn/document/c_jiaoan/c28.htm

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
>>返回首页<<
推荐阅读
 
 
频道精选
 
静静地坐在废墟上,四周的荒凉一望无际,忽然觉得,凄凉也很美
© 2005- 王朝网络 版权所有