NC140 #排序#

正好复习一下快速排序：
一定不要忘记加&!!!!!忘加了就寄了

class Solution {
public:
    void swap(vector<int>& arr, int a, int b)
    {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    int partition(vector<int>& arr, int left, int right)
    {
        int pivot = arr[left];
        while(left < right)
        {
            while(left < right && arr[right] >= pivot)
                right--;
            swap(arr, left, right);
            while(left < right && arr[left] <= pivot)
                left++;
            swap(arr, left, right);
        }
        return left;
    }

    void quickSort(vector<int>& arr, int left, int right)
    {
        if(left < right)
        {
            // 进行交换并确定pivot以用来分治
            int pivot = partition(arr, left, right);
            // 分治，递归
            quickSort(arr, left, pivot - 1);
            quickSort(arr, pivot + 1, right);
        }
    }

    vector<int> MySort(vector<int>& arr) {
        quickSort(arr, 0, arr.size() - 1);
        return arr;
    }
};