JS中的睡眠排序、猴子排序

今天看到睡眠排序和猴子排序，感觉经典确实是经典，为失业编程！简单的写这两个排序，一方面可以锻炼自己的思维能力，另一方面可以进一步理解JS三座山之间的异步。

睡眠排序就遇到一个数就把一个数放到一个线程里睡着，然后先醒的先放到数组里，后醒的后放到数组里，时间复杂度取决于这个数组里的最大数是多少，理论上可以达到正无穷。

JS是单线程的，可以使用setTimeout来假装一下，下面的手写使用 async 和 await 处理异步函数：

let arr = [2,4,-7,6,-9]
function getArray(numbers){
    return new Promise((resolve) => {
        let ary = []
        numbers.forEach((el) => {
            //  如果小于0 那就按照先完成的先放，后完成的后放（时间越大数越小，放在数组左边）
            if (el < 0) {
                setTimeout(() => {
                    ary.unshift(el)
                    if (ary.length === numbers.length) resolve(ary)
                }, ~(el * 4 + 4))  // 时间取正数 因为 setTimeout 的最小延迟时间是4ms以及确保0的时候也有延迟
            } else {
                setTimeout(() => {
                    ary.push(el)
                    if (ary.length === numbers.length) resolve(ary)
                }, el * 4 + 4)
            }
        })
    });
}
async function sleepSort(numbers){  //  异步函数
    let data = await getArray(numbers)  //  等待promise 完成并返回结果
    console.log(data)  //  [-9, -7, 2, 4, 6]
    return data
}
console.log(sleepSort(arr));  //  Promise{<pending>}

猴子排序

有一个经典的说法，把一直猴子和一个电脑放到一个房间里，给它无限的时间，那么他在键盘上乱敲总能敲出一部《莎士比亚》，

猴子排序就是把一个数组全部打乱，总有一次能够排序成功。这个时间复杂度依据数组长度，数越多，理论上也可以到达正无穷，但是最小时间复杂度可以到1（欧皇附体）。

猴子排序主要实现就是如何打乱整个数组的顺序，使用的方法是每一个数都与数组内的随机一个数进行交换，然后检测数组是否有序

function shuffle(numbers){
    let len = numbers.length
    while (len--){
        let random = (Math.random() * len >>> 0);  //  注意分号 否则JS会认为是()[]
            [numbers[random], numbers[len]] = [numbers[len], numbers[random]]
    }
}
function monkeySort(numbers){
    while (true){
        shuffle(numbers)
        let blo = true
        for (let i=0; i<numbers.length-1; i++){
            if (numbers[i]>numbers[i+1]){
                blo = false
                break
            }
        }
        if (blo) return
    }
}
monkeySort(arr)
console.log(arr);  //  [-9, -7, 2, 4, 6]

链接: https://www.fly63.com/article/detial/12416