题解 | #排序#

#include <math.h>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */

    void MergeSort(vector<int> &arr,vector<int> &temp,int l,int r)
    {
        if(l < r)
        {
            int m = (l + r) / 2;
            MergeSort(arr,temp,l,m);
            MergeSort(arr,temp,m+1,r);
            Sort(arr,temp,l,m+1,r);
        }

    }

    void Sort(vector<int>& arr,vector<int> temp,int l,int m,int r)
    {
        int leftIndex = l;
        int  rightIndex = m;
        int index = l;
        while(leftIndex <= m-1 && rightIndex <= r)
        {
            if(arr[leftIndex] <= arr[rightIndex])
            {
                temp[index++] = arr[leftIndex++];
            }
            else {
                temp[index++] = arr[rightIndex++];
            }
        }
        while(leftIndex <= m-1)
        {
            temp[index++] = arr[leftIndex++];
        }
        while(rightIndex <= r)
        {
            temp[index++] = arr[rightIndex++];
        }
        for(int i = l;i <= r;i++)
        {
            arr[i] = temp[i];
        }
    }

    vector<int> MySort(vector<int>& arr) {
        // write code here
        vector<int> temp(arr.size(),0);
        MergeSort(arr,temp,0,arr.size()-1);
        return arr;
    }
};