题解 | #牛的品种排序II#

知识点：

排序/归并排序

分析：

总结归并思路

1.有数组 q, 左端点 l, 右端点 r

2.确定划分边界 mid

3.递归处理子问题 q[l..mid], q[mid+1..r]

4.合并子问题

1.主体合并

至少有一个小数组添加到 tmp 数组中

2.收尾

可能存在的剩下的一个小数组的尾部直接添加到 tmp 数组中

3.复制回来

tmp 数组覆盖原数组

完整代码C++：

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param cows int整型vector
     * @return int整型vector
     */
    void mergeSort(vector<int>& q, int l, int r) {
        if (l >= r) return ;
        int mid = l + r >> 1;
        mergeSort(q, l, mid);
        mergeSort(q, mid + 1, r);
        int p1 = l;
        int p2 = mid + 1;
        int tmp[q.size()];
        int k = 0;
        while (p1 <= mid && p2 <= r) {
            tmp[k++] = q[p1] < q[p2] ? q[p1++] : q[p2++];
        }
        while (p1 <= mid) {
            tmp[k++] = q[p1++];
        }
        while (p2 <= r) {
            tmp[k++] = q[p2++];
        }
        for (int i = l, j = 0; i <= r; i++, j++) {
            q[i] = tmp[j];
        }

    }
    vector<int> sortCows(vector<int>& cows) {
        mergeSort(cows,0,cows.size() - 1);
        return cows;
    }
};