目录一、快速排序的基本想法二、三路划分中 4 个区域的含义三、为什么三个分支中指针移动方式不同情况一nums[i] key情况二nums[i] key情况三nums[i] key四、Java 中的交换方法五、题目一颜色分类六、题目二排序数组——三路快速排序七、题目三数组中的第 K 个最大元素八、题目四最小的 k 个数九、4 道题共同形成的快速排序规律规律二从右边交换元素时当前指针不能移动规律三完整排序要递归两边规律四只找答案时只递归一边规律五快速选择的关键是重新计算 k十、常用 Java 写法获取数组长度生成随机下标交换数组中的两个元素前置自增与后置自增十一、这一阶段的总结快速排序最容易让初学者困惑的地方是代码中同时出现多个指针而且有些指针移动、有些指针不移动。真正理解它的关键不是先背完整代码而是先弄清楚每个区间分别保存什么。本文涉及的题目链接75颜色分类912排序数组215数组中的第 K 个最大元素剑指 Offer 40最小的 k 个数一、快速排序的基本想法快速排序的基本过程是选出一个基准元素代码中叫key把数组中比key小、等于key、比key大的元素分开如果要完整排序就继续处理还没有排好序的区域如果只需要找某一个位置的答案就只处理可能包含答案的区域。这里使用的是三路划分小于 key | 等于 key | 大于 key如果数组中有很多重复数字等于key的中间部分已经不需要再次排序因此三路划分比只分成左右两部分更适合重复元素较多的情况。二、三路划分中 4 个区域的含义假设当前处理的区间是[l, r]准备使用key进行划分。代码定义int left l - 1; int right r 1; int i l;在循环过程中始终保持下面的关系[l, left] 小于 key [left 1, i - 1] 等于 key [i, right - 1] 还没有判断 [right, r] 大于 key其中left表示“小于key”区域的最后位置i表示当前正在判断的位置right表示“大于key”区域的起始位置[i, right - 1]是还没有判断的部分。循环条件是while(i right)当i right时未处理区域为空整个区间划分完成。三、为什么三个分支中指针移动方式不同情况一nums[i] key当前元素应该放到左边。把它与left 1位置交换并让left和i都向右移动swap(nums, left, i);交换之后当前位置已经确认处理完毕所以i可以加一。情况二nums[i] key当前元素已经属于中间区域不需要交换只让i向右移动i;情况三nums[i] key当前元素应该放到右边。把它与right - 1位置交换并让right向左移动swap(nums, --right, i);这里i不能移动因为从右边交换过来的新元素原来还没有判断必须在下一轮继续检查。因此要牢牢记住小于 keyleft 和 i 都移动 等于 key只有 i 移动 大于 key只有 right 移动i 不动四、Java 中的交换方法Java 的基本类型参数传递的是值不能通过下面这种方法交换数组中的两个位置void swap(int a, int b) { int t a; a b; b t; }因为这个方法只能交换局部变量的副本。对于数组需要传入数组和两个下标public void swap(int[] nums, int i, int j) { int t nums[i]; nums[i] nums[j]; nums[j] t; }这个方法在下面几道题中都会使用。五、题目一颜色分类1. 题目描述给定一个只包含0、1、2的数组要求原地排序使相同的数字相邻并按0、1、2的顺序排列。例如输入[2, 0, 2, 1, 1, 0] 输出[0, 0, 1, 1, 2, 2]不能使用库提供的排序方法。题目链接75颜色分类2. 算法思路这道题可以直接看成三路划分0就是“小于基准的元素”放在左边1留在中间2就是“大于基准的元素”放在右边。不需要真正选择一个key直接根据当前数字是0、1还是2进行处理。3. Java 代码class Solution { public void swap(int[] nums, int i, int j) { int t nums[i]; nums[i] nums[j]; nums[j] t; } public void sortColors(int[] nums) { int left -1; int right nums.length; int i 0; while(i right) { if(nums[i] 0) { swap(nums, left, i); } else if(nums[i] 1) { i; } else { swap(nums, --right, i); } } } }4. 为什么left从-1开始right从nums.length开始一开始数组中还没有确认任何0或20 区间为空[0, -1] 2 区间为空[nums.length, nums.length - 1]所以left -1; right nums.length;这是一种用“区间为空”的方式初始化指针的写法。5. 复杂度每个元素都被处理时间复杂度是O(n)只在原数组中交换空间复杂度是O(1)。六、题目二排序数组——三路快速排序1. 题目描述给定一个整数数组要求将数组按升序排列。例如输入[5, 2, 3, 1] 输出[1, 2, 3, 5]题目链接912排序数组2. 算法思路对区间[l, r]如果区间只有一个元素或为空就不需要处理随机选择一个下标得到基准元素key使用三路划分把区间分成小于、等于、大于key的三部分对左边和右边继续递归排序中间等于key的部分不用处理。随机选择基准是为了尽量避免每次都选到很差的基准从而降低出现极端情况的概率。3. Java 代码import java.util.Random; class Solution { public int[] sortArray(int[] nums) { qsort(nums, 0, nums.length - 1); return nums; } public void qsort(int[] nums, int l, int r) { if(l r) return; // 在 [l, r] 中随机选择一个元素作为 key int key nums[new Random().nextInt(r - l 1) l]; int left l - 1; int right r 1; int i l; while(i right) { if(nums[i] key) { swap(nums, left, i); } else if(nums[i] key) { i; } else { swap(nums, --right, i); } } // [l, left] 小于 key[right, r] 大于 key qsort(nums, l, left); qsort(nums, right, r); } public void swap(int[] nums, int i, int j) { int t nums[i]; nums[i] nums[j]; nums[j] t; } }4.new Random().nextInt()是什么Random是 Java 中用于生成随机数的类。new Random().nextInt(x)会生成0到x - 1之间的随机整数。因此new Random().nextInt(r - l 1) l得到的是[l, r]范围中的随机下标。5. 递归出口为什么是l r当l r时区间为空当l r时区间只有一个元素。这两种情况都已经天然有序不需要继续递归。6. 复杂度平均时间复杂度是O(n log n)。如果基准选择非常不理想最坏可能达到O(n^2)随机选择基准可以降低出现这种情况的概率。递归调用会占用栈空间平均空间复杂度通常是O(log n)。七、题目三数组中的第 K 个最大元素1. 题目描述给定一个整数数组和整数k返回数组排序后第k个最大的元素。这里的“第 k 个”允许重复数字参与排序不是第 k 个不同的数字。例如输入[3, 2, 1, 5, 6, 4]k 2 输出5题目链接215数组中的第 K 个最大元素2. 为什么不需要完整排序如果把整个数组排好序再取第k个最大元素时间复杂度是O(n log n)。三路划分以后数组已经分成小于 key | 等于 key | 大于 key对于第k大的元素只需要判断它位于哪一块如果“大于key”的数量已经不少于k答案在右边如果“大于或等于key”的数量已经不少于k答案就是key否则答案在左边但需要减去右边和中间已经占用的数量。这就是快速选择。它与快速排序使用同样的划分方式但不会递归处理两个区间而是只递归一个区间。3. Java 代码import java.util.Random; class Solution { public int findKthLargest(int[] nums, int k) { return qsort(nums, 0, nums.length - 1, k); } public int qsort(int[] nums, int l, int r, int k) { if(l r) { return nums[l]; } int key nums[new Random().nextInt(r - l 1) l]; int left l - 1; int right r 1; int i l; while(i right) { if(nums[i] key) { swap(nums, left, i); } else if(nums[i] key) { i; } else { swap(nums, --right, i); } } // c 是大于 key 的元素个数b 是等于 key 的元素个数 int c r - right 1; int b right - left - 1; if(c k) { return qsort(nums, right, r, k); } else if(c b k) { return key; } else { return qsort(nums, l, left, k - b - c); } } public void swap(int[] nums, int i, int j) { int t nums[i]; nums[i] nums[j]; nums[j] t; } }4. 为什么进入左边时要修改k假设右边有c个比key大的数字中间有b个等于key的数字。如果答案在左边说明这c b个数字已经排在答案前面了。因此原本要找第k大进入左区间后只需要找k - b - c大的元素。5. 复杂度平均时间复杂度是O(n)因为每次只继续处理一个区间。递归栈平均需要O(log n)的空间。八、题目四最小的 k 个数1. 题目描述给定整数数组arr找出其中最小的k个数。返回顺序可以任意。例如输入[3, 2, 1]k 2 输出[1, 2] 或 [2, 1]题目链接剑指 Offer 40最小的 k 个数2. 算法思路仍然使用三路划分。划分以后小于 key | 等于 key | 大于 key设a小于key的元素数量b等于key的元素数量。分三种情况如果a k最小的k个数全部在左边继续处理左区间如果a b k左边和中间已经足够组成最小的k个数不需要继续处理否则还需要从右边找k - a - b个元素。3. Java 代码import java.util.Random; class Solution { public int[] getLeastNumbers(int[] nums, int k) { qsort(nums, 0, nums.length - 1, k); int[] ret new int[k]; for(int i 0; i k; i) { ret[i] nums[i]; } return ret; } public void qsort(int[] nums, int l, int r, int k) { if(l r) return; int key nums[new Random().nextInt(r - l 1) l]; int left l - 1; int right r 1; int i l; while(i right) { if(nums[i] key) { swap(nums, left, i); } else if(nums[i] key) { i; } else { swap(nums, --right, i); } } int a left - l 1; int b right - left - 1; if(a k) { qsort(nums, l, left, k); } else if(a b k) { return; } else { qsort(nums, right, r, k - a - b); } } public void swap(int[] nums, int i, int j) { int t nums[i]; nums[i] nums[j]; nums[j] t; } }4. 为什么可以直接取数组前k个数快速选择过程保证最小的k个数字被放到了数组的前k个位置。前k个数字内部不一定有序但题目允许任意顺序返回所以复制出来即可。5.k在两道题中含义不同第 215 题中的k表示“第 k 大”的名次第 40 题中的k表示“需要多少个最小数字”。两道题虽然都使用快速选择但判断方向不同第 k 大先数右边大于 key 的元素 最小的 k 个先数左边小于 key 的元素6. 复杂度平均时间复杂度是O(n)返回结果需要O(k)的空间递归栈平均需要O(log n)的空间。九、4 道题共同形成的快速排序规律规律一三路划分的核心不是代码而是区间含义[l, left] 小于 key [left 1, i - 1] 等于 key [i, right - 1] 未处理 [right, r] 大于 key只要这四个区间的含义没有混淆代码就不会完全靠死记。规律二从右边交换元素时当前指针不能移动swap(nums, --right, i);右边换来的元素没有判断所以i保持不变下一轮继续检查nums[i]。规律三完整排序要递归两边排序数组时qsort(nums, l, left); qsort(nums, right, r);左右两边都要继续处理。规律四只找答案时只递归一边找第k大或者最小的k个数时不需要把没有答案的那一边排好只递归可能包含答案的区间。规律五快速选择的关键是重新计算 k当已经排除了一部分元素后进入下一个区间时k不一定还是原来的值。进入左边或右边以前要减去已经确定在前面的元素数量。十、常用 Java 写法获取数组长度nums.length生成随机下标new Random().nextInt(r - l 1) l这句话表示在[l, r]中随机取一个下标。交换数组中的两个元素public void swap(int[] nums, int i, int j) { int t nums[i]; nums[i] nums[j]; nums[j] t; }前置自增与后置自增left先加一再使用新值。i先使用当前值再加一。因此swap(nums, left, i);可以理解为先扩大左边区域再完成交换最后让当前扫描位置向右移动。十一、这一阶段的总结快速排序和快速选择并不是两套完全不同的东西它们共享同一个核心围绕key做三路划分。需要把整个数组排好左右两边都递归这就是快速排序只需要找到某个排名或某个数量范围根据区间数量判断答案在哪只递归一边这就是快速选择数组中有很多重复元素把等于key的部分单独拿出来可以避免对它们重复处理。我现在理解这类题时会先画出四个区间再确定每种情况下哪个指针移动最后才写代码。尤其是“大于key”的分支交换以后i不移动这个细节决定了三路划分是否正确。