题解 | #排序#

c++快排，直接上代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> MySort(vector<int>& arr) {
        // write code here
        if(arr.size() < 2){
            return arr;
        }
        QuickSort(arr, 0, arr.size()-1);
        return arr;
    }
    void QuickSort(vector<int>& arr, int begin, int end){
        if(begin==end){
            return;
        }
        int index = Partion(arr, begin, end);
        if(index>begin){
            QuickSort(arr, begin, index-1);
        }
        if(index<end){
            QuickSort(arr, index + 1, end);
        }
    }
    int Partion(vector<int>& arr, int begin, int end){
        int small;
        int index;
        index = RandRange(begin, end);
        Swap(arr[index], arr[end]);
        small = begin - 1;
        for(int index=begin;index<=end;index++){
            if(arr[index] < arr[end]){
                small++;
                if(small != index){
                    Swap(arr[small], arr[index]);
                }
            }
        }
        small++;
        Swap(arr[end], arr[small]);
        return small;
    }
    int RandRange(int begin, int end){
        return rand()%(end-begin + 1) + begin;
    }
    void Swap(int & a, int & b){
        int temp;
        temp = a;
        a = b;
        b = temp;
    }
};