题解 | #排序#

直接使用快速排序的思路

Java里可以直接用sort函数，二路归并、堆排序也可以达到算法要求

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> MySort(vector<int>& arr) {
        quickSort(arr,0,arr.size()-1);
        return arr;
    }
  //递归调用算法quickSort，逐步划分数组空间
    void quickSort(vector<int>& arr,int left,int right){
        if(left>=right){return;}
        int tmp=partSort(arr,left,right);
        quickSort(arr,left,tmp-1);
        quickSort(arr,tmp+1,right);
    }
  //交换算法
    int partSort(vector<int>&arr,int left,int right){
        int divNum =arr[left];
        int le=left;
        for(int i=le+1;i<=right;i++){
            if(arr[i]<=divNum){
                le++;
                swap(arr[i],arr[le]);
            }
        }
        swap(arr[le],arr[left]);
        return le;
    }
};