[算法,排序]归并排序算法,实现,比较与测试
[算法,排序]归并排序算法,实现,比较与测试
(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
