归并排序以ø(N logN)最坏情形运行时间运行，而所使用的比较次数几乎是最优的。
这个算法的基本操作是合并两个已排序的表。
归并排序大致分为两种：
- 自顶向下(递归)
- 自底向上(迭代)
1. 实现
1.1 自顶向下递归排序
自顶向下的递归排序主要使用的是分治思想,代码实现较为复杂。
1.1.1 实现流程
- 分配等同于待排序大小的内存空间。(必须且不会更少)
- 对半分割，成两个不同的部分。
- 重复2步骤直至不能再分割。
- 对两部分分别排序。
- 合并排序两部分。
- 返回上一级递归。
1.1.2 代码实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int ElementType;
/* 归并排序入口程序 */
void MergeSort(ElementType source[], int n);
/* 二分程序 */
static void MSort(ElementType source[], ElementType tmpArr[], int left, int right);
/* 排序合并程序 */
static void Merge(ElementType source[], ElementType tmpArr[], int left, int rightPos, int right);
void MergeSort(ElementType source[], int n) {
ElementType *tmpArr;
tmpArr = (ElementType *) malloc(n * sizeof(ElementType));
if (tmpArr != NULL) {
MSort(source, tmpArr, 0, n - 1);
free(tmpArr);
} else {
printf("No Space for tmp array!!!");
exit(EXIT_FAILURE);
}
}
static void MSort(ElementType source[], ElementType tmpArr[], int left, int right) {
int center;
if (left < right) {
center = (left + right) / 2;
MSort(source, tmpArr, left, center);
MSort(source, tmpArr, center + 1, right);
Merge(source, tmpArr, left, center + 1, right);
}
}
static void Merge(ElementType source[], ElementType tmpArr[], int left, int rightPos, int right) {
int tmpLeft = left;
int leftEnd = rightPos - 1;
int tmpRight = rightPos;
int Num = right - left + 1;
while (tmpLeft <= leftEnd && tmpRight <= right) {
if (source[tmpLeft] < source[tmpRight]) {
tmpArr[left++] = source[tmpLeft++];
} else {
tmpArr[left++] = source[tmpRight++];
}
}
while (tmpLeft <= leftEnd) {
tmpArr[left++] = source[tmpLeft++];
}
while (tmpRight <= right) {
tmpArr[left++] = source[tmpRight++];
}
/* 把排好的tmp复制回原数组,由于左标志已经被移动因此用右标志向左移动倒叙放 */
for (int i = 0; i < Num; ++i, right--) {
source[right] = tmpArr[right];
}
}
1.1.3 自顶向下缩短运行时间的几个Tips
1.1.3.1 对小规模数组使用插入排序
长度小于15，一般可将时间缩短10%~15%。
1.1.3.2 测试数组是否已经有序
如果a[mid]小于等于a[mid+1]，我们就认为数组已经是有序的并跳过merge()方法。
1.1.3.3 不将元素赋值到辅助数组
部分归并排序实现中会现将数组复制到辅助数组排序后再复制回去(本例中没有这么做)。这种操作是可以避免的。
1.2 自低向上归并排序
自底向上的思想是，先两两合并最小的，再四四合并相对小的，如此这般，直到我们将整个数组归并到一起。
1.2.1 实现流程
- 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素
- 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素
- 重复步骤2，直到所有元素排序完毕
1.2.2 算法图解
插入排序
插入排序
1.2.3 代码实现
int min(int x, int y) {
return x < y ? x : y;
}
void merge_sort(int arr[], int len) {
int* a = arr;
int* b = (int*) malloc(len * sizeof(int*));
int seg, start;
for (seg = 1; seg < len; seg += seg) {
for (start = 0; start < len; start += seg + seg) {
int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2)
b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
while (start1 < end1)
b[k++] = a[start1++];
while (start2 < end2)
b[k++] = a[start2++];
}
int* temp = a;
a = b;
b = temp;
}
if (a != arr) {
int i;
for (i = 0; i < len; i++)
b[i] = a[i];
b = a;
}
free(b);
}
2. 时间复杂度
最差时间复杂度 ø( nlog n )
最优时间复杂度 ø( n )
平均时间复杂度 ø( nlog n )
最差空间复杂度 ø( n )
