基数排序

• 时间复杂度（平均）：O(n * k)
• 时间复杂度（最坏）：O(n * k)
• 时间复杂度（最好）：O(n * k)
• 空间复杂度：O(n + k)
• 稳定

由于整数可以表达字符串（名字或者时间）和特定格式的浮点数，所以基数排序也不一定只用于整数排序

算法

按位比较，第一次按个位由小到大排列；第二次按十位由小到大排列。。。以此类推

当第二次十位比较结果相同时，将按照第一次个位比较来判断两个数字的大小，因为将桶中数据按照先push先shift的操作，所以排序是稳定的

// 第二个参数是数组中数据的最大位数
function radixSort(arr, maxDigit) {
	let unit = 10,
		base = 1;
	const buckets = [];
	for (let i = 0; i < maxDigit; i++, unit *= 10, base *= 10) {
		for (let j = 0; j < arr.length; j++) {
			let index = ~~((arr[j] % unit) / base);
			if (!buckets[index]) {
				buckets[index] = [];
			}
			buckets[index].push(arr[j]);
		}
		let arrIndex = 0;
		for (let i = 0; i < buckets.length; i++) {
			while (buckets[i] && buckets[i].length) {
				arr[arrIndex++] = buckets[i].shift();
			}
		}
	}
	return arr;
}