内部排序：归并排序和快速排序

内部排序：归并排序和快速排序2014-12-06前言

之所以把归并排序和快速排序放在一起探讨，很明显两者有一些相似之处：这两种排序算法都采用了分治的思想。下面来逐个分析其实现思想。

归并排序

实现思想

归并的含义很明显就是将两个或者两个以上的有序表组合成一个新的有序表。归并排序中一般所用到的是2-路归并排序，即将含有n个元素的序列看成是n个有序的子序列，每个子序列的长度为1，而后两两合并，得到n/2个长度为2或1的有序子序列，再进行两两合并。。。直到最后由两个有序的子序列合并成为一个长度为n的有序序列。2-路归并的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列。

下面一系列图展示了2-路归并排序的过程:

第一次实现的代码

根据2-路归并操作的思想，站在节省辅助空间的角度上考虑，我写出的归并操作的代码如下：

/* 将有序的arr[start...mid]和有序的arr[mid+1...end]归并为有序的arr[start...end] */void Merge（int *arr,int start,int mid,int end）{int i = start;int j = mid+1;int k = 0;//brr为辅助数组，int *brr = （int *）malloc（（end-start+1）*sizeof（int））;//比较两个有序序列中的元素，将较小的元素插入到brr中while（i<=mid && j<=end）{ if（arr[i]<=arr[j]）brr[k++] = arr[i++];elsebrr[k++] = arr[j++];}//将arr序列中剩余的元素复制到brr中//这两个语句只可能执行其中一个while（i<=mid）brr[k++] = arr[i++];while（j<=end）brr[k++] = arr[j++];//将brr中的元素复制到arr中，使arr[start...end]有序for（i=0;i<k;i++）arr[i+start] = brr[i];//释放brr所占的内存，并将其置为空free（brr）;brr = 0;}

调用上面的函数，得到的归并排序的代码应该是这样的：

/* 对arr[start...end]内的元素进行归并排序 归并排序后的顺序为从小到大 */void MSort（int *arr,int start,int end）{if（start < end）{int mid = （start+end）/2;MSort（arr,start,mid）; //左边递归排序MSort（arr,mid+1,end）; //右边递归排序Merge（arr,start,mid,end）; //左右序列归并}}/* 将该排序算法封装起来 */void Merge_Sort（int *arr,int len）{MSort（arr,0,len-1）;}

输入任意数组来测试，结果也是正确的。