关于javascript:从简单的快速排序说起PartitionThreePartitionTopK

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 算法是一种原地宰割排序的的算法，选定一个基准值，将每一个小于基准值的替换到右边，将每一个大于基准值的替换到左边，最初基准值居中，是一种原地宰割的算法，除了常数级的变量外，没有应用额定的空间

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 算法效率也是十分高效的，散布越收敛，越集中，成果则越好