【每日算法】专题六_分治 - 快速排序

1. 算法思想

快速排序（Quick Sort）是一种基于分治思想的排序算法，由托尼・霍尔（Tony Hoare）在 1959 年提出，以下是其算法思想：

基本概念

• 分治思想：将一个规模较大的问题分解为若干个规模较小且相互独立的子问题，分别求解这些子问题，然后将子问题的解合并得到原问题的解。

算法步骤

1. 选择基准点：在待排序的数组中选择一个元素作为基准点（pivot）。基准点的选择方式有多种，常见的是选择数组的第一个元素、最后一个元素或者中间元素等。
2. 划分操作：遍历数组，将数组中所有小于基准点的元素移动到基准点的左边，所有大于基准点的元素移动到基准点的右边。经过这一步操作后，基准点处于它在最终有序数组中的正确位置，同时将数组分成了左右两个子数组。
3. 递归排序子数组：分别对基准点左边和右边的子数组重复上述的选择基准点和划分操作，直到子数组的长度为 1 或者 0，此时整个数组就完成了排序。

示例

假设有数组 arr = [5, 3, 8, 6, 7, 2]，使用快速排序进行排序：

• 选择基准点：选择第一个元素 5 作为基准点。
• 划分操作：遍历数组，将小于 5 的元素 3、2 放到左边，大于 5 的元素 8、6、7 放到右边，得到 [3, 2, 5, 8, 6, 7]，此时基准点 5 已处于正确位置。
• 递归排序子数组：
  • 对左边子数组 [3, 2] 重复上述步骤，选择 3 作为基准点，划分后得到 [2, 3] 。
  • 对右边子数组 [8, 6, 7] ，选择 8 作为基准点，划分后得到 [6, 7, 8] 。
• 最终整个数组变为 [2, 3, 5, 6, 7, 8] ，完成排序。

时间复杂度

• 平均时间复杂度：\(O(nlogn)\) ，其中 n 是待排序数组的元素个数。因为每次划分能将数组大致等分成两部分，递归树的深度为 logn，每层的操作次数为 \(O(n)\) 。
• 最坏时间复杂度：\(O(n^2)\) ，当基准点选择不当，比如每次都选择数组中的最大或最小元素时，划分后的子数组一个为空，另一个包含 \(n - 1\) 个元素，递归树深度变为 n，导致时间复杂度退化。
• 空间复杂度：快速排序的空间复杂度主要取决于递归调用的深度，平均情况下空间复杂度为 \(O(logn)\)，最坏情况下空间复杂度为 \(O(n)\) 。

分治顾名思义分而治之，即将一个大问题转化成若干个相同或相似的子问题

2. 例题

2.1 颜色分类

75. 颜色分类 - 力扣（LeetCode）

核心思路：

其核心思路是采用三指针法，通过一次遍历完成排序，具体分析如下：

1. 指针含义：

   • left：标记已处理区域中最后一个 0 的位置（初始值 - 1，表示尚未找到 0）
   • right：标记已处理区域中第一个 2 的位置（初始值 n，表示尚未找到 2）
   • i：当前遍历的元素位置

2. 算法逻辑：

   • 当遇到 0 时：将left右移一位，交换left与i位置的元素，然后i右移（因为交换后当前位置一定是 1）
   • 当遇到 1 时：直接将i右移（1 本身就应在中间）
   • 当遇到 2 时：将right左移一位，交换right与i位置的元素，i不移动（因为交换过来的元素可能是 0 或 1，需要重新判断）

3. 终止条件：当i到达right位置时，说明所有元素已处理完毕

该算法的时间复杂度为 O (n)，空间复杂度为 O (1)，是解决此问题的最优方案，体现了原地排序的高效性。

    void sortColors(vector<int>& nums) {int n = nums.size();int left = -1, right = n, i = 0;while(i < right){if(nums[i] == 0) swap(nums[++left], nums[i++]);else if(nums[i] == 1) ++i;else swap(nums[--right], nums[i]);}}

2.2 排序数组

912. 排序数组 - 力扣（LeetCode）

核心思路： 

其核心思路是结合分治思想与三指针法，通过随机选择基准值来优化排序效率，具体分析如下：

1. 整体结构：

   • sortArray 为入口函数，初始化随机数种子后调用快排核心函数 qsort
   • qsort 是快排的核心实现，采用递归方式处理子数组
   • getRandom 用于随机选择基准值，避免在有序数组下的性能退化

2. 核心算法逻辑：

   • 随机选择基准值：通过 getRandom 从当前子数组中随机选取一个元素作为基准值（key），降低最坏情况出现的概率
   • 三指针划分：
     • left 标记小于基准值区域的边界
     • right 标记大于基准值区域的边界
     • i 作为遍历指针，将元素分类到三个区域：
       • 小于基准值：交换到左侧区域，同时移动 left 和 i
       • 等于基准值：直接移动 i（保持在中间区域）
       • 大于基准值：交换到右侧区域，仅移动 right
   • 递归处理：划分完成后，对左侧（小于基准值）和右侧（大于基准值）的子数组分别递归排序

3. 时间与空间复杂度：

   • 平均时间复杂度：O (nlogn)，得益于随机化选择基准值
   • 最坏时间复杂度：O (n²)，但实际发生概率极低
   • 空间复杂度：O (logn)，主要来自递归调用栈

