写了很多次 快速排序，每次都要在 partition 函数这里卡很久，

经过多次总结，发现这样写的 partition 函数最简洁。自己 Mark 一下。

function partition(nums, left, right) {
    if (right <= left) {
        return
    }
    const pivotIndex = getPivotIndex(left, right)
    const pivot = nums[pivotIndex]
    swap(nums, left, pivotIndex)
    let i = left + 1
    let next = i
    while(i < right) {
        const item = nums[i]
        if (item < pivot) {
            swap(nums, i, next)
            next++
        }
        i++
    }
    const k = next - 1
    swap(nums, k, left)
    partition(nums, left, k)
    partition(nums, k + 1, right)
}

function getPivotIndex(left, right) {
    return Math.floor(Math.random() * (right - left)) + left
}

function swap(nums, a, b) {
    const temp = nums[a]
    nums[a] = nums[b]
    nums[b] = temp
}