快速排序

目录

例1

例2

例3

例4

例1

75. 颜色分类

由 < key; == key ; > key三段

左区间[0, left]

中区间[left + 1， right - 1]

右区间[right, r]

分析：i是从左往右边遍历，左边的数据是< 或者 = i的，是对的，通过swap过来的nums[--right]是未知的，左边的nums[++left]这个值不是 = key就是<key,②i<right ,right位置是已经判定过的,所以不用=

参考代码

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left = -1, right = nums.size(), i = 0;
        while(i < right)
        {
            if(nums[i] == 0) swap(nums[++left], nums[i++]);
            else if(nums[i] == 1) i++;
            else swap(nums[--right], nums[i]);
        }
    }
};

例2

912. 排序数组

题目：写一快速排序

①采用随机下标

②l >= r 区间不存在，或者区间里只有一个值

③rand()%(r - l + 1) + l ：取模个数，正好对应下标，后面的+l是相对偏移量还是到区间[l, r]取

④[l, r] 是进行排序的区间，[l, left]是 "< key" 的区间;如果key是最小值，就会区间不存在

[left + 1, right - 1] 是"==key"的区间， 至少一个

[right, r] 是" > key "的区间；key最大值，就会区间不存在

参考代码

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        srand(time(NULL));
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }
    void quickSort(vector<int>& nums, int l, int r)
    {
        if(l >= r) return;
        int key = randomKey(nums, l, r);
        int left = l - 1, right = r + 1, i = l;
        while(i < right)
        {
            if(nums[i] < key) swap(nums[++left], nums[i++]);
            else if(nums[i] == key) i++;
            else swap(nums[--right], nums[i]);
        }
        quickSort(nums, l, left);
        quickSort(nums, right, r);
    }
    int randomKey(vector<int>& nums, int l, int r)
    {
        return nums[rand()%(r - l + 1) + l];
    }
};

例3

215. 数组中的第K个最大元素

解析:第K大，那么就if，else选则一边的quickSort

注意：发现这里的if(l >= r) 改成" == "也是对的，也就是说这里的num[l]改成num[r]也是一样的，那么就说明这里不会出现区间不存在的情况？？

这里只有两个return会退出quickSort，因为k是在[1, nums.size()]，也就是一定是找的到的，那么不断缩小的区间：[l, r] 一定是有效的，其实本质是这里的if，else，无效的区间是进不去的，但是例4不行

参考代码

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(NULL));
        return quickSort(nums, 0, nums.size() - 1, k);
    }

    int quickSort(vector<int>& nums, int l, int r, int k)
    {
        if(l >= r) return nums[l];//== 也对
        int key = randomkey(nums, l, r);
        int i = l, left = l - 1, right = r + 1;
        while(i < right)
        {
            if(nums[i] < key) swap(nums[++left], nums[i++]);
            else if(nums[i] == key) i++;
            else swap(nums[--right], nums[i]);
        }
        int c = r - right + 1, b = right - left - 1;
        if(c >= k) return quickSort(nums, right, r, k);
        else if(c + b >= k) return key;
        else return quickSort(nums, l, left, k - c - b);
    }
    int randomkey(vector<int>& nums, int l, int r)
    {
        return nums[rand()%(r - l + 1) + l];
    }
};

例4

LCR 159. 库存管理 III

注：这里的cnt很坑啊，竟然可以等于0,所以要>=；如果要改成==(写的时候都写>=就行),只要在srand上面加一个判断就行：if(cnt == 0) return {};

②下面的选择区间里的判断 a 是>=cnt 等号不忘，a就是个数

参考代码

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        srand(time(NULL));
        Sort(stock, 0, stock.size() - 1, cnt);
        return {stock.begin(), stock.begin() + cnt};      
    }
    void Sort(vector<int>& stock, int l, int r, int cnt)
    {
        if(l >= r) return;//==不对
        int key = randomkey(stock, l, r);
        int i = l, left = l - 1, right = r + 1;
        while(i < right)
        {
            if(stock[i] < key) swap(stock[++left], stock[i++]);
            else if(stock[i] == key) i++;
            else swap(stock[--right], stock[i]);
        }
        int a = left - l + 1, b = right - left - 1;
        if(a >= cnt) Sort(stock, l, left, cnt);
        else if(a + b >= cnt) return;
        else Sort(stock, right, r, cnt - a - b);
    }
    int randomkey(vector<int>& nums, int l, int r)
    {
        return nums[rand()%(r - l + 1) + l];
    }
};