C++实现归并排序

什么是归并排序

归并排序是一种分治策略的排序算法，将待排序的序列切分为若干个子序列，递归地对子序列排序，并将各子序列的排序结果合并成最终有序序列。归并排序的时间复杂度为O(nlogn)，是一种高效的排序算法。

归并排序的实现

递归实现

归并排序的递归实现比较容易理解。我们可以将待排序的序列不断切分为更小的子序列，直到子序列长度为1，此时子序列已经是有序的，然后将有序的子序列合并成更大的有序序列。

下面是C++实现的递归方法：

void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

在该方法中，参数arr是要排序的数组，参数left表示要排序的子数组的左边界，参数right表示要排序的子数组的右边界。方法中首先判断子数组的长度是否大于1，如果是，则继续将子数组划分为更小的子数组并递归调用归并排序方法。最后调用合并方法merge将排好序的子数组合并成更大的有序序列。

合并实现

为了将两个子数组合并成一个有序数组，我们需要一个辅助数组，并定义三个指针i、j、k，分别指向两个待合并的子数组的起始位置和辅助数组的起始位置。将两个子数组的元素依次比较，将最小的元素放入辅助数组中，直到其中一个子数组的元素全部比较完毕。此时再将另一个子数组的剩余元素依次放入辅助数组中。最后将辅助数组中的元素复制回原数组中。

下面是C++实现的合并方法：

void merge(int arr[], int left, int mid, int right) {
    int i = left, j = mid + 1, k = 0;
    int tmp[right - left + 1];
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            tmp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        tmp[k++] = arr[i++];
    }
    while (j <= right) {
        tmp[k++] = arr[j++];
    }
    for (int p = 0; p < k; p++) {
        arr[left + p] = tmp[p];
    }
}

在该方法中，参数arr是要排序的数组，参数left表示子数组的左边界，参数mid表示子数组的中间位置，参数right表示子数组的右边界。方法中定义了一个辅助数组tmp，并用指针i、j、k分别指向子数组和辅助数组。然后比较子数组的元素大小，较小的元素放入辅助数组中，对应的指针向后移动。最后将辅助数组中的元素复制回原数组中。

示例说明

假设要对序列{8, 3, 2, 9, 7, 1, 5, 4}进行归并排序。

第一步

首先将整个序列切分为两个子序列{8, 3, 2, 9}和{7, 1, 5, 4}。

第二步

对子序列{8, 3, 2, 9}继续切分，分别得到{8, 3}和{2, 9}两个子序列。对子序列{7, 1, 5, 4}同样进行切分，得到{7, 1}和{5, 4}两个子序列。

第三步

继续对子序列进行切分，得到8、3、2、9、7、1、5、4等八个有序子序列。

第四步

将两两相邻的有序子序列合并，得到{3, 8}、{2, 9}、{1, 7}、{4, 5}四个有序数组。

第五步

继续将两两相邻的有序数组合并，得到{2, 3, 8, 9}和{1, 4, 5, 7}两个有序数组。

第六步

最后将两个有序数组合并，得到{1, 2, 3, 4, 5, 7, 8, 9}，即为最终排序结果。

代码演示

以下是完整的C++代码：

#include <iostream>

using namespace std;

void merge(int arr[], int left, int mid, int right) {
    int i = left, j = mid + 1, k = 0;
    int tmp[right - left + 1];
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            tmp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        tmp[k++] = arr[i++];
    }
    while (j <= right) {
        tmp[k++] = arr[j++];
    }
    for (int p = 0; p < k; p++) {
        arr[left + p] = tmp[p];
    }
}

void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {8, 3, 2, 9, 7, 1, 5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    merge_sort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

运行结果为：1 2 3 4 5 7 8 9，即为排序结果。