写文章

归并排序原理

归并排序的核心思想是：利用分治策略，不断划分子序列直到不能划分为止，此时各个子序列是有序的，合并相邻有序子序列最终得到一个有序序列。我们利用下图解释划分子序列过程。

现在有原始序列[5, 10, 6, 8, 15, 11, 10, 7]采用递归的方式不断对序列进行划分，最终划分成单个元素的序列。有序子序列合并过程如下图所示：

相邻有序子序列进行合并，得到一个有序的序列。最终所有有序子序列进行合并得到一个完整的有序序列。

归并排序实现

根据子序列合并过程图我们可以看出，本质上就是两个有序子序列进行合并成一个有序序列的过程。划分的过程还是在原始序列里进行划分，所以相邻的序列必定有边界进行划分，现假设两个相邻子序列边界分别是left、mid和right。其中left~mid构成一个子序列，mid+1~right构成另外一个子序列，两个序列相邻。合并代码如下：

static void merge(data_type_t *src, int left, int mid, int right, data_type_t *temp){
    if(src == NULL || temp == NULL){
        return;
    }
    int i = left, j = mid + 1;
    int index = 0;

    while(i <= mid && j <= right){
        if(src[i] < src[j]){
            temp[index++] = src[i++];
        }else{
            temp[index++] = src[j++];
        }
    }
    if(i <= mid){
        //将剩余左边部分拷贝到临时缓冲区
        memcpy(&temp[index], &src[i], (mid - i + 1) * sizeof(data_type_t));
    }
    if(j <= right){
        //将右边剩余部分拷贝到临时缓冲区
        memcpy(&temp[index], &src[j], (right - j + 1) * sizeof(data_type_t));
    }
    //将临时缓冲区的内容拷贝到原始缓冲区中
    memcpy(&src[left], temp, (right - left + 1) * sizeof(data_type_t));
    for(i = left; i <= right; i++){
        printf("%d ", src[i]);
    }
    printf("\n");
}

每次将较小的值放在临时缓冲区中，其中一个子序列遍历完毕则退出循环，判断两个子序列是否都已遍历完毕，将未遍历完毕的子序列拷贝到临时缓冲区中，最后将临时缓冲区里的内容再复制到两个子序列的所在区间，这样两个子序列合并完毕且有序，为了便于观察合并过程，每进行一次归并则打印归并后的序列值。

归并排序实现代码如下：

void merge_sort(data_type_t *src, int left, int right, data_type_t *temp){
    if(src == NULL || temp == NULL || left >= right){
        return;
    }
    int mid = (left + right) / 2;
    merge_sort(src, left, mid, temp);
    merge_sort(src, mid + 1, right, temp);
    merge(src, left, mid, right, temp);
}

在代码里我们递归对左边区域进行划分，然后再递归对右边区域进行划分，不断进行有序子序列合并。

归并排序算法验证

下面我们写一个小程序验证算法的正确性。

#include <stdio.h>
#include "merge_sort.h"

int main() {
    data_type_t arr[8] = {5, 10, 6, 8, 15, 11, 10, 7};
    data_type_t temp[8] = {0};

    merge_sort(arr, 0, 7, temp);
    printf("归并排序结果\n");
    int i = 0;
    for(i = 0; i < 8; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

为了便于观察，原始数据和图解的一样，现编译运行输出如下：

5 10
6 8
5 6 8 10
11 15
7 10
7 10 11 15
5 6 7 8 10 10 11 15
归并排序结果
5 6 7 8 10 10 11 15

从输出结果中，我们对照图解归并排序过程，完全符合。