标题：【cpp】快速排序
@水墨不写bug
正文开始：
快速排序的局限性：
虽然快速排序是一种高效的排序算法，但也存在一些局限性：
最坏情况下的时间复杂度：如果选择的基准元素不合适，或者数组中存在大量重复的元素，快速排序的时间复杂度可能退化为O(n^2)。这种情况发生在每次划分之后，基准元素都是当前子数组中的最小或最大元素。
对于小规模数据的排序效果较差：当数组规模较小时，例如只有几个元素，快速排序[ 递归的消耗 ]的性能可能不如其他简单的排序算法，如插入排序或选择排序。
对于有序数组的排序效果较差：如果待排序的数组已经接近有序，快速排序的性能会下降。因为在划分过程中，基准元素的选择可能会导致子数组的不平衡，使得算法执行的时间增加。
快速排序是一种不稳定的排序算法：当原始数组中存在相等元素时，算法执行过程中可能会改变它们的相对顺序。
如何优化重复元素的问题，以免快排的时间复杂度退化为O（N^2）？
通过下面这一问题，我们或许会得到一些启发。
给定一个包含红色、白色和蓝色、共 个元素的数组 ，对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 、 和 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]示例 2：
输入：nums = [2,0,1] 输出：[0,1,2]
提示：
- 为 、 或
进阶：
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
颜色分类思想：
定义三个指针（left，cur，right）：
在排序过程中，这三个指针（left，cur，right），将数组分为四个部分，接下来希望你拿出纸笔跟我一起画一下：
四个部分：
一：【0，left】
二：【left+1，cur-1】
三：【cur，right-1】
四：【right，len-1】
主体思路是：
cur向后遍历，将小于1的元素放在left左边，等于1的元素不变位置，大于1的元素放在right的右边。
需要注意的细节是，对于（nums[cur] == 0 ）由于left是右闭区间，其指向的元素满足要求，所以要先自增再交换；交换之后cur++向后遍历。
对于（nums[cur] == 1）cur直接向后遍历；
对于（nums[cur] == 2）由于left是左闭区间，其指向的元素满足要求，所以要先自减再交换；right在交换之前指向的元素本身就是未遍历的元素，所以交换之后不需要cur自增，直接判断cur交换得到的未遍历的元素即可。
给你一个整数数组 ，请你将该数组升序排列。
示例 1：
输入：nums = [5,2,3,1] 输出：[1,2,3,5]示例 2：
输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5]
提示：
根据颜色分类的主体思想，如果用颜色分类来优化快排，那么这时再出现大量重复元素，就可以一次将他们排好序，不会再出现 在每次划分之后，基准元素都是当前子数组中的最小或最大元素的情况。
代码理解：
上述代码是用C++实现的快速排序算法，用于对一个整数数组进行排序。函数接收一个输入向量，并使用函数对其进行排序。
1.函数参数
函数是一个递归函数，用于执行快速排序算法。它接收三个参数：输入向量、左边界索引和右边界索引。
2.递归出口的定义
函数有一个基本情况，即如果左边界索引大于或等于右边界索引，那么只有一个元素或没有元素需要排序，所以函数返回。
3.key的选取
使用函数选择一个随机的轴元素（key），该函数在当前分区的范围内生成一个随机的索引。
4.递归主体
然后，函数将数组分为三部分：小于轴元素（key）的元素、等于轴元素（key）的元素和大于轴元素（key）的元素。它使用三个指针：、和。
指针从左边界索引开始，向右边界索引移动，并相应地交换元素。如果当前元素小于轴元素，则将其与指针处的元素交换，并同时递增这两个指针。如果当前元素等于轴元素，则递增指针。如果当前元素大于轴元素，则将其与指针处的元素交换，并递减指针。
分区完成后，函数在左子数组和右子数组上递归调用自身以进行排序。
5.函数
函数在给定的左边界和右边界索引范围内生成一个随机的索引。它使用函数生成一个随机数，然后通过对右边界和左边界索引之间的差值加一取模，并加上左边界索引来计算索引值。
6.函数
最后，在函数中，在开始排序过程之前，调用函数以用当前时间初始化随机数生成器，以确保每次运行程序时都会生成不同的随机数。
然后返回排序后的数组。
完~
未经作者同意禁止转载