首页 > algorithm > 排序2(递归归并排序)

排序2(递归归并排序)

  今天继续看了《算法导论》的第二章,的确讲的有点深,花费了不少的时间实现了递归归并排序,好了,长话短说,先分析一下:
  递归归并排序需要和得排序记录等长的空间,需要的时间是n lg n。因为对数的增长速度比任何线性函数增长的都慢,当输入的规模大时,合并排序在最坏的情况下都要比(插入||冒泡||选择)快!
时间的算法思路:假设是满树,共2的n次方个,那么递归树就是lgn+1层,每一层花费的代价都是cn,所以总共用的时间是cn(lgn+1)=cnlgn+cn,忽略低阶项和常量,就是nlgn了。

  反思:思想看懂了,用C写了一边之后,竟然没有成功,用VC6.0一步一步的调试,才发现原来递归调用中的for循环没有写对,这也是自己编程习惯的失误,命名简单结果遇到复杂的题时,那些abcijk的不知搞啥用了,结果就错了。以后得记住改正。
  总结到此,代码附上。
#include <stdio.h>
int b[10]={0};
void merge(int *sr,int i,int m,int n)
{
int al,ar,k,j;
for(ar=m+1,al=i,k=i;al<=m&&ar<=n;k++)
{
if(sr[al]<sr[ar])
b[k]=sr[al++];
else
b[k]=sr[ar++];
}
while(al<=m)
b[k++]=sr[al++];
while(ar<=n)
b[k++]=sr[ar++];
for(k=i,j=0;k<=n;j++,k++)
sr[i+j]=b[i+j];
return;
}
void mergeSort(int *sr,int s,int t)
{
int m;
if(s==t)
b[s]=sr[s];
else
{
m=(s+t)/2;
mergeSort(sr,s,m);
mergeSort(sr,m+1,t);
merge(sr,s,m,t);
}
return;
}
int main()
{
int i,a[10]={4,5,7,8,1,9,3,6,11,2};
mergeSort(a,0,9);
for(i=0;i<10;i++)
printf(“%d “,a[i]);
printf(“\n”);
return 0;
}

  1. Antonija 9月 2nd, 2012 @ 04:51 | #1

    Your awnser shows real intelligence.

评论提交中, 请稍候...

留言


可以使用的标签: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
Trackbacks & Pingbacks ( 0 )
  1. 还没有 trackbacks