算法 --快速排序

什么是快速排序快速排序是一种分治法Divide and Conquer的排序算法。它的核心思想非常简单选基准Pivot从数组中选择一个元素作为基准值。划分Partition将数组重新排列使得所有小于基准值的元素放在基准前面所有大于基准值的元素放在基准后面等于基准的放哪边都可以。这个过程结束后基准值就找到了它在最终排序数组中的正确位置。递归Recurse递归地对基准值左边和右边的子数组进行同样的操作。生活类比就像整理扑克牌你先随便抽一张牌基准然后把比它小的放左边比它大的放右边。接着对左边那堆牌和右边那堆牌分别重复这个动作直到所有牌都有序。基础版本的快速排序最经典的实现是Hoare 划分法双指针法。代码逻辑伪代码void quickSort(vectorint nums, int l, int r) { if (l r) return; // 递归终止条件 // 1. 选基准通常选最左边或最右边但这是有隐患的 int pivot nums[l]; int i l, j r; // 2. 划分 while (i j) { // 从右往左找第一个小于 pivot 的数 while (i j nums[j] pivot) j--; // 从左往右找第一个大于 pivot 的数 while (i j nums[i] pivot) i; // 交换这两个数 if (i j) swap(nums[i], nums[j]); } // 将基准值放到正确位置 swap(nums[l], nums[i]); // 3. 递归处理左右两边 quickSort(nums, l, i - 1); quickSort(nums, i 1, r); }快速排序的性能分析时间复杂度平均情况O(nlog⁡n)。每次划分都能将数组大致分为两半递归深度为 log⁡n每层处理 n 个元素。最坏情况O(n2)。当数组已经有序或逆序且每次选的都是最大/最小值作为基准时划分极度不平衡递归深度退化为 n。空间复杂度O(log⁡n) ~ O(n)。主要是递归调用栈的深度。平均为 O(log⁡n)最坏为 O(n)。稳定性不稳定。在交换过程中相同元素的相对顺序可能会被打乱。题目一颜色分类class Solution { public: void sortColors(vectorint 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]); } } };代码逻辑详解初始化指针left -1指向 0 区域的右边界初始时 0 区域为空。right n指向 2 区域的左边界初始时 2 区域为空。i 0当前遍历的指针。循环条件while(i right)当i遇到right时停止因为right及其后面的元素都已经确认是 2 了。分支判断核心逻辑情况一nums[i] 0说明当前元素属于红色区域。执行swap(nums[left], nums[i])。先将left向右移一位然后将当前元素i与left位置的元素交换。因为交换过来的元素一定是 1或者就是它自己所以i也向右移动。情况二nums[i] 1说明当前元素属于白色区域位置正确。执行i。直接跳过继续检查下一个元素。情况三nums[i] 2说明当前元素属于蓝色区域应该放到最右边。执行swap(nums[--right], nums[i])。注意这里i没有自增。先将right向左移一位然后交换。由于交换过来的元素原本在right位置的元素是未知的可能是 0、1 或 2所以需要在下一次循环中继续检查当前位置i的新值因此i不能加 1。题目二排序数组class Solution { public: vectorint sortArray(vectorint nums) { srand(time(NULL)); // 种下⼀个随机数种⼦ quickSort(nums, 0, nums.size() - 1); return nums; } int getRandom(vectorint nums, int left, int right) { int r rand(); return nums[r % (right - left 1) left]; } void quickSort(vectorint 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 key getRandom(nums, l, r);随机选取一个基准值。int i l, left l - 1, right r 1;定义三个指针。left指向小于区域的最右侧初始为l-1。right指向大于区域的最左侧初始为r1。i当前遍历的指针。while(i right)遍历数组。if(nums[i] key) swap(nums[left], nums[i]);当前元素小于基准将其交换到左侧区域left和i同时右移。else if(nums[i] key) i;当前元素等于基准跳过i右移。else swap(nums[--right], nums[i]);当前元素大于基准将其交换到右侧区域right左移。注意此时i不自增因为从右侧交换过来的元素还未被检查。递归处理qsort(nums, l, left);递归排序小于基准的区域。qsort(nums, right, r);递归排序大于基准的区域。中间等于基准的区域[left1, right-1]已经就位无需递归。优化策略随机化基准值int getRandom(vectorint nums, int left, int right) { int r rand(); return nums[r % (right - left 1) left]; }在sortArray函数开头调用srand(time(NULL))初始化随机数种子。在getRandom中通过取模运算r % (right - left 1) left生成一个在[left, right]范围内的随机索引并返回该索引对应的值作为基准值key。为什么需要随机化如果每次都固定选择最左边或最右边的元素作为基准当数组已经有序如[1,2,3,4,5]时快速排序会退化成冒泡排序时间复杂度变为 O(n2)。随机选取基准值可以有效避免最坏情况的发生使得期望时间复杂度稳定在 O(nlog⁡n)。题目三数组中第k个最大元素class Solution { public: int findKthLargest(vectorint nums, int k) { srand(time(NULL)); return qsort(nums, 0, nums.size() - 1, k); } int getRandom(vectorint nums, int left, int right) { return nums[rand() % (right - left 1) left]; } int qsort(vectorint 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, b right - left - 1; if (c k) return qsort(nums, right, r, k); else if (b c k) return key; else return qsort(nums, l, left, k - b - c); } };核心思想快速选择 (Quick Select)快速选择算法是快速排序的变种。它的核心思想是我们不需要对整个数组进行完全排序只需要找到第 k 大的元素即可。在快速排序中我们通过基准值pivot将数组分为三部分后会递归处理左右两边。但在快速选择中我们根据 k 的大小每次只需要递归处理其中一部分。这样平均时间复杂度就从O(nlog⁡n)降到了 O(n)。代码详细拆解函数签名int qsort(vectorint nums, int l, int r, int k)这里的k代表我们需要在当前[l, r]区间内寻找第 kk 大的元素。第一步递归终止条件if(l r) return nums[l];当区间内只剩下一个元素时这个元素必然就是我们要找的第 kk 大元素直接返回。第二步随机化基准值与三路划分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]); }这部分逻辑与上一题排序数组完全一致。经过这轮循环后数组在[l, r]范围内被划分成了三部分[l, left]小于key的元素左区间[left 1, right - 1]等于key的元素中区间[right, r]大于key的元素右区间第三步分情况讨论核心优化点int c r - right 1, b right - left - 1; if(c k) return qsort(nums, right, r, k); else if(b c k) return key; else return qsort(nums, l, left, k - b - c);这里定义了三个关键变量c大于key的元素个数即右区间的长度。b等于key的元素个数即中区间的长度。分支逻辑分析if(c k)如果右区间大于key的元素的数量c已经大于等于k说明第 kk 大的元素一定在右区间里。此时我们只递归右区间qsort(nums, right, r, k)。注意这里的k不变因为我们仍然是在找整个区间内第 kk 大的元素。else if(b c k)如果c k且b c k说明第 kk 大的元素既不在右区间也不在左区间而是正好落在中区间等于key的部分。因为中区间的所有元素都等于key所以第 kk 大的元素就是key。直接返回key。else如果b c k说明第 kk 大的元素在左区间。此时我们只递归左区间qsort(nums, l, left, k - b - c)。注意这里的k变成了k - b - c因为我们排除了右区间和中区间共b c个元素所以在左区间中我们需要找的是第k - b - c大的元素。题目四库存管理IIIclass Solution { public: vectorint inventoryManagement(vectorint stock, int cnt) { srand(time(NULL)); quickSort(stock, 0, stock.size() - 1, cnt); return {stock.begin(), stock.begin() cnt}; } void quickSort(vectorint stock, int l, int r, int cnt) { if (l r) return; int key getRandom(stock, l, r); int left l - 1, right r 1, i l; 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, b right - left - 1; if (a cnt) quickSort(stock, l, left, cnt); else if (a b cnt) return; else quickSort(stock, right, r, cnt - a - b); } int getRandom(vectorint stock, int l, int r) { return stock[rand() % (r - l 1) l]; } };核心思想Top K 问题的变种这道题的本质是Top K 问题找出最小的 K 个元素。最简单的方法是直接对整个数组排序然后取前cnt个时间复杂度为 O(nlog⁡n)。代码利用了快速选择算法在期望 O(n)的时间复杂度内将最小的cnt个元素移动到数组的最左侧而不需要保证它们内部是有序的题目也说了“返回顺序不限”。代码详细拆解第一部分主入口inventoryManagementvectorint inventoryManagement(vectorint stock, int cnt) { srand(time(NULL)); quickSort(stock, 0, stock.size() - 1, cnt); return {stock.begin(), stock.begin() cnt}; }srand(time(NULL))初始化随机数种子保证基准值选择的随机性。quickSort(...)调用核心逻辑。注意这里传入的cnt代表我们需要在数组中找到最小的cnt个元素。return {stock.begin(), stock.begin() cnt};由于quickSort执行完毕后数组的前cnt个位置已经存放了最小的cnt个元素虽然顺序是乱的直接截取并返回即可。第二部分核心逻辑quickSortvoid quickSort(vectorint stock, int l, int r, int cnt) { if (l r) return; // 递归终止条件 int key getRandom(stock, l, r); int left l - 1, right r 1, i l; 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, b right - left - 1; if (a cnt) quickSort(stock, l, left, cnt); else if (a b cnt) return; else quickSort(stock, right, r, cnt - a - b); }三路划分与之前的题目完全一致。经过while循环后数组在[l, r]范围内被分为三部分[l, left]小于key的元素左区间。[left 1, right - 1]等于key的元素中区间。[right, r]大于key的元素右区间。分情况讨论核心剪枝逻辑这里定义了a和ba左区间小于key的元素个数。b中区间等于key的元素个数。我们的目标是确保最小的cnt个元素都落在数组的前cnt个位置。if (a cnt)如果左区间的元素个数a已经大于cnt了说明最小的cnt个元素全部在左区间里。此时我们只需要递归处理左区间quickSort(stock, l, left, cnt)。中区间和右区间都不用管了。else if (a b cnt)如果a不够cnt但是a b左区间 中区间够cnt了。说明最小的cnt个元素正好由左区间的所有元素和部分中区间元素组成。由于中区间的元素都等于key所以此时数组的前cnt个位置已经全部是符合要求的最小元素了。直接return不需要再做任何递归。else如果a b cnt说明左区间和中区间的元素加起来都不够cnt个。说明最小的cnt个元素分布在左区间、中区间以及部分右区间中。此时我们需要递归处理右区间quickSort(stock, right, r, cnt - a - b)。注意cnt的变化因为我们已经在左区间和中区间找到了a b个最小元素所以还需要在右区间中找cnt - (a b)个最小元素。第三部分随机化工具getRandomint getRandom(vectorint stock, int l, int r) { return stock[rand() % (r - l 1) l]; }生成[l, r]范围内的随机索引返回该索引对应的值作为基准值。快速排序 核心总结1. 核心思想分治法选基准从数组中选一个元素作为基准。划分把小于基准的放左边大于基准的放右边等于基准的放中间。递归 (Recurse)对左右两边子数组重复上述过程。2. 性能指标时间复杂度平均 O(nlog⁡n)最坏 O(n2)可通过随机化避免。空间复杂度O(log⁡n) ~ O(n)取决于递归栈深度。稳定性不稳定交换操作会打乱相同元素的相对顺序。3. 三大核心优化现代工业级写法标配随机化基准值目的避免在数组已经有序时退化成 O(n2)。做法用rand()随机选一个元素与最左边交换再作为基准。三路划分目的解决数组中存在大量重复元素导致的性能退化问题。做法将数组分为 key、 key、 key三部分。等于key的中间部分不再参与递归直接留在原地。经典实现荷兰国旗问题使用left,right,i三个指针。小区间优化目的减少递归调用开销。做法当子数组长度小于某个阈值时改用插入排序。4. 快排的变种快速选择 —— 解决 Top K 问题的利器核心区别快排递归处理左右两边快速选择根据目标 kk只递归处理其中一边。时间复杂度期望 O(n)。应用场景找第 K 大/小的元素。找最小/最大的 K个元素。剪枝逻辑结合三路划分如果右边大于基准的数量c k只递归右边。如果b c k说明第 k 大就在中间等于基准的区域直接返回key。否则只递归左边且目标 k 变为k - b - c。5. C STL 的std::sort是什么不是纯快排而是内省排序 (Introsort)。结合了快排主体 堆排防止最坏情况 插入排序小区间优化。识别信号1. 题目要求“原地排序”且“不允许使用内置函数”触发词“你必须在不使用任何内置函数的情况下解决问题”、“原地对它们进行排序”、“空间复杂度尽可能小”。场景比如前面看的LeetCode 912. 排序数组或者75. 颜色分类。原因快排是原地排序空间复杂度 O(log⁡n)不需要像归并排序那样开辟 O(n)的额外数组空间非常适合内存受限的场景。2. 题目要求 O(n) 时间复杂度解决 Top K 问题触发词“第 K 个最大/最小的元素”、“找出最小的 K 个数”、“库存管理”。场景比如前面看的LeetCode 215. 数组中的第K个最大元素或者LCR 159. 库存管理 III。原因这是快速选择Quick Select的绝佳场景。它不需要对整个数组排序每次划分后只需要根据 K 的大小只递归处理其中一边从而将平均时间复杂度从 O(nlog⁡n) 降到了O(n)。这是解决 Top K 问题的最优解之一另一种是堆排序时间复杂度 O(nlog⁡k。3. 数据量巨大且包含大量重复元素触发词“数组中有大量重复元素”、“注意nums 的值不一定唯一”。场景比如75. 颜色分类只有 0, 1, 2 三种元素或者数组中存在大量相同的数值。原因此时必须使用三路划分的快排。传统的快排遇到大量重复元素会退化成 O(n2)而三路划分可以将等于基准值的元素直接固定在中间不参与后续递归完美解决重复元素问题。4. 题目要求“不稳定排序”且对缓存友好触发词通常不会直接说但如果你需要极高的实际运行速度。原因快排的局部性访问非常好连续内存对 CPU 缓存友好在实际工程中通常比归并排序和堆排序跑得快。C 的std::sort底层就是快排内省排序。