这种实现相比传统快排更稳定，通过将等于基准值的元素单独处理，减少了递归次数，特别适合存在大量重复元素的数组排序场景。

    vector<int> sortArray(vector<int>& nums) {srand(time(NULL));int left = 0, right = nums.size() - 1;qsort(nums, left, right);return nums;}// 快排void qsort(vector<int>& nums, int l, int r){if(l >= r) return;int key = getRandom(nums, l, r);int left = l - 1, right = r + 1;int i = l;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){return nums[(rand() % (right - left + 1)) + left];}

2.3 数组中的第K个最大元素

215. 数组中的第K个最大元素 - 力扣（LeetCode）

核心思路： 

核心思路是基于快速排序的分治思想进行优化，避免对整个数组完全排序，具体分析如下：

1. 整体思路：

   • 利用快速排序的划分特性，每次划分后能确定基准值在数组中的相对位置
   • 只递归处理包含目标元素的子数组，大幅减少不必要的计算
   • 通过随机选择基准值优化性能，避免最坏情况

2. 核心算法逻辑：

   • 随机选择基准值：通过getRandom从当前子数组中随机选取基准值，保证算法平均效率
   • 三指针划分：
     • 将数组划分为三部分：小于基准值、等于基准值、大于基准值
     • left标记小于区域的边界，right标记大于区域的边界
   • 判断与递归：
     • 计算右侧（大于基准值）区域长度c和中间（等于基准值）区域长度b
     • 如果k ≤ c：第 k 大元素在右侧区域，递归处理右侧
     • 如果k ≤ b + c：第 k 大元素在中间区域，直接返回基准值
     • 否则：第 k 大元素在左侧区域，调整 k 值后递归处理左侧

3. 时间与空间复杂度：

   • 平均时间复杂度：O (n)，每次次划分能排除部分元素，无需完整排序
   • 最坏时间复杂度：O (n²)，但随机化选择基准值使其概率极低
   • 空间复杂度：O (logn)，主要来自递归调用栈

这种实现相比先完全排序再取第 k 个元素的方法更高效，尤其适合处理大规模数据，体现了分治思想在优化算法中的重要作用。

    int findKthLargest(vector<int>& nums, int k) {srand(time(NULL));int left = 0, right = nums.size() - 1;return qsort(nums, left, right, 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 left = l - 1, right = r + 1;int i = l;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;// 中间段的长度int b = right - left - 1;// 第K个最大元素在右侧段if(k <= c) return qsort(nums, right, r, k);// 在中间段, 当在中间段的时候，由于中间段的数全都相等且等于key，所以直接返回key就行了else if(k <= b + c) return key;// 在左侧段else return qsort(nums, l, left, k - b - c); }int getRandom(vector<int>& nums, int left, int right){return nums[(rand() % (right - left + 1)) + left];}

2.4 库存管理

LCR 159. 库存管理 III - 力扣（LeetCode）

 核心思路：

核心思路是基于快速排序的分治思想进行优化，避免对整个数组完全排序，只关注与目标相关的子数组，具体如下：

1. 核心目标：从数组中高效筛选出最小的cnt个元素，无需对整个数组排序

2. 算法逻辑：

   • 随机选择基准值：通过getRandom在当前处理区间随机选择基准值，避免极端情况影响效率
   • 三指针划分：
     • 将数组划分为三部分：小于基准值（左侧）、等于基准值（中间）、大于基准值（右侧）
     • left标记小于区域的右边界，right标记大于区域的左边界
   • 针对性递归：
     • 计算左侧（小于基准值）区域长度a和中间（等于基准值）区域长度b
     • 若cnt < a：最小的cnt个元素全在左侧区域，递归处理左侧
     • 若cnt <= a + b：左侧和中间区域的元素已足够cnt个，直接返回（无需继续排序）
     • 否则：需要从右侧区域补充cnt - a - b个元素，递归处理右侧区域

3. 最终结果：经过处理后，数组前cnt个元素就是所需的最小cnt个元素，将其取出返回

这种实现的时间复杂度平均为 O (n)，空间复杂度为 O (logn)（递归栈），相比完整排序后取前cnt个元素的方法更高效，尤其适合大规模数据场景，体现了分治思想在筛选问题中的优化作用。

    vector<int> inventoryManagement(vector<int>& stock, int cnt) {srand(time(NULL));int left = 0, right = stock.size() - 1;qsort(stock, left, right, cnt);vector<int> ret;for(int i = 0; i < cnt; ++i)ret.push_back(stock[i]);return ret;}void qsort(vector<int>& stock, int l, int r, int cnt){if(l >= r) return;int key = getRandom(stock, l, r);int i = l;int left = l - 1, right = r + 1;while(i < right){if(stock[i] < key) swap(stock[++left], stock[i++]);else if(stock[i] == key) ++i;else swap(stock[--right], stock[i]);}int a = left - l + 1;int b = right - left - 1;if(cnt < a) qsort(stock, l, left, cnt);else if(cnt <= a + b) return;else qsort(stock, right, r, cnt - a - b);}int getRandom(vector<int>& stock, int left, int right){return stock[(rand() % (right - left + 1)) + left];}