从简单的快速排序说起-Partition-ThreePartition-TopK
1. 简单快速排序
快速排序是一个简单,易于理解的排序算法,我们先来看看一个入门级别的快排:
function QuickSort(nums){
if(nums.length <= 1){
return nums
}
let pivot = nums[random(0, nums.length - 1)]
let left= []
let right = []
let mid= []
for (let i = 0;
i < nums.length;
i++) {
if(nums[i] < pivot){
left.push(nums[i])
}else if(nums[i] == pivot){
mid.push(nums[i])
}else{
right.push(nums[i])
}
}
return QuickSort(left).concat(mid, QuickSort(right))
}
这种写法的优点是逻辑非常清晰,很好理解;缺点是每次递归都产生了新的数组,最后再合并数组,空间复杂度略高
2.原地排序 Partition算法 【从简单的快速排序说起-Partition-ThreePartition-TopK】Partition算法是一种原地分割排序的的算法,选定一个基准值,将每一个小于基准值的交换到左边,将每一个大于基准值的交换到右边,最后基准值居中,是一种原地分割的算法,除了常数级的变量外,没有使用额外的空间
2.1 公共函数
我们先定义几个常用的公共函数
//数组交换
function swap(nums, i ,j){
tmp = nums[j]
nums[j] = nums[i]
nums[i] = tmp
}
//范围内随机数
function random(minNum,maxNum){
return parseInt(Math.random()*(maxNum-minNum+1)+minNum,10)
}
2.2 从左向右一次遍历-Partition算法
function Partition(nums, l = 0, r = nums.length - 1) {
//随机选取一个作为基值值
let random_i= random(l, r)
let pivot= nums[random_i]
swap(nums, l, random_i)
let pos= l
for (let i = l + 1;
i <= r;
i++) {
if(nums[i] <= pivot){
pos++
if(i != pos){
swap(nums, i, pos)
}
}
}
swap(nums, l, pos)
return pos
}
pos是分割线,pos(含本身)右边都是小于等于基准值的,右边都是大于基准值的
2.3 双指针-Partition算法
function Partition(nums, l = 0, r = nums.length - 1)
{
let pivot = nums[l]
while(l < r)
{
while(l < r && nums[r] >= pivot){
r--
}
nums[l] = nums[r]
while(l < r && nums[l] <= pivot){
l++
}
nums[r] = nums[l]
}
nums[begin] = pivot;
return begin;
}
双指针的算法比较不太好理解,精妙在没有使用交换函数,通过pivot暂存了基准值,然后使用基准值,左右端点的关系,完成了分割,感兴趣可以打上断点跑一下看看
3.使用Partition算法的快排
function QuickSort(nums, l = 0, r = nums.length - 1){
if(r - l <= 0){
return nums
}
let pos = Partition(nums, l, r)
QuickSort(nums, l, pos - 1)
QuickSort(nums, pos + 1, r)
return nums
}
使用Partition算法的快排,没有创建新的数组,在原数组上交换,完成了排序
4. Three-Partition算法 Three-Partition算法是Partition算法的延伸,把无序数组分为3份,小于基准值,等于基准值,大于基准值,非常适合重复数据很多的数组分割排序
4.1 确定左右边界的Three-Partition算法
function ThreePartition(nums, l = 0, r = nums.length - 1) {
//随机选取一个作为基准值
let mid= random(l, r)
let pivot= nums[mid]
let p = l//这里的p就是左边界,p(含p)左边都是小于基准值的
for (let i = l;
i <= r;
i++) {
while(i <= r && nums[i] > pivot){
swap(nums, i, r)//这里的r就是右边界,r右边都是大于基准值的
r--
}
if(nums[i] < pivot){
swap(nums, i, p)
p++
}
}
return [p,r]
}
这种算法我觉得比
4.2确定左中边界的Three-Partition算法
好理解些,遇到每一个大于基准值的,都交换到右边,同时右边界r--
;
遇到小于基准值的,都交换到左边,同时左边界p++
,更符合常见思维。4.2 确定左中边界的Three-Partition算法
function ThreePartition(nums, l = 0, r = nums.length - 1) {
//随机选取一个作为基准值
let mid= random(l, r)
let pivot= nums[mid]let p0 = p1 = l//p0 0的最右边界//p1中间值的最右边界
for (let i = l;
i <= r;
i++) {
if(nums[i] < pivot){
swap(nums, i, p0)
//因为首先是连续的左值+连续的基准值+连续的右值
//如果p1 > p0则会把一个基准值交换到了i,这不是我们期望的
//这时候我们需要把i和基准值的右边界p1交换
if(p0 < p1){
swap(nums, i, p1)
}
p0++
p1++
}else if(nums[i] == pivot){
swap(nums, i, p1)
p1++
}
}
return [p0,p1-1]
}
这种算法是基于确定左中边界,每次都会左值交换到左边界,把基准值交换到基准值的右边界,但当基准值的右边界
p1
增长过快时,超过p0
,此时就需要把i
和基准值的右边界p1
交换5 使用Three-Partition算法的快排
function QuickSort(nums, l = 0, r = nums.length - 1){
if(r - l <= 0){
return nums
}
let pos = ThreePartition(nums, l, r)
QuickSort(nums, l, pos - 1)
QuickSort(nums, pos + 1, r)
return nums
}
如果无序数组里没有重复值,那么完全等价于Partition算法,如果数组内存在重复值,重复的越多,分布越集中,此算法效率越高
6. 使用Partition算法求解
TopK
问题
function findKthNumber(nums, k){
let l = 0;
let r = nums.length - 1;
while (l <= r){
let pos = Partition(nums, l ,r)
let r_len = r - pos
let l_len = pos
if(k == r_len + 1){
return nums[pos]
}else if(k <= r_len){
l = pos + 1
}else{
r = pos - 1
k -= (r_len + 1)
}
}
return 0
}
效率还是非常高效的
文章图片
7. 使用Three-Partition算法求解
TopK
问题
function findKthNumber(nums, k){
let l = 0;
let r = nums.length - 1;
while (l <= r){
let pos = Partition(nums, l ,r)
let r_len = r - pos
let l_len = pos
if(k == r_len + 1){
return nums[pos]
}else if(k <= r_len){
l = pos + 1
}else{
r = pos - 1
k -= (r_len + 1)
}
}
return 0
}
Three-Partition算法效率也是非常高效的,分布越收敛,越集中,效果则越好
文章图片
推荐阅读
- vue使用router-link做导航栏跳转遇到的Bug
- 企业如何选择最佳云服务提供商()
- 怎么查自己的电话卡号码
- call()apply()和bind()的异同
- XMAPP 的安装与配置
- apple 下安装mysql 以及 碰到的问题
- .Net Core 2.0+ InfluxDB+Grafana+App Metrics 实现跨平台的实时性能监控
- 一文带你看懂ATM的应用权限访问控制能力
- 基于SqlSugar的数据库访问处理的封装,在.net6框架的Web|基于SqlSugar的数据库访问处理的封装,在.net6框架的Web API上开发应用
- 10分钟了解Vue3递归组件的用法