从简单的快速排序说起-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 }

效率还是非常高效的
从简单的快速排序说起-Partition-ThreePartition-TopK
文章图片

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算法效率也是非常高效的,分布越收敛,越集中,效果则越好
从简单的快速排序说起-Partition-ThreePartition-TopK
文章图片

    推荐阅读