基础算法-归并排序

原理

归并排序是稳定的排序算法，其时间复杂度为O(lgN)，空间复杂度为O(N)。

算法步骤

使用分治法进行归并排序。
纸面上二路归并算法：
一、有序列{a1, a2, a3,…an}，二分法得到两个序列{a1, a2,… ak}和{ak+1,… an}，其中k=(1+n)/2;
二、同理，这两个子序列分别进行二分得到新的4个序列，直到划分成{a1}，{a2}… {an}个序列为止。
三、{a1}，{a2}… {an}，可看做有序序列，然后进行二路有序合并即{a1, a2}, {a3, a4}, … {an-1, an}。这些序列中a1

实现

// 一般递归版本、二路归并
// 合并函数
// 要合并的数组1：src[start]~src[mid]
// 要合并的数组2：src[mid+1]~src[end]
// 临时存放数组 dst[start] ~ dst[end] 
void merge(int src[], int dst[], int start, int mid, int end) {
        int i = start;
        int j = mid+1;
        int k = start; // 注意：dst数组索引起始位置为start与src相同
        /*
        while (i < mid+1 && j < end+1) {
                if (src[i] < src[j])
                        dst[k++] = src[i++];
                else
                        dst[k++] = src[j++];
        }
        while (i  < mid+1) {
                dst[k++] = src[i++];
        }
        while (j < end+1) {
                dst[k++] = src[j++];
        }
        */
        while (k <= end) {
            if (j > end || (i <= mid && src[i] < src[j])) {
                dst[k++] = src[i++];
            } else {
                dst[k++] = src[j++];
            }
        }
        // 重新写回原数组
        for (i = start; i < end+1; i++) {
                src[i] = dst[i];
        }
}
// 更好的merge版本
void merge(int src[], int dst[], int start, int mid, int end) {
        int i = start;
        int j = mid+1;
        for (int k = start; k <= end; k++) {
            if (i > mid) dst[k] = src[j++];
            else if (j > end) dst[k] = src[i++];
            else if (src[i] < src[j]) dst[k] = src[i];
            else dst[k] = src[j];
        } 
        // 重新写回原数组
        for (i = start; i < end+1; i++) {
                src[i] = dst[i];
        }
}
// b[] 数组大小与a[]一样，临时存放合并后的元素
void mergeSort(int a[], int b[], int start, int end) {
        if (start < end) { // 不考虑一个元素的情况，直接从两个元素的归并开始
                int mid = (start + end)/2;
                mergeSort(a, b, start, mid);
                mergeSort(a, b, mid+1, end);
                // 若两部分已经有序且右半部最小值大于等于左半部最大值，则直接返回
                if (a[mid+1] >= a[mid]) return;
                merge(a, b, start, mid, end);
        }
}