行业知识
Offer必备算法09
2026-10-21 19:33:52
来源：互联网转载
���录
（）分治快排算法原理
①力扣75. 颜色分类
（）解析代码
②力扣912. 排序数组
解析代码
③力扣215. 数组中的第K个最大元素
解析代码
④力扣LCR 159. 库存管理 III（剑指 Offer . 最小的k个数）
解析代码
本篇完。
分治快排算法原理
分治就是分而治之，快排在数据结构也学过了，现在来学一学三路划分快排（数组划分三块）：
前面我们已经实现了三个版本的快速排序的算法，分别是hoare法，挖坑法和前后指针法。但是前面的三个版本的快速排序在某些极端场景中效率都会变得很低，例如大部分都是同一个数的时候，前面的三种方法都不能很高效地完成排序，时间复杂度退化成了O(N^2)，所以有必要对之前的排序方法进行一些改进，使它能够适应包含任何数据的数组。于是就有大佬想出了一个更牛的方法，那就是三路划分快排。
三路划分快排的思路：三路划分，顾名思义就是把数组分成三个部分进行排序，在待排序数组中随机选定一个key，把数组分成小于key的，等于key的，还有大于key的。
具体操作是：
- 定义一个left下标为数组首元素下标的前一个位置，即left=begin-1；
- 再定义一个right下标为数组最后一个元素的下标的后一个位置，即right=end+1；
- 再定义一个下标cur=left，作为遍历数组的下标，一共就left，cur，right三个下标。
- 从a[cur]开始与key比较，如果a[cur]key,就用a[cur]和a[- -right]交换(记住这里是先减减，后交换)；如果a[cur]==key,那就只++cur即可，
- 这样循环往复，直到cur=right就结束，最后得到的a[begin,left]是比key小的数，a[left+1,right-1]是等于key的数，a[right,end]是大于key的数，划分成三路之后，中间这一路就不用再进行排序了，因为中间这一路都是等于key的，所以已经有序了，只需要对左路和右路再进行递归排序即可。
①力扣75. 颜色分类
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.length
- 1
