珠排序

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))