归并排序C++

本篇文章参考《大话数据结构》一书

归并排序（Merge Sort）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略将问题分成一些小的问题然后递归求解，即分而治之。

#include
using namespace std;
#include

#define initial_capacity 10
//归并排序
class Solution
{
public:

    vector merge_sort(vector& ans)
    {
        vectorres;
        res.resize(initial_capacity); //需要预先设置起始容量，防止越界
        int s = 0, t = ans.size() - 1;
        mySort(ans, res, s, t); 
        return res;
    }

    void mySort(vector& ans, vector& res, int s, int t)
    {
        vectortemp;
        temp.resize(initial_capacity);
        if (s == t)
            res[s] = ans[s];
        else
        {
            int m = (s + t) / 2;          //将ans数组平分为两个数组
            mySort(ans, temp, s, m);      //递归地将前数组归并为有序的temp数组
            mySort(ans, temp, m + 1, t);  //递归地将后数组归并为有序的temp数组
            myMerge(temp, res, s, m, t);  //将前两个数组归并为res有序数组
        }
    }

    void myMerge(vector& ans, vector& result, int i, int m, int n)
    //m,n分别为中间位置以及尾部位置
    {
        int j, k, l;
        for (j = m + 1, k = i; i <= m && j <= n; k++)
        {
            if (ans[i] < ans[j])
            {
                result[k] = ans[i++];
            }
            else
            {
                result[k] = ans[j++];
            }
        }

        //如果此时前数组未结束，而后数组结束时，将前数组剩余内容依次追加到结果数组
        if (i <= m)
        {
            for (l = 0; l <= m - i; l++)
            {
                result[k + l] = ans[i + l];
            }
        }

        //与上述反之
        if (j <= n)
        {
            for (l = 0; l <= n - j; l++)
            {
                result[k + l] = ans[j + l];
            }
        }

    }
};

//打印输出
void myPrint(vector& ans)
{
    for (int i = 0; i < ans.size(); i++)
    {
        cout << ans[i] << "  ";
    }
    cout << endl;
}

int main()
{
    vectorans = { 1,12,3,9,5,4,0,1,8,7 };

    Solution s;
    auto a = s.merge_sort(ans);
    myPrint(a);      //打印输出

    system("pause");
    return 0;
}