归并排序算法（优化版）——C++

关于归并排序的介绍可以参考这边博客：归并排序算法（经典返回变量版）——C++_净无邪博客-CSDN博客。本文主要是对递归排序进行优化。

由于经典版本返回临时变量的归并排序效率比较低，需要多每次创建临时空间进行优化，使用一个固定内存空间，这样可以减少每次创建和销毁内存空间的时间消耗，由于这部分很费时间，所以优化效果是比较明显的。

优化版跟基本版的区别主要区别如下：

1.归并函数原来是入参两个数组，优化后入参为两个待排序数组合并在一起的起始和截止位置，如下所示：

void merge1(vector& nums, int start, int end, vector& tmpNums); // 优化后版本
vector merge(vector& nums1, vector& nums2); // 优化前版本

由上面代码可知，优化后除了包含两个有序代码数组的起始和截止位置，还多了一个存储临时变量的数组

2.归并排序进行“分”的二分法操作时，递归顺序仍然和原来一样都是先递归遍历左边元素再遍历右边元素，等两边元素都有序后再调用合并函数将两个有序数组合并成一个数组存储在临时存储空间tmpNums中。

优化后递归函数

void Sorts::merge(vector& nums, int start, int end, vector& tmpNums)
{
    if (start == end) //递归终止条件：如果起始下标等于结束下标，则终止递归
        return; // 返回
    int middle = (start + end) / 2; // 分治法，采用二分法，取中间下标开始左右递归，直到一个元素开始返回
    merge(nums, start, middle, tmpNums); // 先递归左边部分，退出该层后向右递归，直到一个元素
    print(tmpNums);
    merge(nums, middle + 1, end, tmpNums); // 先左边再右边递归取有序数组
    merge1(nums, start, end, tmpNums); // 合并两个有序数组，然后继续回退到上一层左边或者右边递归，直到整个递归结束返回为止
}

经典递归函数：

vector Sorts::merge(vector& nums, int start, int end)
{
    if (start == end) //递归终止条件：如果起始下标等于结束下标，则终止递归
        return { nums[start] }; // 返回左边第一个元素
    int middle = (start + end) / 2; // 分治法，采用二分法，取中间下标开始左右递归，直到一个元素开始返回
    auto left = merge(nums, start, middle); // 先递归左边部分，退出该层后向右递归，直到一个元素
    auto right = merge(nums, middle + 1, end); // 先左边再右边递归取有序数组    
    return merge(left, right); // 合并两个有序数组，然后继续回退到上一层左边或者右边递归，直到整个递归结束返回为止
}

3.将两个有序数组合并成一个数组时，需要内部再划分左右区间，由于原来是按照这种取中间值合并在一起的，所以重新划分的时候只需要取中间值即可。

然后后面依次遍历两个区间，将较小值放入临时存储空间，最后将临时存储空间的值存放在待排序原数组内完成一趟排序；就这样直到整个递归结束完后，整个原来数组已经完成排序。

void Sorts::merge1(vector& nums, int start, int end, vector& tmpNums)
{
    int middle = (start + end) / 2; // 重新划分区间和确定两个区间下标索引
    int start1 = start;
    int end1 = middle;
    int start2 = middle + 1;
    int end2 = end;
    int index1 = start1;
    int index2 = start2;
    int index = start1;
    while (index1 <= end1 && index2 <= end2)
    {
        if (nums[index1] <= nums[index2])
        {
            tmpNums[index] = nums[index1];
            ++index1;
            ++index;
        }
        else
        {
            tmpNums[index] = nums[index2];
            ++index2;
            ++index;
        }
    }
    while (index1 <= end1)
    {
        tmpNums[index] = nums[index1];
        ++index1;
        ++index;
    }
    while (index2 <= end2)
    {
        tmpNums[index] = nums[index2];
        ++index2;
        ++index;
    }
    
    for (int i = start; i <= end; ++i) // 跟经典返回临时变量归并排序区别之一：将区间待排序数据拷贝到原来待排序数组内
    {
        nums[i] = tmpNums[i];
    }
}

跟原来经典返回临时变量归并排序的主要区别是：在内部重新划分两个有序区间，排好序后将临时空间的数据拷贝到原来数组待排序区间完成局部排序。

4.下面是完整的优化后归并排序算法代码

Sorts.h

#pragma once

#include 
#include 

using namespace std;

struct Sorts {    
    void merge(vector& nums);
    
    void print(vector& nums);

private:    
    void merge(vector& nums, int start, int end, vector& tmpNums);
    void merge1(vector& nums, int start, int end, vector& tmpNums);
};

Sorts.cpp

#include "Sorts.h"

void Sorts::merge(vector& nums)
{
    if (nums.size() <= 1)
    {
        return;
    }
    auto tmpNums = merge(nums, 0, nums.size() - 1);
    nums = tmpNums;
}

void Sorts::print(vector& nums)
{
    for (const auto& it : nums)
        cout << it << ",";
    cout << endl;
}

void Sorts::merge(vector& nums, int start, int end, vector& tmpNums)
{
    if (start == end) //递归终止条件：如果起始下标等于结束下标，则终止递归
        return; // 返回
    int middle = (start + end) / 2; // 分治法，采用二分法，取中间下标开始左右递归，直到一个元素开始返回
    merge(nums, start, middle, tmpNums); // 先递归左边部分，退出该层后向右递归，直到一个元素
    print(tmpNums);
    merge(nums, middle + 1, end, tmpNums); // 先左边再右边递归取有序数组
    merge1(nums, start, end, tmpNums); // 合并两个有序数组，然后继续回退到上一层左边或者右边递归，直到整个递归结束返回为止
}

void Sorts::merge1(vector& nums, int start, int end, vector& tmpNums)
{
    int middle = (start + end) / 2;
    int start1 = start;
    int end1 = middle;
    int start2 = middle + 1;
    int end2 = end;
    int index1 = start1;
    int index2 = start2;
    int index = start1;
    while (index1 <= end1 && index2 <= end2)
    {
        if (nums[index1] <= nums[index2])
        {
            tmpNums[index] = nums[index1];
            ++index1;
            ++index;
        }
        else
        {
            tmpNums[index] = nums[index2];
            ++index2;
            ++index;
        }
    }
    while (index1 <= end1)
    {
        tmpNums[index] = nums[index1];
        ++index1;
        ++index;
    }
    while (index2 <= end2)
    {
        tmpNums[index] = nums[index2];
        ++index2;
        ++index;
    }
    
    for (int i = start; i <= end; ++i)
    {
        nums[i] = tmpNums[i];
    }
}

main.cpp

 #include 
#include "Sorts.h"

using namespace std;

int main()
{
    vector nums = { 2,0,1,6,8,10,5,99,87,333,2,0,1 };
    Sorts sorts;
    sorts.print(nums);
    sorts.merge(nums);
    sorts.print(nums);
   
	return 1;
}

输出结果：

由上面的输出结果可知，归并排序递归的顺序每次都是先遍历左区间再遍历右区间，结果排序正确。 

其实还可以继续优化，优化的是函数merge1(...)里面的临时变量，插入下标可以优化为:

index = start1 + index1 - start1 + index2 - start2 == index1 + index2 - start2 ;

本文不继续优化了，再优化就不好理解，故暂时只讨论到这里。