【优选算法篇】化繁为简，见素抱朴：从乱象中重构秩序的艺术

文章目录

• 分治专题（一）：快速排序核心思想与应用
  • 前言
  • 第一章：快速排序的应用与延展
    • 1.1 颜色分类（medium）
      • 解法（分治思想 - 三指针法实现三分）
      • C++ 代码实现
      • 易错点提示
      • 时间复杂度和空间复杂度
    • 1.2 快速排序（medium）
      • 解法（数组分三块 + 随机基准元素的快速排序）
      • C++ 代码实现
      • 易错点提示
      • 时间复杂度和空间复杂度
    • 1.3 快速选择算法（medium）
      • 解法（快速选择算法）
      • C++ 代码实现
      • 易错点提示
      • 时间复杂度和空间复杂度
    • 1.4 最小的 k 个数（medium）
      • 解法（快速选择算法）
      • C++ 代码实现
      • 易错点提示
      • 时间复杂度和空间复杂度
  • 写在最后

分治专题（一）：快速排序核心思想与应用

🚀 欢迎讨论：如果你有任何问题或见解，欢迎在评论区留言。

👍 点赞、收藏与分享：如果觉得这篇文章对你有帮助，请点赞、收藏并分享给更多朋友。

💡 分享给更多人：一起学习分治策略，掌握快速排序的精髓！

前言

快速排序不仅是一种算法，更是一种从局部到整体的思维方式。分治的本质在于将复杂的问题拆解为更小的子问题，并逐步推进至全局最优。快排通过递归的力量，在无序中找到秩序，将数组分块，再在细小的区间中一一排列。这种策略不仅适用于排序，也广泛应用于高效查找。在这里，我们将围绕快速排序，深入探讨其核心分治思想在算法中的应用，从理论到实践，一步步领略其简洁之美。

第一章：快速排序的应用与延展

1.1 颜色分类（medium）

题目链接：75. 颜色分类

题目描述：

给定一个包含红色、白色和蓝色的数组 nums，共 n 个元素，要求对它们进行原地排序，使得相同颜色的元素相邻，并按红色、白色、蓝色的顺序排列。这里使用整数 0、1 和 2 分别表示红色、白色和蓝色，且不能使用库的排序函数。

示例 1：

• 输入：nums = [2,0,2,1,1,0]
• 输出：[0,0,1,1,2,2]

解法（分治思想 - 三指针法实现三分）

算法思路：

颜色分类问题可以视为一种简化的排序问题。我们可以通过“分治”思想，将数组分为三块，分别存储 0、1 和 2，实现“快速”分类。这种方法可以类比于快速排序的分区思想，使用三个指针高效地将数组分成三部分。

1. 指针定义：
   • left：用于标记 0 序列的末尾位置，初始为 -1。
   • cur：当前扫描位置，初始为 0。
   • right：用于标记 2 序列的起始位置，初始为 n（数组长度）。
2. 区域划分：
   • [0, left]：全部为 0。
   • [left + 1, cur - 1]：全部为 1。
   • [cur, right - 1]：待定元素。
   • [right, n - 1]：全部为 2。
3. 扫描与分区：
   • 当 cur < right 时，根据 nums[cur] 的值执行不同操作：
     • 若 nums[cur] == 0：将 cur 位置的 0 与 left + 1 位置的元素交换，并将 left 和 cur 均右移一位。
     • 若 nums[cur] == 1：当前元素 1 已在正确位置，无需交换，直接将 cur 右移。
     • 若 nums[cur] == 2：将 cur 位置的 2 与 right - 1 位置的元素交换，将 right 左移一位，但保持 cur 不变（因为交换过来的元素需要重新判断）。
4. 循环终止：
   • 当 cur 遇到 right 时，整个数组已被正确分类。最终得到 [0, left] 为 0，[left + 1, right - 1] 为 1，[right, n - 1] 为 2。

C++ 代码实现

