C++算法
分治专题：快速排序核心思想与典型应用
分治专题：快速排序核心思想与应用 前言 快速排序不仅是一种排序算法，更体现了'分而治之'的核心思维。其本质是将复杂问题拆解为规模更小的子问题，通过递归逐步求解。快速排序通过选取基准元素将数组分区，在无序中建立局部秩序，最终实现全局有序。该思想不仅适用于排序，也广泛应用于高效查找与选择问题。将围绕快速排序，深入探讨其分治思想在典型算法题中的应用。 颜色分类 **题目链接**：75. 颜色分类 *…
分治专题：快速排序核心思想与应用 前言 快速排序不仅是一种排序算法，更体现了'分而治之'的核心思维。其本质是将复杂问题拆解为规模更小的子问题，通过递归逐步求解。快速排序通过选取基准元素将数组分区，在无序中建立局部秩序，最终实现全局有序。该思想不仅适用于排序，也广泛应用于高效查找与选择问题。将围绕快速排序，深入探讨其分治思想在典型算法题中的应用。 颜色分类 **题目链接**：75. 颜色分类 *…
快速排序不仅是一种排序算法，更体现了'分而治之'的核心思维。其本质是将复杂问题拆解为规模更小的子问题，通过递归逐步求解。快速排序通过选取基准元素将数组分区，在无序中建立局部秩序，最终实现全局有序。该思想不仅适用于排序，也广泛应用于高效查找与选择问题。本文将围绕快速排序，深入探讨其分治思想在典型算法题中的应用。
题目链接：75. 颜色分类
题目描述：给定一个包含红色、白色和蓝色（分别用整数 0、1、2 表示）的数组 nums，要求原地排序，使相同颜色的元素相邻，并按红、白、蓝顺序排列。不能使用库的排序函数。
示例：
nums = [2,0,2,1,1,0][0,0,1,1,2,2]本题可视为快速排序分区思想的简化版（荷兰国旗问题）。通过三个指针将数组划分为三个区域：
left：指向 0 区域的末尾，初始为 -1。cur：当前遍历指针，初始为 0。right：指向 2 区域的起始位置，初始为 n（数组长度）。[0, left]：全为 0[left + 1, cur - 1]：全为 1[cur, right - 1]：待处理区域[right, n - 1]：全为 2cur < right 时循环：
nums[cur] == 0：与 left + 1 位置交换，left++，cur++。nums[cur] == 1：已在正确区域，cur++。nums[cur] == 2：与 right - 1 位置交换，right--。注意：交换后 cur 不移动，因为换过来的元素尚未检查。cur 与 right 相遇时，所有元素已分类完毕。class Solution {
public:
void sortColors(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++]);
} else if (nums[cur] == 1) {
cur++;
} else {
swap(nums[--right], nums[cur]);
}
}
}
};
cur 指针处理：当遇到 2 并与右侧交换时，cur 必须保持不变，因为从右侧换过来的元素可能是 0 或 2，需要重新判断。O(1) 空间要求，所有交换均在原数组上进行。O(n)。cur 指针最多遍历数组一次，每个元素最多被交换两次。O(1)。仅使用常数个额外指针。题目链接：912. 排序数组
题目描述：给定整数数组 nums，将其按升序排列。
示例：
nums = [5,2,3,1] -> 输出：[1,2,3,5]传统快速排序在数据有序或大量重复时可能退化至 O(n^2)。优化方案如下：
< key、== key、> key 三部分，减少重复元素的递归开销。< key 和 > key 的区间递归调用，等于基准的元素已就位。class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
srand(time(nullptr));
quickSort(nums, 0, nums.size() - 1);
return nums;
}
private:
void quickSort(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++]);
} else if (nums[i] == key) {
i++;
} else {
swap(nums[--right], nums[i]);
}
}
quickSort(nums, l, left);
quickSort(nums, right, r);
}
int getRandom(const vector<int>& nums, int left, int right) {
return nums[rand() % (right - left + 1) + left];
}
};
l >= r 时必须返回，防止栈溢出。rand() % (right - left + 1) + left 确保基准索引严格落在当前区间内。left 维护小于区末尾，right 维护大于区开头，i 负责扫描。注意 swap 后指针的移动逻辑。O(n log n)。随机基准有效规避了有序数据导致的退化，最坏情况仍为 O(n^2) 但概率极低。O(log n)，主要为递归调用栈开销。题目链接：215. 数组中的第K个最大元素
题目描述：返回数组排序后第 k 个最大的元素（非去重）。
示例：输入 [3,2,1,5,6,4], k = 2 -> 输出 5
快速选择算法基于快速排序的分区思想，但无需完全排序，只需定位目标元素所在区间即可，平均时间复杂度可降至 O(n)。
< key、== key、> key 三部分。c。k <= c，说明目标在右侧，递归右区间。k 落在中间区间（c < k <= c + b，b 为等于基准的个数），则基准即为目标，直接返回。k 为 k - c - b。class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
srand(time(nullptr));
return quickSelect(nums, 0, nums.size() - 1, k);
}
private:
int quickSelect(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, 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; // 等于基准的元素个数
if (k <= c) return quickSelect(nums, right, r, k);
else if (k <= c + b) return key;
(nums, l, left, k - c - b);
}
{
nums[() % (right - left + ) + left];
}
};
l == r 时直接返回该元素。k 的更新：进入左区间查找时，需减去已排除的右侧和中间区间的元素数量（k - c - b）。O(n)。每次分区期望排除一半元素，总比较次数为 n + n/2 + n/4 + ... ≈ 2n。O(log n)，递归栈深度。题目链接：剑指 Offer 40. 最小的k个数
题目描述：输入整数数组 arr，找出其中最小的 k 个数。
示例：输入 arr = [3,2,1], k = 2 -> 输出 [1,2]（顺序不限）
与第 K 大元素类似，本题求最小的 k 个数，只需调整区间判断逻辑：
a，中间区间个数为 b）：
a >= k：最小的 k 个数全在左区间，递归左区间。a + b >= k：左区间和中间区间已包含至少 k 个最小元素，直接返回。a + b < k：左、中区间元素不足，需进入右区间查找剩余的 k - a - b 个元素。class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
if (k == 0 || arr.empty()) return {};
srand(time(nullptr));
quickSelect(arr, 0, arr.size() - 1, k);
return {arr.begin(), arr.begin() + k};
}
private:
void quickSelect(vector<int>& arr, int l, int r, int k) {
if (l >= r) return;
int key = getRandom(arr, l, r);
int left = l - 1, right = r + 1, i = l;
while (i < right) {
if (arr[i] < key) swap(arr[++left], arr[i++]);
else if (arr[i] == key) i++;
else swap(arr[--right], arr[i]);
}
int a = left - l + 1; // 小于基准的元素个数
int b = right - left - 1; // 等于基准的元素个数
if (a >= k) (arr, l, left, k);
(a + b >= k) ;
(arr, right, r, k - a - b);
}
{
arr[() % (r - l + ) + l];
}
};
k == 0 或数组为空时需直接返回空结果。k 个元素即为所求，直接截取返回即可，无需额外排序。k 在递归右区间时的扣减逻辑。O(n)。O(log n)，递归栈开销。分治策略的核心在于'分而治之'与'递归收敛'。快速排序通过基准划分将无序数组逐步有序化；快速选择则在此基础上剪枝，仅递归目标所在区间，将时间复杂度优化至线性。掌握这些变体不仅能高效解决排序与选择问题，更能培养将复杂问题拆解为可管理子问题的算法思维。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online