一天一算法 - 基数排序
介绍
- 比较型排序和非比较型排序
首先，比较型排序和非比较型排序有何不同呢？很简单，如果在排序过程中，需要比较数组中的元素大小，然后将元素放置在最终位置，这称之为比较型排序。举个简单的例子来说，对于选择排序，排序的思想就是从第一个位置开始，找到数组中最小的元素放进去，那么怎么找到最小的元素呢？这个时候就需要设置一个 min 变量，在数组中依次比较，不断地替换 min（如果元素的值小于 min ） 直到数组最后的一个元素。
一个比较型排序的比较次数直接影响算法的性能，比如选择排序的比较次数就与 (N^2) 成正比。
非比较型排序不需要经过比较就可以将一个数组变成有序的，从理论上来说，它应该快于任何比较型算法，可事实上却不是这样！但是值得注意的是，比较型排序算法的时间复杂度是不可能会突破 O(NlogN) 的，但是非比较型算法比如基数排序在某些情况下却可以突破下界，达到 O(N)。
- 稳定排序和不稳定排序
稳定与不稳定该怎么鉴定呢？数组中有任意两个元素 a[i] 和 a[j], 而且 a[i] 和 a[j] 满足条件 a[i] == a[j] && i > j，如果在排序后，i > j 仍然成立，那么这种排序就是稳定排序，否则是不稳定排序。
基数排序是一种稳定排序算法。
算法思想
将所有待比较的数值统一为相同位数，长度不够的在高位补0，然后从低位开始依次进行排序，这样等排到最高位的时候，整个数组自然就是有序的了。
前面我们说了，基数排序是一种非比较型排序，那么我们依赖怎样的手段对数据进行排序呢？
不论个位，十位还是百位，其数值都在 [0, 9] 这个区间内，所以我们首先声明一个数组 backet[10]，然后再将 bucket[0] ... bucket[9] 声明为数组，这样的话，我们就可以对个位进行排序，因为个位为 0 的都被放在 bucket[0] 这个数组中，个位为 1 的都被放在 bucket[1] 这个数组里...
当进行完个位的排序时，按照顺序将 bucket[] 元素重新推入原数组中，然后将 bucket 数组清空，以便进行十位的排序。
如果看了以上文字你还是浑浑噩噩的，那么就来举个简单的例子，比如我们对以下数组进行排序。
[1, 21, 89, 110, 56]
首先，我们声明一个数组。
var bucket = [];
for(var i = 0; i < 10; i++) {
bucket[i] = [];
}
[1, 21, 89, 110, 56] 的个位分别是 [1, 1, 9, 0, 6], 很显然，对个位排序后，bucket[0] = [110], bucket[1] = [1, 21], bucket[6] = [56], bucket[9] = [89], 将这些数依次推入原数组，这个时候数组为 [110, 1, 21, 56, 89]
[110, 1, 21, 56, 89] 的十位分别为 [1, 0, 2, 5, 8]，对十位进行排序后，bucket[0] = [1], bucket[1] = [110], bucket[2] = [21], bucket[5] = [56], bucket[8] = [89], 将这些数依次推入原数组，这个时候数组为 [1, 110, 21, 56, 89]。
[1, 110, 21, 56, 89] 的百位分别是 [0, 1, 0, 0, 0]，对百位进行排序后，bucket[0] = [1, 21, 56, 89], bucket[1] = [110],将这些数依次推入原数组，这个时候数组为 [1,21,56,89,110]。
可见，这个时候数组就变得有序了，而且和比较型排序不同的是，我们并没有与数组中的其它元素进行比较，只是根据自己各个位数的值让其放进不同的数组中。
实现 (JavaScript)
/*
* @Author: hwaphon
* @Date: 2017-03-10 13:07:02
* @Last Modified by: hwaphon
* @Last Modified time: 2017-03-10 13:34:52
*/
function radixSort(array) {
if (array.length <= 1) {
return array;
}
var length = array.length,
i,
j,
str,
k,
t,
loop,
bucket = [],
max = array[0];
for (i = 1; i < length; i++) {
if (array[i] > max) {
max = array[i];
}
}
loop = (max + '').length;
for (i = 0; i < 10; i++) {
bucket[i] = [];
}
for (i = 0; i < loop; i++) {
for (j = 0; j < length; j++) {
str = array[j] + '';
if (str.length - 1 >= i) {
k = parseInt(str[str.length - i - 1]);
bucket[k].push(array[j]);
} else {
bucket[0].push(array[j]);
}
}
array.splice(0, length);
for (j = 0; j < 10; j++) {
t = bucket[j].length;
for (k = 0; k < t; k++) {
array.push(bucket[j][k]);
}
bucket[j] = [];
}
}
return array;
}
总结
刚才我们介绍的基数排序是从低位开始进行排序的，这种排序称之为最低位优先排序(LSD), 还有一种最高位优先排序（MSD）。LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。
我在我电脑上对比了基数排序与快速排序的效率，无论我选择怎样的数据，总是快速排序更快一点，如果看到我博客的人知道原因或者知道基数排序适用情况请告与我知晓，感激不尽。
还有一点，因为快速排序是原地排序，而基数排序还需要额外的内存消耗，所以在选择排序算法时一定要考虑这一点！
拓展阅读：
