Skip to content

Instantly share code, notes, and snippets.

@zyf0330
Created June 28, 2017 08:06
Show Gist options
  • Save zyf0330/547fb50b72102d37b3809180a455a6a3 to your computer and use it in GitHub Desktop.
Save zyf0330/547fb50b72102d37b3809180a455a6a3 to your computer and use it in GitHub Desktop.
const numsNum = 10
const nums = '0'.repeat(numsNum).split('').map(() => parseInt(Math.random() * 100) + 1)
console.log('before sort', nums)
const arrs = []
let push = 0
// 这里的循环说明了空间使用是 O(n2)
for (const num of nums) {
for (let n = 0; n < num; n++) {
if (arrs[n] == null) {
arrs[n] = []
}
push++
// 移动珠子
arrs[n].push(true)
}
}
const sorted = []
for (let i in arrs[0]) {
for (let num = 0; num < arrs.length; num++) {
if (arrs[num][i] == null) {
sorted.push(num)
break
}
if (num == arrs.length - 1) {
sorted.push(num + 1)
break
}
}
}
console.log('after sort ', sorted)
console.log('n', numsNum)
console.log('push num (move ball | space usage)', push, 'nums sum', nums.reduce((sum, num) => sum + num, 0))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment