C语言实现归并排序算法实例.docx

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:[e-mail])//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:[e-mail])//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