快速排序单边循环

LeetCode 912. 排序数组

双边循环写法

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        return quickSort(nums);
    }
    vector<int> quickSort(vector<int>& nums){
        int n = nums.size();
        quickCore(nums,0,n - 1);
        return nums;
    }
    void quickCore(vector<int>& nums,int left,int right){
        if(left >= right){
            return;
        }
        int base = nums[left];
        int l = left;
        int r = right;
        while(l < r){
            while(l < r && nums[r] >= base)--r;
            if(l < r)
                nums[l++] = nums[r];
            while(l < r && nums[l] <= base)++l;
            if(l < r)
                nums[r--] = nums[l];
        }
        nums[l] = base;
        quickCore(nums,left,l-1);
        quickCore(nums,l+1,right);
        return;
    }
};

单边循环快排

//运行时间20ms
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        return quickSort(nums);
    }
    vector<int> quickSort(vector<int>& nums){
        int n = nums.size();
        quickCore(nums,0,n - 1);
        return nums;
    }
    void quickCore(vector<int>& nums,int left,int right){
        if(left >= right){
            return;
        }
        int base = nums[left];//跟以前一样左边第一个为基准
        int m = left;
        for(int i = left + 1; i <= right; i++){
            //如果小于基准值，m加1，然后跟m位置交换（其实就是把比base小的数换到左边）
            if(nums[i] < base){
                m++;
                swap(nums[m],nums[i]);
            }
        }
        //把base换到空缺的位置（这时候num[m]肯定小于等于num[left]）
        swap(nums[m],nums[left]);
        quickCore(nums,left,m-1);
        quickCore(nums,m+1,right);
        return;
    }
};