算法导论——归并排序

归并排序的步骤分为三个：将问题分解为更小的问题，然后解决小问题，将小问题合并为大问题的解。针对归并排序的主要思想是：将一个需要排序的数组一分为二，然后将这两部分进行单独排序，然后将这两个排好序的子数组合然后按照顺序合并为大数组。还有一个就是边界问题，将数组无限的分下去知道最后的子数组只剩一个元素的时候也就是终止的时候，因为一个元素的数组，我们认为它就是排好序的。

下面是C++的实现代码：

归并排序从原始数组开始

void merge_sort(int *array, int n){
    merge_range(array, 0, n - 1);
}

中间的merge_range是对大数组进行的分解，然后最开始的if判断语句是这个分解的终止条件。

void merge_range(int *array, int start, int end){
    if(start == end)
        return;

    int mid = (start + end) / 2;
    merge_range(array, start, mid);
    merge_range(array, mid + 1, end);

    merge(array, start, mid, end);
}

最重要的部分就是将两个排好序的子数组合并为一个大数组，其主要的步骤就是，将两个部分的数组拷贝两个新的数组中，然后将这两个数组从小到大地填到大数组，这里有个技巧就是，两个排好序的数组都用探针慢慢往后移，当有一个移动到最后的时候，我们可以通过检查是否到结尾来判断，这样另一个子数组的元素就可以填补到大数组中了，唯一避免这种麻烦的判断，我们在新数组中分别都加了一个元素代表哨兵，用了int的最大值表示无穷大，这里就可以按照普通的判断来结束。

void merge(int *array, int start, int mid, int end){
    int *left_array = new int[mid - start + 2];
    int *right_array = new int[end - mid + 2];
    int i, j;

    for(i = 0; i <= mid - start; i++){
        left_array[i] = array[i + start];
    }
    left_array[i] = std::numeric_limits<int>::max();

    for(j = 0; j <= end - mid - 1; j++){
        right_array[j] = array[j + mid + 1];
    }
    right_array[j] = std::numeric_limits<int>::max();

    i = 0;
    j = 0;

    while(start <= end){
        if(left_array[i] < right_array[j])
            array[start++] = left_array[i++];
        else
            array[start++] = right_array[j++];
    }
}

通过一个main函数，然后增加了一些输出，得到下面结果：

int main()
{
    const int ARRAY_LENGTH = 8;
    int array[ARRAY_LENGTH] = {5, 2, 4, 7, 1, 3, 2, 6};

    merge_sort(array, ARRAY_LENGTH);
}

[0-0] : [ 5 ]
[1-1] : [ 2 ]
[0-1] : [ 2 5 ]
[2-2] : [ 4 ]
[3-3] : [ 7 ]
[2-3] : [ 4 7 ]
[0-3] : [ 2 4 5 7 ]
[4-4] : [ 1 ]
[5-5] : [ 3 ]
[4-5] : [ 1 3 ]
[6-6] : [ 2 ]
[7-7] : [ 6 ]
[6-7] : [ 2 6 ]
[4-7] : [ 1 2 3 6 ]
[0-7] : [ 1 2 2 3 4 5 6 7 ]