荷兰国旗

荷兰国旗问题，例如一个数组[1,4,3,5,6,7,2],给定一个num=2，把小于num的放左边，等于num的放中间，大于num的放右边。

function partition(arr, num) {
    let cur = 0,
        left = -1,
        right = arr.length
    while (cur < right) {
        if (arr[cur] < num) {
            //小于num 把这个数跟小于区域的下一个数交换 小于区域向右扩大一位 cur向右挪一位
            swap(arr, ++left, cur++)
        } else if (arr[cur] > num) {
            //大于num 把这个数跟大于区域的前一个数交换 cur不动 继续考察换过来的这一个数 大于区域向左扩大一位
            swap(arr, --right, cur)
        } else {
            cur++
        }
    }
}

function swap(arr, i, j) {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

经典快排

相当于把数组的最后一个数当做num，递归partition操作。

function quickSort(arr, L, R) {
    if (L < R) {
        let a = partition(arr, L, R)
        quickSort(arr, L, a[0] + 1)
        quickSort(arr, a[1], R)
    }
}

function partition(arr, L, R) {
    let cur = L,
        left = L - 1,
        right = R,
        target = arr[right - 1]
    while (cur < right) {
        if (arr[cur] < target) {
            //小于num 把这个数跟小于区域的下一个数交换 小于区域向右扩大一位 cur向右挪一位
            swap(arr, ++left, cur++)
        } else if (arr[cur] > target) {
            //大于num 把这个数跟大于区域的前一个数交换 cur不动 继续考察换过来的这一个数 大于区域向左扩大一位
            swap(arr, --right, cur)
        } else {
            cur++
        }
    }
    return [left, right]
}

function swap(arr, i, j) {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}
let arr = [7, 2, 1, 4, 3, 5, 6]
quickSort(arr, 0, arr.length)
console.log(arr)

随机快排

先随机选一个数与最后一个数交换，再来做划分
只需在partition之前加上一句

swap(arr, L + Math.floor(Math.random() * (R - L)), R - 1)