C++归并排序详解

归并排序是一种基于分治思想的高效排序算法，它的时间复杂度为O(nlogn)，并且它的稳定性使得它在实际应用中得到了广泛的应用。在本文中，我们将为大家详细讲解C++归并排序的具体实现过程和算法思想。

算法原理

归并排序基于分治算法，首先将待排序序列不断二分，直到每个子序列只剩一个元素，然后将相邻的子序列进行归并，合并后的子序列再次进行归并，最终得到有序序列。

简单来说，归并排序可以概括为以下三个步骤：

1. 分割：将待排序序列不断二分，直到每个子序列只剩一个元素。
2. 归并：将相邻的子序列进行归并，合并后的子序列再次进行归并。
3. 合并：最终得到有序的序列。

代码实现

下面是C++中归并排序的具体实现：

void merge(vector<int>& nums, int start, int mid, int end) {
    int left = start, right = mid + 1;
    vector<int> temp;
    while (left <= mid && right <= end) {
        if (nums[left] <= nums[right])
            temp.push_back(nums[left++]);
        else
            temp.push_back(nums[right++]);
    }
    while (left <= mid)
        temp.push_back(nums[left++]);
    while (right <= end)
        temp.push_back(nums[right++]);
    for (int i = 0; i < temp.size(); ++i) 
        nums[start + i] = temp[i];
}

void mergeSort(vector<int>& nums, int start, int end) {
    if (start >= end) return;
    int mid = (start + end) / 2;
    mergeSort(nums, start, mid);
    mergeSort(nums, mid + 1, end);
    merge(nums, start, mid, end);
}

归并排序的主要部分是归并操作，也就是merge函数。mergeSort函数用于划分子序列和递归调用归并操作，其中start表示待排序序列的起始位置，end表示终止位置，mid表示中间位置。在merge函数中，定义temp用于临时存储归并后的结果，在循环中依次将两个子序列的元素进行比较，将较小的元素依次存入temp中，最终将剩余的元素直接插入到temp中，然后将temp中的元素拷贝回原数组中。

示例说明

示例一

看下面这个例子，假设我们有一个数组[6,8,4,3,9,1,7,2,5]需要进行排序。

1. 分割：首先整个数组被分为[6,8,4,3]和[9,1,7,2,5]两个子序列，然后两个子序列再分别被分割为[6,8]、[4,3]和[9,1,7]、[2,5]两个子序列，最终分为[6]、[8]、[4]、[3]、[9]、[1]、[7]、[2]、[5]这九个独立的子序列。
2. 归并：将相邻子序列归并，首先将[6]和[8]两个子序列进行合并，得到[6,8]，继续将[3]和[4]进行合并，得到[3,4]，然后将[6,8]和[3,4]进行合并，得到[3,4,6,8]。同理，将另一个半部分归并，得到[1,2,5,7,9]
3. 合并：最终将[3,4,6,8]和[1,2,5,7,9]进行合并，得到[1,2,3,4,5,6,7,8,9]。

示例二

假设我们有一个长度为1000的随机数组，需要进行排序并统计时间复杂度。

#include <iostream>
#include <vector>

using namespace std;

void merge(vector<int>& nums, int start, int mid, int end) {
    int left = start, right = mid + 1;
    vector<int> temp;
    while (left <= mid && right <= end) {
        if (nums[left] <= nums[right])
            temp.push_back(nums[left++]);
        else
            temp.push_back(nums[right++]);
    }
    while (left <= mid)
        temp.push_back(nums[left++]);
    while (right <= end)
        temp.push_back(nums[right++]);
    for (int i = 0; i < temp.size(); ++i) 
        nums[start + i] = temp[i];
}

void mergeSort(vector<int>& nums, int start, int end) {
    if (start >= end) return;
    int mid = (start + end) / 2;
    mergeSort(nums, start, mid);
    mergeSort(nums, mid + 1, end);
    merge(nums, start, mid, end);
}

int main() {
    vector<int> nums;
    for (int i = 0; i < 1000; ++i)
        nums.push_back(rand() % 1000);
    mergeSort(nums, 0, nums.size() - 1);
    for (int num : nums)
        cout << num << " ";
    return 0;
}

在示例二中，我们生成了一个长度为1000的随机数组，使用归并排序进行排序，并统计时间复杂度。通过测试数据发现，对于长度为1000的序列，归并排序的时间复杂度在0.5ms左右。

总结

本文详细讲解了C++归并排序算法的基本原理、代码实现和示例。归并排序划分自序列、递归和合并操作使得它的时间复杂度为O(nlogn)，并且稳定性在实际应用中得到了广泛的应用。