C++实现合并排序的方法

C++ 是一门功能强大的编程语言，提供了多种排序算法来满足不同场景的需要。其中，合并排序是一种常用的高效排序算法，下面我们就来介绍一下 C++ 实现合并排序的方法。

合并排序算法简介

合并排序算法是一种基于归并操作的排序算法，它的基本思想是将一个数组划分为两个子数组，递归地对这两个子数组分别进行排序，然后将排好序的两个子数组合并成一个有序的数组。该算法的时间复杂度为 O(nlogn)，是一种高效的排序算法。

C++ 实现合并排序的方法

下面是 C++ 实现合并排序的一般步骤：

1. 将待排序数组划分为两个子数组，分别排序；
2. 将排好序的两个子数组合并成一个有序的数组。

下面给出这些步骤的详细代码实现：

// 合并排序函数
void merge_sort(vector<int>& nums, int begin, int end)
{
    // 判断数组是否为空或只有一个元素
    if (begin >= end) 
        return;

    int mid = begin + (end - begin) / 2;   // 计算中间位置

    // 递归排序左右两部分
    merge_sort(nums, begin, mid);
    merge_sort(nums, mid + 1, end);

    // 合并两个有序数组
    int left = begin, 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++]);

    // 将 temp 数组中的元素复制回 nums 数组中
    for (int i = begin; i <= end; ++i)
        nums[i] = temp[i - begin];
}

示例

下面分别以数组 {3,1,5,7,2,4,9,6,8} 和 {9,8,7,6,5,4,3,2,1} 为例，演示一下合并排序的过程。

示例一

输入：{3,1,5,7,2,4,9,6,8}

输出：{1,2,3,4,5,6,7,8,9}

            {3,1,5,7,2,4,9,6,8}
            /                \
       {3,1,5,7}            {2,4,9,6,8}
       /       \              /       \
    {3,1}     {5,7}        {2,4,9}   {6,8}
    /    \    /    \       /     \   /   \
   {3}   {1} {5}   {7}    {2,4}  {9} {6} {8} 
    \     /    \    /      /   \       /   \
   {1,3}  {5,7} {2,4,9}  {6,8,9} {}    {}    {}
     \    /       \        /     \       \   /
   {1,3,5,7}    {2,4,6,8,9}       {8,9}  {6,8}
       \           /                |     |
        \         /                 |     |
         \       /                  |     |
          \     /                   |     |
           \{1,2,3,4,5,6,7,8,9}-----{}  {8,9,6}
                      /                \   /
                     /                  \ /
                  {6,8,9}               {9,8,7,6,5,4,3,2,1}

示例二

输入：{9,8,7,6,5,4,3,2,1}

输出：{1,2,3,4,5,6,7,8,9}

            {9,8,7,6,5,4,3,2,1}
            /                \
           {9,8,7,6}        {5,4,3,2,1}
          /       \          /       \
         {9,8}   {7,6}     {5,4}    {3,2,1}
        /    \   /    \     /   \      /  \
       {9}   {8} {7}   {6} {5}  {4}   {3} {2,1}
        \     /    \    /      \      /    \
       {8,9} {6,7} {4,5} {2,3}  {1}   {1,2} {3}
         \    /      \      /   \   /            \
        {6,7,8,9}   {2,3,4,5}  {1}  {1,2,3}      {1,2,3}
          \             /       \        \         |
           \           /         {1,2,3,4,5,6,7,8,9}   |
            \{1,2,3,4,5,6,7,8,9}                      |
                                      /                \
                                     /                  \
                                  {6,7,8,9}            {1,2,3,4,5}
                                     |                  |
                                     |                  |
                                  {1,2,3,4,5,6,7,8,9}-----{1,2,3,4,5,6,7,8,9}

由上面两个示例可以看出，合并排序可以对任意长度的数组进行排序，其时间复杂度为 O(nlogn) ，这使得它成为了一个非常优秀的排序算法。