题解 | #排序#

该题实现一个快速排序即可，注意vector是一个引用，否则函数调用后并不能改变vector

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> MySort(vector<int>& arr) {
        // write code here
        quick_sort(arr,0,arr.size() - 1);
        return arr;
    }

    void quick_sort(vector<int>& a, int left, int right)
    {
        if(left >= right)
            return;
        int pivot = parti(a,left,right);
        quick_sort(a,left,pivot-1);
        quick_sort(a,pivot+1,right);
    }

    int parti(vector<int>& a, int left, int right)
    {
        int i = left;
        int j = right;
        int tmp = a[left];

        while(i < j)
        {
            while(i<j && a[j] >= tmp)
                j--;
            while(i<j && a[i] <= tmp)
                i++;

            if(i < j)
            {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        a[left] = a[i];
        a[i] = tmp;
        return i;
    }
};