一文详解“分治—快排“在算法中的应用
找往期文章包括但不限于本期文章中不懂的知识点：
个人主页：我要学编程(ಥ_ಥ)-ZEEKLOG博客
所属专栏： 优选算法专题
分治算法是利用分而治之的思想来实现的。典型代表，递归，将一个大问题转换为多个与其类似的小问题，降低规模。以下关于有关快排的优化，个人可能表述的不是很清楚，想要弄清楚原理的小伙伴，可以去算法导论中关于快排的优化章节去好好看看，下面是算法导论中文版：
通过百度网盘分享的文件：算法导论中文版.rar
链接：https://pan.baidu.com/s/1j-14MWs_MeJyVxwn-O3QVA?pwd=2580
提取码：2580
目录
75. 颜色分类
题目：
给定一个包含红色、白色和蓝色、共n个元素的数组nums，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数0、1和2分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]
示例 2：输入：nums = [2,0,1] 输出：[0,1,2]
提示：n == nums.length1 <= n <= 300nums[i]为0、1或2
思路：有一种最简单且不讲武德的方法，题目已经告诉我们怎么写了，就是套用标准库中给的sort方法。还有一些的方法，使用排序的思路解决。但是这些方法都是比较常规的，我们可以不使用常规的排序算法来解决，而是使用我们在最开始学习双指针算法时，遇到的 "移动零" 问题的解决思路，这里题目就是让我们把 2 移动到后面，把 0 移动到前面，把 1移动到中间。那就可以用三个指针来解决。移动0
代码实现：
class Solution { public void sortColors(int[] nums) { int len = nums.length; int left = -1; // 0区域 int right = len; // 2区域 // 这里的循环截止条件是 i 与 right 相遇就停止 for (int i = 0; i != right;) { int j = nums[i]; // 判断当前位置是啥情况 if (j == 0) { // 与left交换 swap(nums, i++, ++left); } else if (j == 2) { // 与right交换 swap(nums, i, --right); // i不能++，还未判断呢 } else { i++; } } } private void swap(int[] nums, int left, int right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; } }912. 排序数组
题目：
给你一个整数数组nums，请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为O(nlog(n))，并且空间复杂度尽可能小。
示例 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 <= nums.length <= 5 * 104-5 * 104 <= nums[i] <= 5 * 104
思路： 同样如果是在笔试阶段遇到这样的题型，直接使用内置的函数即可。这里题目的要求是 O(N * log N)，其实就是想让我们使用快排去解决的。如果使用常规的快排肯定是会超时的，我们得想办法去优化。例如，前面在学习快排时候的采取的"三数取中法"，找到一个合适的中间值，是单分支的树重新变为二叉树。 快排(三数取中法优化)
代码实现：
class Solution { public int[] sortArray(int[] nums) { quick_sort(nums, 0, nums.length - 1); return nums; } private void quick_sort(int[] nums, int start, int end) { // 递归的出口 if (start >= end) { return; } // 利用三数取中法，拿到中间值 int index = medianOfThree(nums, start, end); // 交换中间值与原基准，变为二叉树的形式 swap(nums, index, start); // 新的基准值 int key = nums[start]; int left = start, right = end; while (left != right) { while (left < right && nums[right] >= key) { right--; } while (left < right && nums[left] <= key) { left++; } swap(nums, left, right); } swap(nums, start, right); // 继续处理 quick_sort(nums, start, right - 1); quick_sort(nums, right + 1, end); } // 三数取中法的实现 private int medianOfThree(int[] nums, int low, int high) { int mid = (low + high) / 2; int a = nums[low], b = nums[mid], c = nums[high]; if (a > b) { if (a < c) { return low; } else if (b > c) { return mid; } else { return high; } } else { if (a > c) { return low; } else if (b < c) { return mid; } else { return high; } } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } 除了这种方法之外，还有另外一种方法。上一题学习的颜色分类，我们采取的是对数组的分块操作，将 < key 的全部放到 key 的左边，大于 key 的全部放到 key的右边，这个本质上与快排是类似的，但是快排一次只能确定一个元素的最终位置(正常情况)，但这个数组分块的操作，可以直接将值为 key 的元素确定下来，一次可以确定多个，效率更高。前面颜色分类已经详细的画图了，所以这里就直接给出代码了。但还要注意一点，数组分三块这个操作只是针对快排的主逻辑进行的操作，但是我们还是需要去手动指定 key。同样也需要使用三数取中法，找到合适的基准值。
class Solution { public int[] sortArray(int[] nums) { quick_sort(nums, 0, nums.length - 1); return nums; } private void quick_sort(int[] nums, int start, int end) { // 递归的出口 if (start >= end) { return; } // 利用三数取中法，拿到中间值 int index = medianOfThree(nums, start, end); // 交换中间值与原基准值，变为二叉树的形式 swap(nums, index, start); // 新的基准值 int key = nums[start]; int left = start-1, right = end+1; for (int i = start; i != right;) { int j = nums[i]; if (j < key) { swap(nums, ++left, i++); } else if (j > key) { swap(nums, i, --right); } else { i++; } } // 递归 左子树、右子树 // 注意起始位置与结束位置 quick_sort(nums, start, left); quick_sort(nums, right, end); } private int medianOfThree(int[] nums, int low, int high) { int mid = (low + high) / 2; int a = nums[low], b = nums[mid], c = nums[high]; if (a > b) { if (a < c) { return low; } else if (b > c) { return mid; } else { return high; } } else { if (a > c) { return low; } else if (b < c) { return mid; } else { return high; } } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }在算法导论中，针对快排取基准值，有一个比三数取中法效率更好的方法：随机取值。即在数组中随机取一个值，作为基准值，然后进行 数组分三块 的操作。
class Solution { public int[] sortArray(int[] nums) { quick_sort(nums, 0, nums.length - 1); return nums; } private void quick_sort(int[] nums, int start, int end) { // 递归的出口 if (start >= end) { return; } // 生成随机数，作为基准值 int key = nums[new Random().nextInt(end-start+1)+start]; int left = start-1, right = end+1; for (int i = start; i != right;) { int j = nums[i]; if (j < key) { swap(nums, ++left, i++); } else if (j > key) { swap(nums, i, --right); } else { i++; } } // 递归 左子树、右子树 // 注意起始位置与结束位置 quick_sort(nums, start, left); quick_sort(nums, right, end); } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }取随机数的方式，因为简单只有一行代码，因此最终的运行结果，肯定也是比 三数取中法 的时间要少的。
215.数组中的第K个最大元素
题目：
给定整数数组nums和整数k，请返回数组中第k个最大的元素。
请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。
你必须设计并实现时间复杂度为O(n)的算法解决此问题。
示例 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 <= 105-104 <= nums[i] <= 104
思路：笔试遇到肯定是使用不讲武德的方法。这题本质上是一个top-k问题，也可以采取堆的方式来写，使用堆的话，就比较简单了，用两种方式，第一种是建立大根堆，直接将全部的元素插入堆中，然后再循环k-1次将堆顶的元素删除，最终剩下的堆顶元素就是我们需要的结果；第二种是建立一个大小为k的小根堆，先将数组前 k 个元素插入堆中，最终形成的堆一定是堆顶元素是这k个元素中最小的，接着再去遍历数组剩下的元素，如果小于堆顶元素，直接跳过，如果大于堆顶元素（堆顶元素一定不是第k个最大的），那么就将堆顶元素删除，将该元素插入堆顶，遍历完成后，最终堆顶的元素，一定是第 k个最大的。
代码实现：
使用大根堆的方式：
class Solution { public int findKthLargest(int[] nums, int k) { // 使用 堆排序 // 默认是小根堆，但题目是要求第k个最大的元素 // lambda表达式也可以使用更加简洁的写法：(a, b) -> b - a PriorityQueue<Integer> queue = new PriorityQueue<>((a, b)->b.compareTo(a)); for (int x : nums) { queue.offer(x); } // 再从队列中出k个元素即可 int ret = 0; for (int i = 0; i < k; i++) { ret = queue.poll(); } return ret; } }使用小根堆的方式：
class Solution { public int findKthLargest(int[] nums, int k) { // 创建一个大小为 k 的小根堆 PriorityQueue<Integer> minHeap = new PriorityQueue<>(k); // 遍历数组中的元素 for (int num : nums) { if (minHeap.size() < k) { // 如果堆的大小小于 k，直接加入 minHeap.offer(num); } else if (num > minHeap.peek()) { // 如果堆的大小等于 k，且当前元素大于堆顶元素，替换堆顶 minHeap.poll(); minHeap.offer(num); } } // 堆顶元素即为第 k 大的元素 return minHeap.peek(); } }另外一种解法，就是使用 优化的快排来实现。
代码实现：
class Solution { public int findKthLargest(int[] nums, int k) { // 使用快速选择算法 // 首先得使用数组分三块的操作，将数组划分，然后再去判断 return quick_sort(nums, 0, nums.length-1, k); } private int quick_sort(int[] nums, int start, int end, int k) { // 递归结束的条件之一 if (start >= end) { return nums[start]; } // 随机取一个数作为基准值 int key = nums[new Random().nextInt(end-start+1)+start]; // 注意各个变量的初始值 int left = start-1, right = end+1; for (int i = start; i != right;) { int j = nums[i]; if (j < key) { swap(nums, ++left, i++); } else if (j > key) { swap(nums, --right, i); } else { i++; } } // 经过上面的处理，数组已经分为了三块，接下来得根据k的值来决定怎么走了 if (end - right + 1 >= k) { // c区域 return quick_sort(nums, right, end, k); } else if (end - left >= k) { // b区域 return key; } else { // a区域 // 去a区域寻找时，k不再是原来的k了，得减去前面的b+c return quick_sort(nums, start, left, k-(end-left)); } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }LCR 159.库存管理 III
题目：
仓库管理员以数组stock形式记录商品库存表，其中stock[i]表示对应商品库存余量。请返回库存余量最少的cnt个商品余量，返回 顺序不限。
示例 1：输入：stock = [2,5,7,4], cnt = 1 输出：[2]
示例 2：输入：stock = [0,2,3,6], cnt = 2 输出：[0,2] 或 [2,0]
提示：0 <= cnt <= stock.length <= 10000
0 <= stock[i] <= 10000
思路： 这题本质上也还是一个 top-k 问题，只不过不是让我们找到 第k大或者第k小了，而是让我们找到前k个最小的元素。笔试遇到，首先，还是优先考虑：内置函数排序+copyOfRange，直接解决，其次就是使用 堆，大小根堆都是可以的。
不知道大家有没有发现一个规律：需要第 k个最小或者前 k个最小时，暴力小根堆+遍历就可以解决，但是还有一种更加便捷的方式，使用创建一个大小为k的大根堆，然后再去遍历剩下的元素，如果小于堆顶元素，就将堆顶元素删除，然后将当前元素入堆。
这里其实就是看我们的处理方式是咋样的，如果是暴力的话，就是建一个与题目要求一样的堆；如果是优化一点的话，就是建一个与题目要求相反的堆。
上面方法所对应的代码在上一题中已经写过，这里就不再赘述了，直接使用快速选择算法。
由于题目是让我们返回一个数组，如果还是使用前面的方法去返回一个数组的话，肯定不现实。
代码实现：
class Solution { public int[] inventoryManagement(int[] stock, int cnt) { // 快速选择算法：将前 k 个最小的，随机放到数组前面 quick_sort(stock, 0, stock.length-1, cnt); // 返回原数组的cnt个即可 return Arrays.copyOfRange(stock, 0, cnt); } private void quick_sort(int[] nums, int start, int end, int k) { // 递归的结束条件之一 if (start >= end) { return; } // 随机确定基准值 int key = nums[new Random().nextInt(end-start+1)+start]; // 注意这里的变量的初始值 int left = start-1, right = end+1; for (int i = start; i != right;) { if (nums[i] < key) { swap(nums, ++left, i++); } else if (nums[i] > key) { swap(nums, --right, i); } else { i++; } } // 确定 k 的范围 // a:[start, left] b:[left+1, right-1] c:[right, end] int a = left-start+1, b = right-1-left; if (k < a) { // 在a区域内小范围的排序 quick_sort(nums, start, left, k); } else if (k <= a+b) { return; } else { // 对c区域进行小范围的排序 quick_sort(nums, right, end, k-a-b); } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }这里的quick_sort方法，之所以比快排要高效，正是因为其不是将数组变为完全有序，而是根据 k 的大小来是数组的前 k 个位置的值变为相对有序，相对于后面的元素来说，前面的元素都是小于后面的，且都是有序的，只不过被打乱了顺序而已，而这个顺序刚好题目不要求，这就是本题的精髓所在。
好啦！本期 一文详解“分治—快排“在算法中的应用 的学习之旅 就到此结束啦！我们下一期再一起学习吧！
