2.2：归并排序

一：归并操作

在本节中我们所讨论的算法都基于归并这个简单的操作，即将两个有序数组归并成一个：

void sort(vector<int> &arr, int start, int mid, int end){
    int i=start, j= mid+1;
    vector<int> arrcopy;
    for (int k = 0; k <= end; ++k)
    {
        arrcopy.push_back(arr[k]);
    }
    for (int k = start; k <= end; ++k)
    {
        if (i > mid){ arr[k] = arrcopy[j++]; } //剩下的走完
        else if (j > end){ arr[k] = arrcopy[i++]; }
        else
        {
            //谁小谁走
            if (arrcopy[j] < arrcopy[i]){ arr[k] = arrcopy[j++]; }
            else{ arr[k] = arrcopy[i++]; }
        }                                    
    }
}

自顶向下的递归归并排序

class MergeSort
{
private:
    static vector<int> aux;//归并所需的辅助数组
public:

    static void merge(vector<int> &arr, int start, int mid, int end)
    {
        int i = start, j = mid + 1;
        vector<int> arrcopy;
        for (int k = 0; k <= end; ++k)
        {
            arrcopy.push_back(arr[k]);
        }
        for (int k = start; k <= end; ++k)
        {
            if (i > mid){ arr[k] = arrcopy[j++]; }
            else if (j > end){ arr[k] = arrcopy[i++]; }
            else
            {
                if (arrcopy[j] < arrcopy[i]){ arr[k] = arrcopy[j++]; }
                else{ arr[k] = arrcopy[i++]; }
            }
        }
    }
//首先记住，只有一个数的数组是有序的
//sort的递归调用只是负责把原数组分开，一直细分直到就剩下一个元素，即满足hi<=hi
//然后return，至此并无排序功能，排序的实现主要在merge，那么为什么要用递归分开呢？
//因为递归能最简单地做到入栈出栈效果，且分到最后，单个元素一定有序，然后再merge
    static void sort(vector<int> &arr, int start, int end)
    {
        if (start >= end){ return; }
        int mid = start + (end - start) / 2;
        sort(arr, start, mid);
        sort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }
};

自底向上的非递归归并排序

这个更好理解

class MergeSort
{
private:
    static vector<int> aux;//归并所需的辅助数组
public:

    static void merge(vector<int> &arr, int start, int mid, int end)
    {
        int i = start, j = mid + 1;
        vector<int> arrcopy;
        for (int k = 0; k <= end; ++k)
        {
            arrcopy.push_back(arr[k]);
        }
        for (int k = start; k <= end; ++k)
        {
            if (i > mid){ arr[k] = arrcopy[j++]; }
            else if (j > end){ arr[k] = arrcopy[i++]; }
            else
            {
                if (arrcopy[j] < arrcopy[i]){ arr[k] = arrcopy[j++]; }
                else{ arr[k] = arrcopy[i++]; }
            }
        }
    }

    static void sort(vector<int> &arr)
    {
        int N = arr.size();
        for (int sz = 1; sz < N; sz *= 2) //子数组每次是原来的两倍
        {
            for (int start = 0; start < N - sz; start += 2 * sz)
            {
                //最后一个子数组的大小只有在数组大小是sz的偶数倍的情况下等于sz，否则就小于
                merge(arr, start, start + sz - 1, min(start + 2 * sz - 1, N - 1));
            }
        }
    }
};