归并排序

归并排序

2019 年 03 月 18 日

915 次浏览

900字数

1. 原理

首先考虑有两个有序数组，现需要将两个有序数组合并为一个数组，并使得新数组同样是有序的。实现方法其实很简单，先建立一个大小为两个数组之和的新数组，然后想象有两个指针分别指向两个数组的第一个元素，然后比较这两个元素的大小并将较小元素放入新数组的第一位，然后让指向那个元素的指针往后走一位就行了，最终就可得到一个新的有序数组。一个要注意的地方是必定会有一个数组先遍历完，这时候直接将另一个数组的剩下部分全部放入新数组的剩余部分即可。

而归并排序的原理是，我现在要排序一个乱序数组。首先我要将这个数组分成大小尽量相等的两个部分，而先分别将这两个部分排好序，这时候就相当于是两个有序的数组，所以我们现在只需要像上面所说的将两个有序数组合并就行了。而这两个部分各自又怎么排序呢，当然也就是一样的方法，先分成两个部分，然后分别排好序再合并就可以了。可以想象，一个无序数组像这样一层一层的向下递归，最终要排序的一定是大小为1的数组，而这样的数组不需要排序，所以归并排序逻辑上是完备的。

可以用下面的图清晰地看到归并排序的全过程。

归并排序时间复杂度：O(NlogN)。可知分组合并的时候每层合并都要遍历一遍数组，而总共需要合并递归深度次，所以时间复杂度为 O(NlogN)。空间复杂度为O(N)。归并排序是一种稳定的排序算法。

2. 代码

#include <stdio.h>
#include <stdlib.h>

// 合并两个有序区间为一个有序区间
void merge(int* arr, int left, int middle, int right) {
    // 用一个临时数组存储两个区间合并后的有序数组
    int* tmpArr = (int *)malloc(sizeof(int) * (right - left + 1));
    int l = left, r = middle + 1, index = 0;

    while (l <= middle && r <= right) {  // 同时遍历两个区间
        if (arr[l] < arr[r]) {
            tmpArr[index++] = arr[l++];
        }
        else {
            tmpArr[index++] = arr[r++];
        }
    }

    if (l > middle) {  // 如果左区间遍历完了
        while (r <= right) {  // 则将右区间填到剩余空间
            tmpArr[index++] = arr[r++];
        }
    }
    if (r > right) {  // 如果右区间遍历完了
        while (l <= middle) {  // 则将左区间填到剩余空间
            tmpArr[index++] = arr[l++];
        }
    }

    // 搬移有序区间到原空间
    for (int i = left; i <= right; i++) {
        arr[i] = tmpArr[i - left];
    }

    free(tmpArr);
}

void __merge_sort(int* arr, int left, int right) {
    int middle = (left + right) / 2;

    if (left < right) {  // 当区间内只有一个元素的时候就不用排序了
        __merge_sort(arr, left, middle);
        __merge_sort(arr, middle + 1, right);
        merge(arr, left, middle, right);
    }
}

void merge_sort(int* arr, int size) {
    __merge_sort(arr, 0, size-1);
}

int main(int argc, char const *argv[])
{
    int arr[] = {2, 4, 1, 1, 7, 9, 3, 6, 5, 8};
    int i;
    merge_sort(arr, sizeof(arr) / sizeof(int));
    for(i = 0; i<(sizeof(arr)/sizeof(int)); i++) 
        printf("%d\n", arr[i]);
    return 0;
}

3. 归并排序非递归

如何用非递归的方法完成归并排序呢？这里有一种不需要栈的思路。

递归思路是先将整个区间一直向下二分成两个子区间，直到最终一个区间内只剩一个元素的时候这个区间就是有序的，然后再把有序区间两两合并成为更大的有序区间。而不用递归的话，我们可以直接把每个元素都看成一个只有一个元素的有序区间，然后直接两两合并得到更大的有序区间，然后一直向后两两合并即可，如下图：

可以看出还是归并的思路，而且是省去了递归的向下分组的过程。

需要注意的是区间边界的选定。假设gap为当前一个区间最多有几个元素。如果要套用递归中 merge() 函数的话，left如果等于 i，则从上图可知 middle 应该等于 i + gap - 1 ，right 应该等于 middle + gap。但注意很有可能会出现分组不够的情况，例如上图第一排最右边的4，它的区间没有其他区间和它合并，如果直接按照上面的公式算的话 right 会直接越界，而且可以想到 middle 也有越界的可能，故多加一个判断，如果 middle 或者 right 越界就将它们重新拉回右边界即可。

void MergeSortNor(int* arr, int size) {
    int gap = 1;  // 初始一组只有一个元素，两组两组合并
    while (gap < size) {  // 当gap大于等于size的时候，所有元素都在一组里，则不用合并了
        for (int i = 0; i < size; i += 2 * gap) {  // i一次要跳过两组
            int left = i;
            int middle = left + gap - 1;
            int right = middle + gap;

            if (middle >= size) {  // middle可能越界
                middle = size - 1;
            }
            if (right >= size) {  // right可能越界
                right = size - 1;
            }

            merge(arr, left, middle, right);
        }
        gap *= 2;
    }
}

// 一样的 merge() 函数
// 合并两个有序区间为一个有序区间
void merge(int* arr, int left, int middle, int right) {
    // 用一个临时数组存储两个区间合并后的有序数组
    int* tmpArr = (int *)malloc(sizeof(int) * (right - left + 1));
    int l = left, r = middle + 1, index = 0;

    while (l <= middle && r <= right) {  // 同时遍历两个区间
        if (arr[l] < arr[r]) {
            tmpArr[index++] = arr[l++];
        }
        else {
            tmpArr[index++] = arr[r++];
        }
    }

    if (l > middle) {  // 如果左区间遍历完了
        while (r <= right) {  // 则将右区间填到剩余空间
            tmpArr[index++] = arr[r++];
        }
    }
    if (r > right) {  // 如果右区间遍历完了
        while (l <= middle) {  // 则将左区间填到剩余空间
            tmpArr[index++] = arr[l++];
        }
    }

    // 搬移有序区间到原空间
    for (int i = left; i <= right; i++) {
        arr[i] = tmpArr[i - left];
    }

    free(tmpArr);
}

归并排序