今天看到睡眠排序和猴子排序,感觉经典确实是经典,为失业编程!简单的写这两个排序,一方面可以锻炼自己的思维能力,另一方面可以进一步理解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]
2 天前