找往期文章包括但不限于本期文章中不懂的知识点：
个人主页：我要学编程(ಥ_ಥ)-CSDN博客
所属专栏： 优选算法专题
分治算法是利用分而治之的思想来实现的。典型代表，递归，将一个大问题转换为多个与其类似的小问题，降低规模。以下关于有关快排的优化，个人可能表述的不是很清楚，想要弄清楚原理的小伙伴，可以去算法导论中关于快排的优化章节去好好看看，下面是算法导论中文版：
通过百度网盘分享的文件：算法导论中文版.rar
链接：https://pan.baidu.com/s/1j-14MWs_MeJyVxwn-O3QVA?pwd=2580
提取码：2580
目录
75. 颜色分类
912. 排序数组
215.数组中的第K个最大元素
LCR 159.库存管理 III
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 个位置的值变为相对有序，相对于后面的元素来说，前面的元素都是小于后面的，且都是有序的，只不过被打乱了顺序而已，而这个顺序刚好题目不要求，这就是本题的精髓所在。
好啦！本期 一文详解“分治—快排“在算法中的应用 的学习之旅 就到此结束啦！我们下一期再一起学习吧！
