快速排序练习

快排练习题旨在熟悉快排操作与快排延伸的快速选择算法.

颜色分类

75. 颜色分类 - 力扣（LeetCode）

思路

本题需要用到快排（以从小到大为例）的思想：选取一个key，将比key小的放到前面，比key大的放到后面。对于本题，我们需要用到三个指针：left, right, i.

left到数组左边范围是比key小的，left到i范围是与key相等的，i到right是还没有排序的，right到数组右边是比key大的。这即为我们所期望的。

对于本题来说，取特定值即可。

代码

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

排序数组 

912. 排序数组 - 力扣（LeetCode）

思路

key的选取：先通过时间函数time()对rand()函数取种子，在通过rand()函数取随机值作为key值，这么做是为了防止key值取得过大或过小，随机值靠中间的期望较大。将随机值模上所要区间的长度随机值的范围即为0到right，再加上left即为left到right的值。

int getRandom(vector<int>& nums, int left, int right)
{
    int r = rand();
    return nums[r % (right - left + 1) + left];
}

 最后再进行递归即可实现快速排序。

qsort(nums, l, left);

qsort(nums, right, r);

代码 

vector<int> sortArray(vector<int>& nums)
{
    srand(time(NULL));
    qsort(nums, 0, nums.size() - 1);
    return nums;
}

void qsort(vector<int>& nums, int l, int r)
{
    if (l >= r) return;
    int key = getRandom(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]);
    }
    qsort(nums, l, left);
    qsort(nums, right, r);
}

int getRandom(vector<int>& nums, int left, int right)
{
    int r = rand();
    return nums[r % (right - left + 1) + left];
}

 数组中的第K个最大元素

215. 数组中的第K个最大元素 - 力扣（LeetCode）

思路

本题根据快排的思想，将数组分为三块。找最大的第K个元素，我们就从最右边的那块数组开始找

对比上一题的代码，需要改变的只是递归的法则，abc分别是分成三块的数组各自的长度。如果c>=k,在c区递归；如果b+c>=k,则直接返回key;否则，则在a 处递归。

int c = r - right + 1, b = right - left - 1;

if(c >= k) return qsort(nums, right, r, k);

else if(b + c >= k) return key;

else return qsort(nums, l, left, k - b - c);

代码 

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

    int qsort(vector<int>& nums, int l, int r, int k)
    {
        if (l == r) return nums[l];
        int key = getRandom(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 qsort(nums, right, r, k);
        else if (b + c >= k) return key;
        else return qsort(nums, l, left, k - b - c);

    }

    int getRandom(vector<int>& nums, int left, int right)
    {
        int r = rand();
        return nums[r % (right - left + 1) + left];
    }
};

 库存管理III

LCR 159. 库存管理 III - 力扣（LeetCode）

思路

本题实质是返回最小的前k个数。与上题相反，寻找最小的值，我们先从a区开始找

int a = left - l + 1, b = right - left - 1;
if (a > k) qsort(nums, l, left, k);
else if (a + b >= k)  return;
else return qsort(nums, right, r, k - a - b);

代码 

class Solution
{
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt)
    {
        srand(time(NULL));
        qsort(stock, 0, stock.size() - 1, cnt);
        return { stock.begin(), stock.begin() + cnt };
    }
    void qsort(vector<int>& nums, int l, int r, int k)
    {
        if (l >= r) return;
        int key = getRandom(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 a = left - l + 1, b = right - left - 1;
        if (a > k) qsort(nums, l, left, k);
        else if (a + b >= k)  return;
        else return qsort(nums, right, r, k - a - b);

    }

    int getRandom(vector<int>& nums, int left, int right)
    {
        int r = rand();
        return nums[r % (right - left + 1) + left];
    }
};