classSolution{public:voidsortColors(vector<int>& nums){int n = nums.size();int left =-1, right = n, cur =0;while(cur < right){if(nums[cur]==0){swap(nums[++left], nums[cur++]);// 将当前 0 移到 0 区间末尾}elseif(nums[cur]==1){ cur++;// 当前为 1，位置已正确，直接跳过}else{swap(nums[--right], nums[cur]);// 将当前 2 移到 2 区间起始位置}}}};

易错点提示

1. 区间含义理解：
   • left 表示 0 序列的末尾，cur 表示当前扫描位置，right 表示 2 序列的起始位置。在移动指针时，要确保每个区间内的元素始终符合定义。
2. 保持 cur 不变：
   • 当 nums[cur] == 2 时，交换后需要重新判断 cur 位置，因为此位置交换过来的元素还未被处理。
3. 确保原地修改：
   • 本题要求在原数组上进行分类，避免额外的空间消耗，因此所有操作都在 nums 数组内完成，符合分治的原地修改原则。

时间复杂度和空间复杂度

• 时间复杂度：O(n)，cur 指针遍历数组一次，每个元素仅被处理一次。
• 空间复杂度：O(1)，使用常数个指针进行排序，无额外空间开销。

1.2 快速排序（medium）

题目链接：912. 排序数组

题目描述：

给定一个整数数组 nums，请将该数组按升序排列。

示例 1：

• 输入：nums = [5,2,3,1]
• 输出：[1,2,3,5]

示例 2：

• 输入：nums = [5,1,1,2,0,0]
• 输出：[0,0,1,1,2,5]

解法（数组分三块 + 随机基准元素的快速排序）

算法思路：

快速排序的核心在于“分区”：将数据按基准元素划分为小于基准、等于基准和大于基准的三部分。通过分治的思想，递归对两侧的分区进行排序。

1. 随机选择基准元素：
   • 快速排序的效率受基准元素的选取影响。若基准选取不佳，递归的深度增加，影响排序性能。（具体证明详见《算法导论》）
   • 在 getRandom 函数中，使用随机数来生成基准下标，这样在数据量大或元素重复较多的情况下，能有效避免最坏情况。
2. 三分区思想：
   • 类似于荷兰国旗问题，将数组划分为小于基准、等于基准和大于基准的三部分。
   • 使用三个指针来划分区间：
     • left 指向小于基准的部分末尾。
     • right 指向大于基准的部分起始。
     • i 用于遍历数组，根据当前值的大小，决定其在三分区的位置。
3. 递归排序左右分区：
   • 对于小于基准和大于基准的部分，递归应用快速排序，最终实现数组的整体有序。

C++ 代码实现

classSolution{public: vector<int>sortArray(vector<int>& nums){srand(time(NULL));// 初始化随机数种子qsort(nums,0, nums.size()-1);return nums;}// 快速排序voidqsort(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++]);// 移动到小于基准的区域elseif(nums[i]== key) i++;// 等于基准，跳过elseswap(nums[--right], nums[i]);// 移动到大于基准的区域}// 递归处理左右区域qsort(nums, l, left);// 左分区qsort(nums, right, r);// 右分区}// 随机基准选择intgetRandom(vector<int>& nums,int left,int right){int r =rand();// 生成随机数return nums[r %(right - left +1)+ left];// 生成基准的随机下标}};

易错点提示

1. 递归终止条件：
   • 在快速排序中，l >= r 时停止递归，否则会陷入无限递归。确保左右分区都有终止条件，避免栈溢出。
2. 随机基准选取：
   • getRandom 中使用 rand() % (right - left + 1) + left 随机生成基准索引，确保基准在 [left, right] 区间内选择，以应对重复数据。
3. 三分区逻辑：
   • left 表示小于基准的区域末尾，right 表示大于基准的区域起点，i 为当前扫描位置。确保每轮 i 的位置经过判断后处理到对应的区间，避免重复处理或漏处理。

时间复杂度和空间复杂度

• 时间复杂度：平均 O(n log n)。使用随机基准元素有效避免最坏 O(n^2) 的情况，提升了排序效率。
• 空间复杂度：O(log n)，主要为递归栈的空间消耗，最坏情况为 O(n)。

1.3 快速选择算法（medium）

题目链接：215. 数组中的第K个最大元素

题目描述：

给定一个整数数组 nums 和一个整数 k，返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例1：

• 输入：[3,2,1,5,6,4], k = 2
• 输出：5

示例2：

• 输入：[3,2,3,1,2,4,5,5,6], k = 4
• 输出：4

提示：

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

解法（快速选择算法）

算法思路：

快速选择算法是快速排序的变种，可以在不完全排序的情况下找到第 k 大的元素，从而将时间复杂度控制在 O(n)。我们通过分区思想来缩小查找范围，避免对整个数组排序。

1. 分区思想：
   • 快速排序将数组分成三块：小于基准、等于基准和大于基准。快速选择算法基于同样的分区思想，通过选择一个基准元素，将数组划分为左、中、右三部分。
   • 在每次划分后，可以根据每个区域的元素个数，确定第 k 大的元素所在的区域，从而递归地只处理该部分，逐步缩小范围。
2. 基准元素的随机选择：
   • 为避免最坏情况，使用 getRandom 函数随机选取基准元素位置，生成随机下标，确保基准在 [left, right] 范围内。
3. 分区计数与递归：
   • 使用 left、right 和 i 指针对数组进行划分：
     • [l, left]：存放小于基准的元素。
     • [left + 1, right - 1]：存放等于基准的元素。
     • [right, r]：存放大于基准的元素。
   • 划分完成后，通过以下判断确定第 k 大元素所在区间：
     • 若 k 小于等于 c（即右侧元素数），则递归在右侧区间 [right, r] 中继续查找；
     • 若 k 位于中间区间，则直接返回基准元素；
     • 否则递归在左侧区间 [l, left] 中继续查找。

C++ 代码实现

classSolution{public:intfindKthLargest(vector<int>& nums,int k){srand(time(NULL));// 初始化随机数种子returnqsort(nums,0, nums.size()-1, k);}// 快速选择intqsort(vector<int>& nums,int l,int r,int k){if(l == r)return nums[l];// 递归终止条件// 1. 随机选择基准元素int key =getRandom(nums, l, r);// 2. 根据基准元素将数组分三块int left = l -1, right = r +1, i = l;while(i < right){if(nums[i]< key)swap(nums[++left], nums[i++]);// 移动到小于基准的区域elseif(nums[i]== key) i++;// 等于基准，跳过elseswap(nums[--right], nums[i]);// 移动到大于基准的区域}// 3. 分情况判断int c = r - right +1;// 大于基准元素的个数int b = right - left -1;// 等于基准元素的个数if(c >= k)returnqsort(nums, right, r, k);// 查找右侧区间elseif(b + c >= k)return key;// 查找中间区间elsereturnqsort(nums, l, left, k - b - c);// 查找左侧区间}// 随机基准选择intgetRandom(vector<int>& nums,int left,int right){return nums[rand()%(right - left +1)+ left];}};

易错点提示

1. 递归出口控制：
   • if (l == r) return nums[l]; 确保当数组已缩小到单元素时返回该元素，避免陷入无止境的递归。
2. 基准随机选取：
   • getRandom 中使用 rand() % (right - left + 1) + left 确保基准元素在 [left, right] 区间内随机选取，减少最坏时间复杂度的可能。
3. 划分后的区域判断：
   • c 表示大于基准的元素个数；b 表示等于基准的元素个数。通过 k 与这些区域大小的比较，递归进入相应的区间，避免不必要的处理。

时间复杂度和空间复杂度

• 时间复杂度：平均 O(n)。每次选择的基准元素有效缩小搜索范围，递归深度为 log n，总共需遍历 n 个元素。
• 空间复杂度：O(log n)，用于递归栈的深度开销。

1.4 最小的 k 个数（medium）

题目链接：剑指 Offer 40. 最小的k个数

注：题目叙述有所调整，但整体要求保持一致。

题目描述：

输入整数数组 arr，找出其中最小的 k 个数。例如，输入 [4,5,1,6,2,7,3,8]，则最小的 4 个数字是 [1,2,3,4]。

示例 1：

• 输入：arr = [3,2,1], k = 2
• 输出：[1,2] 或者 [2,1]

示例 2：

• 输入：arr = [0,1,2,1], k = 1
• 输出：[0]

限制：

• 0 <= k <= arr.length <= 10000
• 0 <= arr[i] <= 10000

解法（快速选择算法）

算法思路：

快速选择算法是快速排序的变体，可以在 O(n) 的时间复杂度下找到最小的 k 个数。通过分区，将数组划分为小于基准、等于基准和大于基准的三部分，逐步缩小查找范围，直到找到前 k 小的元素。

1. 分区策略：
   • 使用随机基准元素，将数组划分为小于基准、等于基准和大于基准的三部分。
   • 通过计算每个区间的元素个数，判断最小的 k 个数应在哪个区间中，递归地缩小查找范围。
2. 随机选择基准：
   • 为避免最坏情况，使用 getRandom 函数随机选取基准元素。通过生成随机下标，将其作为当前基准元素，确保划分的高效性。
3. 递归查找：
   • 在 qsort 中，使用 left、right 和 i 指针对数组进行分区。
   • 划分完成后，确定第 k 小的元素范围：
     • 若左区间元素个数 a 大于 k，则递归左区间；
     • 若左区间加中间区间的元素总数 a + b 大于等于 k，直接返回前 k 个元素；
     • 若 a + b < k，则递归右区间，寻找剩余的 k - a - b 个元素。

C++ 代码实现

classSolution{public: vector<int>getLeastNumbers(vector<int>& nums,int k){srand(time(NULL));// 初始化随机数种子qsort(nums,0, nums.size()-1, k);return{nums.begin(), nums.begin()+ k};}// 快速选择voidqsort(vector<int>& nums,int l,int r,int k){if(l >= r)return;// 递归终止条件// 1. 随机选择一个基准元素，并进行分区int key =getRandom(nums, l, r);int left = l -1, right = r +1, i = l;while(i < right){if(nums[i]< key)swap(nums[++left], nums[i++]);// 小于基准的部分elseif(nums[i]== key) i++;// 等于基准，跳过elseswap(nums[--right], nums[i]);// 大于基准的部分}// 2. 分情况讨论int a = left - l +1;// 小于基准的元素个数int b = right - left -1;// 等于基准的元素个数if(a > k)qsort(nums, l, left, k);// 在左区间查找elseif(a + b >= k)return;// 在前 a + b 个元素中找到结果elseqsort(nums, right, r, k - a - b);// 在右区间查找剩余的元素}// 随机选择基准元素intgetRandom(vector<int>& nums,int l,int r){return nums[rand()%(r - l +1)+ l];}};

易错点提示

1. 递归出口：
   • 当 l >= r 时，递归停止，避免无止境递归。
2. 随机基准选取：
   • 在 getRandom 函数中使用 rand() % (r - l + 1) + l，确保基准元素随机选自 [l, r] 区间。
3. 分区结果判定：
   • a 为左区间元素个数，b 为等于基准的元素个数：
     • 若 a > k，表示最小的 k 个数在左区间。
     • 若 a + b >= k，表示最小的 k 个数在前两个区间，直接返回。
     • 若 a + b < k，则在右区间查找剩余的元素。

时间复杂度和空间复杂度

• 时间复杂度：平均 O(n)。通过随机基准，快速缩小查找范围。
• 空间复杂度：O(log n)，为递归栈的深度开销。

写在最后

分治法是一种化繁为简、由局部到整体的解决思路。快速排序的核心在于分而治之，将数组不断划分并排序，使递归在小区间中快速完成各自的排序任务；同时，快速选择算法则在相似的框架中寻找到目标元素，无需对整个数组排序，省去不必要的步骤，呈现出简洁而高效的解法。掌握分治不仅是算法本身的精通，更是编程思维的升华，在细节中不断优化、在局部中逐步收敛，以追求最终的全局最优。

以上就是关于【优选算法篇】化繁为简，见素抱朴：从乱象中重构秩序的艺术的内容啦，各位大佬有什么问题欢迎在评论区指正，或者私信我也是可以的啦，您的支持是我创作的最大动力！❤️