预览加载中,请您耐心等待几秒...
1/4
2/4
3/4
4/4

在线预览结束,喜欢就下载吧,查找使用更方便

如果您无法下载资料,请参考说明:

1、部分资料下载需要金币,请确保您的账户上有足够的金币

2、已购买过的文档,再次下载不重复扣费

3、资料包下载后请先用软件解压,在使用对应软件打开

C语言实现归并排序算法实例C语言实现归并排序算法实例归并排序(Mergesort)是创建在归并操作上的一种有效的排序算法。该算法是采用分治法(DivideandConquer)的一个非常典型的应用。一个归并排序的例子:对一个随机点的链表进行排序算法描述归并操作的过程如下:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列设定两个指针,最初位置分别为两个已经排序序列的起始位置比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置重复步骤3直到某一指针到达序列尾将另一序列剩下的所有元素直接复制到合并序列尾特点: 归并排序是稳定的.排序.即相等的元素的顺序不会改变,速度仅次于快速排序,但较稳定。归并操作归并操作(merge),也叫归并算法,指的是将两个顺序序列合并成一个顺序序列的方法。如:设有数列[6,202,100,301,38,8,1]初始状态:6,202,100,301,38,8,1第一次归并后:[6,202],[100,301],[8,38],[1],比较次数:3;第二次归并后:[6,100,202,301],[1,8,38],比较次数:4;第三次归并后:[1,6,8,38,100,202,301],比较次数:4;总的比较次数为:3+4+4=11,;逆序数为14;算法实现//Completedon2014.10.1117:20//Language:C99////版权所有(C)codingwu(mail:oskernel@126.com)//merge_sort(int*list,constintfirst,constintlast){intlen=last-first+1;intleft_min,left_max;//左半区域边界intright_min,right_max;//右半区域边界intindex;inti;int*tmp;tmp=(int*)malloc(sizeof(int)*len);if(tmp==NULL||len<=0)return;for(i=1;i<len;i*=2){for(left_min=0;left_min<len-i;left_min=right_max){intj;right_min=left_max=left_min+i;right_max=left_max+i;j=left_min;if(right_max>len)right_max=len;index=0;while(left_min<left_max&&right_min<right_max){tmp[index++]=(list[left_min]>list[right_min]?list[right_min++]:list[left_min++]);}while(left_min<left_max){list[--right_min]=list[--left_max];}while(index>0){list[--right_min]=tmp[--index];}}}free(tmp);}intmain(){inta[]={288,52,123,30,212,23,10,233};intn,mid;n=sizeof(a)/sizeof(a[0]);mid=n/2;merge_sort(a,0,n-1);for(intk=0;k<n;k++)printf("%d",a[k]);printf("n");return0;}使用递归实现://Completedon2014.10.1118:20//Language:C99////版权所有(C)codingwu(mail:oskernel@126.com)//merge(int*array,constintfirst,constintmid,constintlast){inti,index;intfirst1,last1;intfirst2,last2;int*tmp;tmp=(int*)malloc((last-first+1)*sizeof(int));if(tmp==NULL)return;first1=first;last1=mid;first2=mid+1;last2=last;index=0;while((first1<=last1)&&(first2<=last2)){if(array[first1]<array[first2]){tmp[index++]=array[first1];first1++;}else{tmp[index++]=array[first2];fir