快排练习题旨在熟悉快排操作与快排延伸的快速选择算法.
颜色分类
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];}
};
