《算法题讲解指南：优选算法-分治-快排》--43.颜色分类，44.排序数组
🔥小叶-duck：个人主页
❄️个人专栏：《Data-Structure-Learning》
《C++入门到进阶&自我学习过程记录》《算法题讲解指南》--优选算法
✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游
目录
43.颜色分类
题目链接：
75. 颜色分类 - 力扣（LeetCode）
题目描述：
题目示例：
解法（快排思想——三指针法使数组分三块）：
算法思路:
类比数组分两块的算法思想，这里是将数组分成三块，那么我们可以再添加一个指针，实现数组分三块。
设数组大小为 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 - 1 ]内的元素都是2。
C++算法代码：
class Solution { public: void sortColors(vector<int>& nums) { int left = -1, right = nums.size(), i = 0; while(i < right) { if(nums[i] > 1) { swap(nums[i], nums[--right]); } else if(nums[i] < 1) { swap(nums[i++], nums[++left]); } else { i++; } } } };算法总结及流程解析：
44.排序数组
题目链接：
912. 排序数组 - 力扣（LeetCode）
题目描述：
题目示例：
解法(数组分三块思想+随机选择基准元素的快速排序)：
算法思路：
我们在数据结构阶段学习的快速排序的思想可以知道，快排最核心的一步就是 Partition (分割数据)：将数据按照一个标准，分成左右两部分。
如果我们使用荷兰国旗问题的思想，将数组划分为左中右三部分：左边是比基准元素小的数据，中间是与基准元素相同的数据，右边是比基准元素大的数据。然后再去递归的排序左边部分和右边部分即可(可以舍去大量的中间部分)。
在处理数据量有很多重复的情况下，效率会大大提升。
C++算法代码：
class Solution { public: void quicksort(vector<int>& nums, int l, int r) { if(l >= r) { return; } int ra = rand(); int key = nums[ra % (r - l + 1) + l]; //控制随机数的范围在[left, right] int i = l; int left = l - 1; int right = r + 1; while(i < right) { if(nums[i] > key) { swap(nums[i], nums[--right]); } else if(nums[i] < key) { swap(nums[i++], nums[++left]); } else { i++; } } quicksort(nums, l, left); quicksort(nums, right, r); } vector<int> sortArray(vector<int>& nums) { srand(time(NULL)); //种下一个随机数种子 quicksort(nums, 0, nums.size() - 1); return nums; } }; 这里提一句，之前我们学习快排原理数据结构之排序-选择排序&交换排序中实现快排代码使用的获取key的方法是三数取中，这里也能通过，但不进行展示了，只是把三数取中的代码放在下面供大家查看：
而且相较于之前实现快排的代码，这里使用的数组分三块在效率上是非常快的。因为之前所学的实现快排只是将数组分成两块，如果一个数组相同元素过多就会导致算法复杂度退化，而分成三块后则相同的key则会被忽略。
算法总结及流程解析：
结束语
到此，43.颜色分类，44.排序数组 这两道算法题就讲解完了。颜色分类：采用三指针法将数组分为0、1、2三个区间，通过left、cur、right指针实现高效分区。排序数组：在传统快排基础上引入荷兰国旗问题的三区划分思想，配合随机基准选择，有效处理重复元素，提升排序效率。希望大家能有所收获！
