背景
接上面四篇文章
算法踩坑-快速排序
算法踩坑2-插入排序
算法踩坑3-堆排序
算法踩坑4-冒泡排序
来继续聊聊最近我写的一些算法的小例程，这次要聊的是归并排序，是一个时间复杂度O(NLogN)的算法。归并排序是经典的递归的案例。
主要从以下几方面来说的：
- 归并排序思想
- 归并排序实现
- 归并排序优化
- 时间分析
归并排序思想
归并排序是经典的分治算法的经典实现，把一个大的问题逐步的分解为两部分，然后再进行重组，最终得到一个完整的结果。归并排序有两个重要的步骤是拆分和重组。
归并重组
先说下归并排序的重组思路，前提条件是两个已经排序好的子数组，比如数组A和数组B。
各自有一个指针指向A和B，比如aPtr和bPtr。
使用aPtr和bPtr和遍历数组A和数组B，比较aPtr和bPtr指向的元素，把小的那个元素复制到临时数组，直到aPtr或者bPtr到达数组A或者数组B的末尾，然后把A或者数组B的末尾中没有拷贝到临时数组中的其他元素拷贝到临时数组中去。此时，临时数组是一个合并之后的有序的数组，这个是归并重组的过程。
归并拆分
归并的拆分是为了归并重组服务的，递归的把问题拆解为两部分，最后的递归出口是只有一个元素的情况，那么数组A和数组B是只有一个元素的数组，此时进行归并重组，重组之后的两个元素的数组是有序的，然后需要把临时数组中有序的序列复制到原数组中，后面归并重组步骤需要使用到前面已经排序的结果。
归并排序实现
void MSort(ElementType arr[], ElementType tmpArr[], int left, int right) {
int Center;
if (left < right) {
Center = (left + right) / 2;
MSort(arr, tmpArr, left, Center);
MSort(arr, tmpArr, Center+1, right);
// [left, center]、[center+1, right] 这两部分是排好序的了，合并这两部分
Merge(arr, tmpArr, left, Center+1, right);
}
}
void MergeSort(ElementType arr[], int count) {
ElementType *tmpArr = malloc(count * sizeof(ElementType));
MSort(arr, tmpArr, 0, count-1);
}
void Merge(ElementType arr[], ElementType tmpArr[], int lPos, int rPos, int rightEnd) {
int i, leftEnd, tmpPos, count;
leftEnd = rPos - 1;
tmpPos = lPos;
count = rightEnd - lPos + 1;
// 比较元素复制到临时数组中,！！注意需要使用<=符号
while (lPos <= leftEnd && rPos <= rightEnd) {
if (arr[lPos] < arr[rPos]) {
tmpArr[tmpPos++] = arr[lPos++];
} else {
tmpArr[tmpPos++] = arr[rPos++];
}
}
// 拷贝剩余的元素到临时数组中！！注意需要使用<=符号
while (lPos <= leftEnd) {
tmpArr[tmpPos++] = arr[lPos++];
}
while (rPos <= rightEnd) {
tmpArr[tmpPos++] = arr[rPos++];
}
// 把排序的元素复制到原来的数组中
for (i = 0; i<count; i++, rightEnd--) {
arr[rightEnd] = tmpArr[rightEnd];
}
}
归并排序优化
归并排序以O(NLogN)最坏的情形运行时间运行，使用的比较次数几乎是最优的。
时间分析
归并排序的时间分析和快速排序的时间分析是一样的，一次排序的时间为两次分割的时间加上遍历这次元素所花费的时间：T(N) = 2T(N/2) + N，使用叠缩求和，最终可以得到时间复杂度的结果，该结果是最坏情况的结果。
T(N) = 2T(N/2) + N
T(N/2) =2 T(N/4) + N
T(N/4) = 2T(N/8) + N
=>
T(N)/N = T(N/2)/N/2 + 1
T(N/2)/(N/2) = T(N/4)/(N/4) +1
T(N/4)(N/8) = T(N/8)/(N/16) +1
...
T(N)/N = T(1)/1 + logN
T(N) = NlogN
