一、基本思想
快速排序采用分治法策略，将一个大数组（或子数组）分为两个小数组，然后递归地对这两个小数组进行排序。其基本思想可以概括为“分解、解决、合并”三个步骤：
- 分解：将原问题（即待排序的数组）分解为若干个规模较小、相互独立且与原问题形式相同的子问题（即子数组）。
- 解决：若子问题规模较小而容易被解决（即子数组的长度较小），则直接进行排序；否则，递归地解各个子问题。
- 合并：由于快速排序是就地排序（即在原数组上进行排序，不需要额外的存储空间），所以子数组排序完成后，原数组也就排序完成了，不需要额外的合并步骤。
二、具体实现
快速排序的具体实现包括以下几个关键步骤：
- 选择基准：从待排序序列中选择一个元素作为基准（Pivot）。基准的选择可以影响排序的效率，常见的选择方法包括选择第一个元素、最后一个元素、中间元素或随机选择。
- 分区：通过一趟扫描，将数组分为两个部分。在分区完成后，基准元素将处于其最终位置（即左侧的元素都小于等于基准，右侧的元素都大于基准）。分区过程通常使用两个指针（i和j）来进行：i指针从左到右扫描数组，找到第一个大于基准的元素；j指针从右到左扫描数组，找到第一个小于等于基准的元素。然后交换i和j指向的元素，直到i和j相遇或交错。
- 递归排序：对基准元素左侧和右侧的子数组进行递归调用快速排序。
三、示例题目
1.颜色分类. - 力扣（LeetCode）
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1] 输出：[0,1,2]
解法(快排思想-三指针法使数组分三块):
算法思路:
类比数组分两块的算法思想，这里是将数组分成三块，那么我们可以再添加一个指针，实现数组分三块。
设数组大小为 n，定义三个指针 left，cur，right:
- left:用来标记 0 序列的末尾，因此初始化为 -1;
- cur:用来扫描数组，初始化为0;
- right:用来标记 2 序列的起始位置，因此初始化为n。
在cur 往后扫描的过程中，保证:
- [0，left]内的元素都是 0;
- [left +1，cur -1]内的元素都是 1;
- [cur，right-1]内的元素是待定元素。
- [right，n]内的元素都是 2。
算法流程:
a.初始化cur =0，left =-1,right = numsSize;
b.当 cur < right 的时候(因为 right 表示的是 2 序列的左边界，因此当 cur碰到right 的时候，说明已经将所有数据扫描完毕了)，一直进行下面循环:
根据 nums[cur]的值，可以分为下面三种情况:
- nums[cur]== 0;说明此时这个位置的元素需要在 left +1的位置上，因此交换 left +1与 cur 位置的元素，并且让 left++(指向 0 序列的右边界)，(为什么可以 ++呢，是因为 left +1 位置要么是0，要么是 cur ，交换完毕之后，这个位置的值已经符合我们的要求，因此cur++）；
- nums[cur]== 1;说明这个位置应该在 left 和 cur 之间，此时无需交换，直接让cur++，判断下一个元素即可;
- nums[cur]== 2;说明这个位置的元素应该在 right -1 的位置，因此交换right-1与cur 位置的元素，并且让right-- (指向 2 序列的左边界)cur 不变(因为交换过来的数是没有被判断过的，因此需要在下轮循环中判断)
c.当循环结束之后:
- [0，left]表示0序列;
- [left + 1, right-1]表示 1 序列;
- [right, numsSize-1]表示 2 序列 。
class Solution { public: void sortColors(vector<int>& nums) { int n=nums.size(); int cur=0,left=-1,right=n; while(cur<right) { if(nums[cur]==0) { swap(nums[++left],nums[cur++]); } else if(nums[cur]==1) { cur++; } else if(nums[cur]==2) { swap(nums[--right],nums[cur]); } } } };2.快速排序. - 力扣（LeetCode）
给你一个整数数组 nums，请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。
示例 1：
输入：nums = [5,2,3,1] 输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5]
解法(数组分三块思想+随机选择基准元素的快速排序)
算法思路:
快排最核心的一步就是 Partition(分割数据):将数据按照一个标准，分成左右两部分。
如果我们使用荷兰国旗问题的思想，将数组划分为 左中右 三部分:左边是比基准元素小的数据，中间是与基准元素相同的数据，右边是比基准元素大的数据。然后再去递归的排序左边部分和右边部分即可(可以舍去大量的中间部分)
在处理数据量有很多重复的情况下效率会大大提升。
算法流程:
随机选择基准算法流程:
函数设计:int randomKey(vector<int>& nums, int left, int right)
- a.在主函数那里种一颗随机数种子;
- b.在随机选择基准函数这里生成一个随机数;
- c.由于我们要随机产生一个基准，因此可以将随机数转换成随机下标: 让随机数 % 上区间大小，然后加上区间的左边界即可。
快速排序算法主要流程:
- 定义递归出口;
- 利用随机选择基准函数生成一个基准元素;
- 利用荷兰国旗思想将数组划分成三个区域;
- 递归处理左边区域和右边区域。
class Solution {
public:
vector<int> sortArray(vector<int>& nums)
{
srand(time(nullptr));//种下一个随机数种子
qsort(nums,0,nums.size()-1);
return nums;
}
void qsort(vector<int>&nums,int l,int r)
{
if(l>=r)
return;
//数组分三块
int key=getRand(nums,l,r);
int i=l,left=l-1,right=r+1;
while(i<right)
{
if(nums[i]<key)
{
swap(nums[i++],nums[++left]);
}
else if(nums[i]>key)
{
swap(nums[i],nums[--right]);
}
else
i++;
}
//[l,left] [left+1,right-1] [right,r]
qsort(nums,l,left);
qsort(nums,right,r);
}
int getRand(vector<int>&nums,int left,int right)
{
int r=rand();
return nums[r%(right-left+1)+left];
}
};3.快速选择算法
数组中的第K个最大元素. - 力扣（LeetCode）
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4],k = 2 输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4 输出: 4
解法(快速选择算法)
算法思路:
在快排中，当我们把数组「分成三块」之后:[l，left] [left + 1，right - 1] [right，r]，我们可以通过计算每一个区间内元素的「个数」，进而推断出我们要找的元素是在「哪一个区间」里面。
那么我们可以直接去「相应的区间」去寻找最终结果就好了。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
srand(time(nullptr));
int ret = getKMax(nums, 0, nums.size() - 1, k);
return ret;
}
int getKMax(vector<int>& nums, int l, int r, int k)
{
if (l == r)
return nums[l];
int key = getRand(nums, l, r);
int i = l, left = l - 1, right = r + 1;
while (i < right)
{
if (nums[i] < key)
{
swap(nums[i++], nums[++left]);
}
else if (nums[i] > key)
{
swap(nums[i], nums[--right]);
}
else
{
i++;
}
}
//分情况讨论
if (r - right+1 >= k)
{
return getKMax(nums, right, r, k);
}
else if (r - left >= k)
{
return key;
}
else
{
return getKMax(nums, l, left, k - (r - left));
}
}
int getRand(vector<int>&nums,int left,int right)
{
int r=rand();
return nums[r%(right-left+1)+left];
}
};4.库存管理Ⅲ. - 力扣（LeetCode）
仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。
示例 1：
输入：stock = [2,5,7,4], cnt = 1 输出：[2]
示例 2：
输入：stock = [0,2,3,6], cnt = 2 输出：[0,2] 或 [2,0]
解法(快速选择算法)
算法思路:
在快排中，当我们把数组「分成三块」之后:[l，left] [left +1，right - 1] [right，r]，我们可以通过计算每一个区间内元素的「个数」，进而推断出最小的k个数在哪些区间里面。
那么我们可以直接去「相应的区间」继续划分数组即可。
class Solution {
public:
vector<int> inventoryManagement(vector<int>& nums, int k)
{
srand(time(NULL));
getKmin(nums,0,nums.size()-1,k);
return {nums.begin(),nums.begin()+k};
}
void getKmin(vector<int>&nums,int l,int r,int k)
{
if(l>=r)
return;
int key=getRand(nums,l,r);
int left=l-1,right=r+1,i=l;
while(i<right)
{
if(nums[i]<key)
{
swap(nums[i++],nums[++left]);
}
else if(nums[i]>key)
{
swap(nums[i],nums[--right]);
}
else
{
i++;
}
}
int a=left-l+1,b=right-left-1;
if(a>k)
{
getKmin(nums,l,left,k);
}
if(a+b>=k)
{
return;
}
else
{
getKmin(nums,right,r,k-a-b);
}
}
int getRand(vector<int>&nums,int l,int r)
{
return nums[rand()%(r-l+1)+l];
}
};标签：right,cur,nums,int,分治,C++,快排,数组,left From： https://blog.csdn.net/m0_74826386/article/details/143455294