数据结构与算法之归并排序

数据结构与算法，可以说是编程思维的基石。不知道大家在大学期间对这门功课有着怎样的情感，或是喜爱？或是泪奔？不管怎样，作为软件开发的我们都要有信心去啃这块硬骨头，下面我们就先分享一下关于归并排序的原理及编码实现。

原理

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并过程分解

假设两个有序表分别为a,b，最后归并到r表中。

归并过程：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

示例分解

假设原始序列为：{6，202，100，301，38，8，1}，其长度len = 7，归并过程：

1. 第一次归并：先中分得到mid索引为3，递归归并左半部分{6， 202， 100， 301}，对这个子序列又中分为{6, 202}和{100, 301}，此时这两个子序列已有序；递归归并右半部分{38, 8, 1}，对这个子序列又中分为{38, 8}和{1}，归并后形成{8，38}和{1}，共比较3次

2. 第二次归并：第一次归并后变成{6,202},{100,301},{8,38},{1}，即{6， 202，100，301，8，38，1}，再中分得到{6，202，100，301}和{8，38，1}，分别递归归并后为{6，100，202，301}新序列和{1，8，31}新序列，共比较3+1=4次。

3. 第三次归并：第二次归并后，得到的两个有序的子序列为{6，100，202，301}和{1，8，38}，这一次是递归回到第一层了，已经是中分了，直接比较和复制到新的r即可。最终得到{1，6，8，38，100，202，301}，共比较4次（6与1比较，6与8比较，100与8比较，100与38比较）。

这个序列从无序到有序总共比较了3+4+4=11次。

算法复杂度分析

归并排序的效率是比较高的，假设数列长度为N，采用中分法的方式将数列分开成若干个小数列一共要log2N 步，每步都是一个合并有序数列的过程，时间复杂度可以记为O ( N )，故一共为O ( N * log2N )。

因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在常用的几种排序方法（快速排序，归并排序，希尔排序，堆排序）中也是效率比较高的。

时间复杂度：O ( N * log2N )；

C语言实现：

/**

* 归并排序算法

*

* @param list 待排序的序列

* @param first 子序列的起点索引

* @param last 子序列的终点索引

* @param temp 临时数组，用于将两个子序列二路归并时存储

*/

voidmergeSort(intlist[],intfirst,intlast,inttemp[]){

if(first<last){

intmid=(first+last)/2;

// 递归归并中分左子序列，使子序列有序

mergeSort(list,first,mid,temp);

// 递归归并中分右子序列，使子序列有序

mergeSort(list,mid+1,last,temp);

// 最后二路归并，使序列成有序

// 必须明白的一点，每次中分递归归并都需要二路归并，因为中分后的任意子序列

// 在有序后，都要二路归并成一个序列

mergeList(list,first,mid,last,temp);

}

}

/**

* 二路归并list[first...mid]子序列与list[mid+1...last]

*

* @param list 序列

* @param first 左子序列的起点

* @param mid 序列中间分割点

* @param last 右序列终点

* @param temp 临时序列，用于将两个无序的子序列归并到temp中，使之有序

*/

voidmergeList(intlist[],intfirst,intmid,intlast,inttemp[]){

intleftIndex=first;

intleftEndIndex=mid;

intrightIndex=mid+1;

intrightEndIndex=last;

inttempIndex=0;

// 寻找两个子序列，顺序遍历，将值小的复制到临时数组中，直到其中一个子序列遍历完毕

while(leftIndex<=leftEndIndex&&rightIndex<=rightEndIndex){

// 值小的就复制到临时数组中

if(list[leftIndex]<=list[rightIndex]){

temp[tempIndex]=list[leftIndex];

tempIndex++;

leftIndex++;

}else{

temp[tempIndex]=list[rightIndex];

tempIndex++;

rightIndex++;

}

}

// 有可能左子序列更长，因此将剩下的部分直接复制到临时数组中

while(leftIndex<=leftEndIndex){

temp[tempIndex++]=list[leftIndex++];

}

// 有可能右子序列更长，因此将剩下的部分直接复制到临时数组中

while(rightIndex<=rightEndIndex){

temp[tempIndex++]=list[rightIndex++];

}

// 最后还需要将有序的临时数组复制到原始序列中

for(inti=0;i<tempIndex;++i){

list[first+i]=temp[i];

}

// 这里添加一个打印，记录归并

NSMutableString*str=[[NSMutableStringalloc] init];

for(inti=0;i<sizeof(list)-1;++i){

if(i==0){

[str appendFormat:@"%d",list[i]];

}else{

[str appendFormat:@", %d",list[i]];

}

}

NSLog(@"此次二路归并后，得到的序列为：(%@)",str);

}

测试：

intlist[]={6,202,100,301,38,8,1};

inttemp[7]={0};

mergeSort(list,0,7-1,temp);

打印结果：

此次二路归并后，得到的序列为：(6,202,100,301,38,8,1)

此次二路归并后，得到的序列为：(6,202,100,301,38,8,1)

此次二路归并后，得到的序列为：(6,100,202,301,38,8,1)

此次二路归并后，得到的序列为：(6,100,202,301,8,38,1)

此次二路归并后，得到的序列为：(6,100,202,301,1,8,38)

此次二路归并后，得到的序列为：(1,6,8,38,100,202,301)

从打印结果可以看出来，果然与我们前面的算法分析是一样的。