归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
基本思想：
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
初始关键字 49 38 65 97 76 13 27
第一趟归并 (38 49) (65 97) (13 76) 27
第二趟归并 (38 49 65 97) (13 27 76)
第三趟归并 (13 27 38 49 65 76 97)
将待排序序列R[0...n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。
综上可知，归并排序其实要做两件事：
（1）“分解”——将序列每次折半划分。
（2）“合并”——将划分后的序列段两两合并后排序。
我们先来考虑第二步，如何合并？
在每次合并过程中，都是对两个有序的序列段进行合并，然后排序。这两个有序序列段分别为 R[low, mid] 和 R[mid+1, high]。先将他们合并到一个局部的暂存数组R2中，带合并完成后再将R2复制回R中。
为了方便描述，我们称 R[low, mid] 第一段，R[mid+1, high] 为第二段。每次从两个段中取出一个记录进行关键字的比较，将较小者放入R2中。最后将各段中余下的部分直接复制到R2中。经过这样的过程，R2已经是一个有序的序列，再将其复制回R中，一次合并排序就完成了。
// 合并代码
void Merge(int sourceArr[], int tempArr[], int startIndex, int midIndex, int endIndex) {
int i = startIndex; // i是第一段序列的下标
int j = midIndex + 1; // j是第二段序列的下标
int k = startIndex; // k是临时存放合并序列的下标
while(i <= midIndex && j <= endIndex) {
// 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描
if(sourceArr[i] >= sourceArr[j]) {
tempArr[k++] = sourceArr[j++];
} else {
tempArr[k++] = sourceArr[i++];
}
}
// 若第一段序列还没扫描完，将其全部复制到合并序列
while(i <= midIndex) {
tempArr[k++] = sourceArr[i++];
}
// 若第二段序列还没扫描完，将其全部复制到合并序列
while(j <= endIndex) {
tempArr[k++] = sourceArr[j++];
}
// 将合并序列复制到原始序列中
for(i = startIndex; i <= endIndex; i++) {
sourceArr[i] = tempArr[i];
}
}
掌握了合并的方法，接下来，让我们来了解如何分解。
在某趟归并中，设各子表的长度为gap，则归并前R[0...n-1]中共有n/gap个有序的子表：R[0...gap-1], R[gap...2gap-1], ... , R[(n/gap)gap ... n-1]。
调用Merge将相邻的子表归并时，必须对表的特殊情况进行特殊处理。
若子表个数为奇数，则最后一个子表无须和其他子表归并（即本趟处理轮空）：若子表个数为偶数，则要注意到最后一对子表中后一个子表区间的上限为n-1。
void MergePass(int sourceArr[], int tempArr[], int gap, int length) {
int low = 0;
// 归并gap长度的两个相邻子表
for (low = 0; low + 2 * gap - 1 < length; low = low + 2 * gap) {
Merge(sourceArr, tempArr, low, low + gap - 1, low + 2 * gap - 1);
}
// 余下两个子表，后者长度小于gap
if (low + gap - 1 < length) {
Merge(sourceArr, tempArr, low, low + gap - 1, length - 1);
}
}
void MergeSort(int sourceArr[], int tempArr[], int length) {
for (int gap = 1; gap < length; gap = 2 * gap) {
MergePass(sourceArr, tempArr, gap, length);
}
}
算法的实现（非递归实现版本）：
// 输出数组内容
void print(int array[], int length) {
for (int j = 0; j < length; j++) {
printf(" %d ", array[j]);
}
printf("\n");
}
// 合并-将划分后的序列段两两合并后排序
void Merge(int sourceArr[], int tempArr[], int startIndex, int midIndex, int endIndex) {
int i = startIndex; // i是第一段序列的下标
int j = midIndex + 1; // j是第二段序列的下标
int k = startIndex; // k是临时存放合并序列的下标
while(i <= midIndex && j <= endIndex) {
// 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描
if(sourceArr[i] >= sourceArr[j]) {
tempArr[k++] = sourceArr[j++];
} else {
tempArr[k++] = sourceArr[i++];
}
}
// 若第一段序列还没扫描完，将其全部复制到合并序列
while(i <= midIndex) {
tempArr[k++] = sourceArr[i++];
}
// 若第二段序列还没扫描完，将其全部复制到合并序列
while(j <= endIndex) {
tempArr[k++] = sourceArr[j++];
}
// 将合并序列复制到原始序列中
for(i = startIndex; i <= endIndex; i++) {
sourceArr[i] = tempArr[i];
}
}
void MergeSort(int sourceArr[], int tempArr[], int length) {
for (int gap = 1, low = 0; gap < length; gap = 2 * gap) {
// 归并gap长度的两个相邻子表
for (low = 0; low + 2 * gap - 1 < length; low = low + 2 * gap) {
Merge(sourceArr, tempArr, low, low + gap - 1, low + 2 * gap - 1);
}
// 余下两个子表，后者长度小于gap
if (low + gap - 1 < length) {
Merge(sourceArr, tempArr, low, low + gap - 1, length - 1);
}
}
}
int main(int argc, const char * argv[]) {
int sourceArr[7] = { 49,38,65,97,76,13,27 };
int tempArr[7];
MergeSort(sourceArr, tempArr, 7);
print(sourceArr, 7);
return 0;
}
算法的实现（递归实现的版本）：
// 输出数组内容
void print(int array[], int length) {
for (int j = 0; j < length; j++) {
printf(" %d ", array[j]);
}
printf("\n");
}
// 合并-将划分后的序列段两两合并后排序
void Merge(int sourceArr[], int tempArr[], int startIndex, int midIndex, int endIndex) {
int i = startIndex; // i是第一段序列的下标
int j = midIndex + 1; // j是第二段序列的下标
int k = startIndex; // k是临时存放合并序列的下标
while(i <= midIndex && j <= endIndex) {
// 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描
if(sourceArr[i] >= sourceArr[j]) {
tempArr[k++] = sourceArr[j++];
} else {
tempArr[k++] = sourceArr[i++];
}
}
// 若第一段序列还没扫描完，将其全部复制到合并序列
while(i <= midIndex) {
tempArr[k++] = sourceArr[i++];
}
// 若第二段序列还没扫描完，将其全部复制到合并序列
while(j <= endIndex) {
tempArr[k++] = sourceArr[j++];
}
// 将合并序列复制到原始序列中
for(i = startIndex; i <= endIndex; i++) {
sourceArr[i] = tempArr[i];
}
}
// 二路归并排序（Merge Sort）
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex) {
int midIndex;
if(startIndex < endIndex) { // 是if，不是while，且不含等号，否则死循环
midIndex = (startIndex + endIndex) / 2;
MergeSort(sourceArr, tempArr, startIndex, midIndex);
MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
}
}
int main(int argc, const char * argv[]) {
int sourceArr[7] = { 49,38,65,97,76,13,27 };
int tempArr[7];
MergeSort(sourceArr, tempArr, 0, 6);
print(sourceArr, 7);
return 0;
}
总结
若从空间复杂度来考虑：首选堆排序，其次是快速排序，最后是归并排序。
若从稳定性来考虑，应选取归并排序，因为堆排序和快速排序都是不稳定的。
若从平均情况下的排序速度考虑，应该选择快速排序。
网友评论