简单分析C语言中的归并排序算法

　　在我们利用C语言进行程序编写的时候，排序算法的选择使用往往决定我们编写程序所需的时间和精力，选择正确的排序算法能够事半功倍。今天课课家笔者给大家介绍的是C语言中的归并排序算法，让大家在编写程序的时候多一种算法的选择。那么到底什么是归并排序算法呢？它的具体编写运算方法又是怎么样的呢？大家可以在本次的讲解中找到答案。

　　所谓归并排序（MERGE-SORT），它是建立在归并操作上的一种有效的排序算法，这种算法是采用分治法（Divide and Conquer）的一个非常典型的应用。具体执行过程为将已有序的子序列合并，使之得到完全有序的序列，也就是说先使每个子序列有序，再使子序列段间有序。如果我们将两个有序表合并成一个有序表，它就被称为二路归并。归并排序算法的基本思想是将待排序序列分为两部分，依次对分得的两个部分再次使用归并排序，之后再对其进行合并。大家看完基本概念的介绍可能还比较模糊，接下来笔者就以对序列A[0],A[l]…,A[n-1]进行升序排列为例来给大家进行讲解，在此采用自顶向下的实现方法，具体操作步骤如下：

　　①首先我们将所要进行的排序序列分为左右两个部分，如果要进行排序的序列的起始元素下标为first，最后一个元素的下标为last，那么左右两部分之间的临界点下标mid=(first+last)/2，这两部分分别是A[first…mid]和A[mid+1…last]。

　　②接下来我们将上面所分得的两部分序列继续按照步骤1继续进行划分，直到划分的区间长度为1。

　　③最后我们将划分结束后的序列进行归并排序，排序方法为对所分的n个子序列进行两两合并，得到n/2或n/2+l个含有两个元素的子序列，再对得到的子序列进行合并，直至得到一个长度为n的有序序列为止。下面笔者通过一段代码来给大家介绍如何实现归并排序，具体代码如下：

　　#include<stdio.h>

　　#include<stdlib.h>

　　#defineN7

　　voidmerge(intarr[],intlow,intmid,inthigh){

　　inti,k;

　　int*tmp=(int*)malloc((high-low+1)*sizeof(int));

　　//申请空间，使其大小为两个

　　intleft_low=low;

　　intleft_high=mid;

　　intright_low=mid+1;

　　intright_high=high;

　　for(k=0;left_low<=left_high&&right_low<=right_high;k++){//比较两个指针所指向的元素

　　if(arr[left_low]<=arr[right_low]){

　　tmp[k]=arr[left_low++];

　　}else{

　　tmp[k]=arr[right_low++];

　　}

　　}

　　if(left_low<=left_high){//若第一个序列有剩余，直接复制出来粘到合并序列尾

　　//memcpy(tmp+k,arr+left_low,(left_high-left_low+l)*sizeof(int));

　　for(i=left_low;i<=left_high;i++)

　　tmp[k++]=arr[i];

　　}

　　if(right_low<=right_high){

　　//若第二个序列有剩余，直接复制出来粘到合并序列尾

　　//memcpy(tmp+k,arr+right_low,(right_high-right_low+1)*sizeof(int));

　　for(i=right_low;i<=right_high;i++)

　　tmp[k++]=arr[i];

　　}

　　for(i=0;i<high-low+1;i++)

　　arr[low+i]=tmp[i];

　　free(tmp);

　　return;

　　}

　　voidmerge_sort(intarr[],unsignedintfirst,unsignedintlast){

　　intmid=0;

　　if(first<last){

　　mid=(first+last)/2;/*注意防止溢出*/

　　/*mid=first/2+last/2;*/

　　//mid=(first&last)+((first^last)>>1);

　　merge_sort(arr,first,mid);

　　merge_sort(arr,mid+1,last);

　　merge(arr,first,mid,last);

　　}

　　return;

　　}

　　intmain(){

　　inti;

　　inta[N]={32,12,56,78,76,45,36};

　　printf("排序前\\n");

　　for(i=0;i<N;i++)

　　printf("%d\\t",a[i]);

　　merge_sort(a,0,N-1);//排序

　　printf("\\n排序后\\n");

　　for(i=0;i<N;i++)

　　printf("%d\\t",a[i]);printf("\\n");

　　system("pause");

　　return0;

　　}

　　输出结果：

　　排序前

　　32125678764536

　　排序后

　　12323645567678

　　通过分析上面的运行结果，我们不难发现归并排序成功地实现了对给定序列的排序操作。接下来笔者通过下图来让大家了解归并排序的具体操作流程：

　　①在上图中，我们首先对所要进行排序的序列进行分解，直到分为单个元素为止，然后将其进行两两合并。由于最终分解成单个元素，因此在合并的时候.将小数放在前面，大数放在后面，这样就能得到一个有序序列了。

　　②接下来我们对两个相连的有序序列进行排序，先比较有序序列中的第一个元素，将较小的元素放入临时数组中，接着将较小元素所在数组的下一个元素与另一个数组中的较小元素比较，同样将较小元素放入临时数组中，依次进行，直到两个数组的所有元素都放入临时数组中。

　　③最后我们再将临时数组的元素放入原始数组中的对应位置。

　　以上就是归并排序算法的具体实现。

　　本次简单分析C语言中的归并排序算法的讲解到此就暂告一段落，如果以后有什么相关的内容进行补充或者修改的话，笔者会继续在此进行相关内容的补充或者修改的工作，同时也欢迎大家对本次的讲解提出自己的建议和补充。最后笔者希望本次的讲解对大家学习C语言能够起到一定的帮助作用！