计数排序，桶排序与基数排序
WindChaser 2019-06-26
一般算法能做到O(logn)，已经非常不错，如果我们排序的对象是纯数字，还可以做到惊人的O(n)。涉及的算法有计数排序、基数排序、桶排序，它们被归类为非比较排序。
非比较排序只要确定每个元素之前的已有的元素个数即可，遍历一次就能求解。算法时间复杂度O(n)。
非比较排序时间复杂度低，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。
计数排序
计数排序需要占用大量空间，它仅适用于数据比较集中的情况。比如 [0~100]，[10000~19999] 这样的数据。
我们看一下计数排序是怎么运作，假设我们有[1,2,3,1,0,4]这六个数，这里面最大的值为4，那么我们创建一个长度为4的数组，每个元素默认为0。这相当于选举排序，一共有6个投票箱，1就投1号箱，0就投入0号箱。注意，这些箱本来就是已经排好序，并且箱的编号就是代表原数组的元素。当全部投完时，0号箱有1个，1号箱有2个，2号箱有1个，3号箱有1，4号箱有1个。然后我们从这些箱的所有数依次出来，放到新数组，就神奇地排好序了。
计数排序没有对元素进行比较，只是利用了箱与元素的一一对应关系，根据箱已经排好序的先决条件，解决排序。
//by 司徒正美
function countSort(arr){
var max = Math.max.apply(0, arr);
var buckets = []
for(var i = 0; i < n; i++){
var el = arr[i]
if(buckets[el]){//子桶里不实际存在
buckets[el]++
}else{
buckets[el] = 1
}
}
var index = 0
for(var i = 0; i < n; i++){
var m = buckets[i].length;
while(m){
arr[index] = i;
index++
m--
}
}
return arr
}但数组有一个问题就是它的索引值是从0开始，但我们的元素也要大于或等于0。我们可以通过一个数学技巧让它支持负数。
//by 司徒正美
function countSort(arr){
var max = arr[0]
var min = arr[0]
for(var i = 0; i < n; i++){
if(arr[i] > max){
max = arr[i]
}
if(arr[i] < min){
max = arr[i]
}
}
var buckets = new Array(max-min+1).fill(0);
for(var i = 0; i < n; i++){
buckets[ arr[i]-min ]++ //减去最小值，确保索引大于负数
}
var index = 0, bucketCount = max-min+1
for(var i = 0; i < bucketCount; i++){
var m = buckets[i].length;
while(m){
//将桶的编号加上最小值，变回原来的元素
arr[index] = i+min;
index++
m--
}
}
return arr
}桶排序
桶排序与计数排序很相似，不过现在的桶不单计数，是实实在在地放入元素。举个例子，学校要对所有老师按年龄进行排序，这么多老师很难操作，那么先让他们按年龄段进行分组，20－30岁的一组，30－40岁一组，50－60岁一组，然后组内再排序。这样效率就大大提高了。桶排序也是于这种思想。
操作步骤：
- 确认范围，亦即求取原数组的最大值与最小值。
- 确认需要多少个桶（这个通常作为参数传入，不能大于原数组长度），然后最大值减最小值，除以桶的数量，但得每个桶最多能放多个元素，我们称这个数为桶的最大容量。
- 遍历原数组的所有元素，除以这个最大容量，就能得到它要放入的桶的编号了。在放入时可以使用插入排序，也可以在合并时才使用快速排序。
- 对所有桶进行遍历，如果桶内的元素已经排好序，直接一个个取出来，放到结果数组就行了。
//by 司徒正美
var arr = [2,5,3,0,2,8,0,3,4,3]
function bucketSort(array, num){
if(array.length <= 1){
return array
}
var n = array.length;
var min = Math.min.apply(0, array)
var max = Math.max.apply(0, array)
if(max === min){
return array
}
var capacity = (max - min + 1) /num;
var buckets = new Array(max - min + 1)
for(var i = 0; i < n; i++){
var el = array[i];//el可能是负数
var index = Math.floor((el - min) / capacity)
var bucket = buckets[index]
if(bucket){
var jn = bucket.length;
if(el >= bucket[jn-1]){
bucket[jn] = el
}else{
insertSort:
for(var j = 0; j < jn; j++){
if(bucket[j] > el){
while(jn > j){ //全部向后挪一位
bucket[jn] = bucket[jn-1]
jn--
}
bucket[j] = el //让el占据bucket[j]的位置
break insertSort;
}
}
}
}else{
buckets[index] = [el]
}
}
var index = 0
for(var i = 0; i < num; i++){
var bucket = buckets[i]
for(var k = 0, kn = bucket.length; k < kn; k++){
array[index++] = bucket[k]
}
}
return array;
}
console.log( bucketSort(arr,4) )
//[ 0, 0, 2, 2, 3, 3, 3, 4, 5, 8 ]基数排序
基数排序是一种非比较型的整数排序算法。其基本原理是，按照整数的每个位数分组。在分组过程中，对于不足位的数据用0补位。
基数排序按照对位数分组的顺序的不同，可以分为LSD（Least significant digit）基数排序和MSD（Most significant digit）基数排序。
LSD基数排序，是按照从低位到高位的顺序进行分组排序。MSD基数排序，是按照从高位到低位的顺序进行分组排序。上述两种方式不仅仅是对位数分组顺序不同，其实现原理也是不同的。
LSD基数排序
对于序列中的每个整数的每一位都可以看成是一个桶，而该位上的数字就可以认为是这个桶的键值。比如下面数组
[170, 45, 75, 90, 802, 2, 24, 66]
首先我们要确认最大值，一个for循环得最大数，因为最大数的位数最长。
然后，建立10个桶，亦即10个数组。
然后再遍历所有元素，取其个位数，个位数是什么就放进对应编号的数组，1放进1号桶。
0号桶： 170，90 1号桶： 无 2号桶： 802，2 3号桶： 无 4号桶： 24 5号桶： 45， 75 6号桶： 66 7－9号桶： 无
然后再依次将元素从桶里最出来，覆盖原数组，或放到一个新数组，我们把这个经过第一次排序的数组叫sorted。
sorted = [170,90,802,2,24,45,75,66]
然后我们再一次遍历sorted数组的元素，这次取十位的值。这时要注意，2不存在十位，那么默认为0
0号桶： 2，802 1号桶： 无 2号桶： 24 3号桶： 无 4号桶： 45 5号桶： 无 6号桶： 66 7号桶： 170， 75 8号桶： 无 9号桶： 90
再全部取出来
sorted = [2，802,24，45，66，170，75，90]
开始百位上的入桶操作，没有百位就默认为0：
0号桶： 2，24，45，66，75，90 1号桶： 170 2－7号桶：无 8号桶： 802 9号桶： 无
再全部取出来
sorted = [2，24，45，66，75，90，170，802]
没有千位数，那么循环结束，返回结果桶sorted
从程序描述如下：
//by 司徒正美
function radixSort(array) {
var max = Math.max.apply(0, array);
var times = getLoopTimes(max),
len = array.length;
var buckets = [];
for (let i = 0; i < 10; i++) {
buckets[i] = []; //初始化10个桶
}
for (var radix = 1; radix <= times; radix++) {
//个位，十位，百位，千位这样循环
lsdRadixSort(array, buckets, len, radix);
}
return array;
}
// 根据数字某个位数上的值得到桶的编号
function getBucketNumer(num, d) {
return (num + "").reverse()[d];
}
//或者这个
function getBucketNumer(num, i) {
return Math.floor((num / Math.pow(10, i)) % 10);
}
//获取数字的位数
function getLoopTimes(num) {
var digits = 0;
do {
if (num > 1) {
digits++;
} else {
break;
}
} while ((num = num / 10));
return digits;
}
function lsdRadixSort(array, buckets, len, radix) {
//入桶
for (let i = 0; i < len; i++) {
let el = array[i];
let index = getBucketNumer(el, radix);
buckets[index].push(el);
}
var k = 0;
//重写原桶
for (let i = 0; i < 10; i++) {
let bucket = buckets[i];
for (let j = 0; j < bucket.length; j++) {
array[k++] = bucket[j];
}
bucket.length = 0;
}
}
// test
var arr = [278, 109, 63, 930, 589, 184, 505, 269, 8, 83];
console.log(radixSort(arr));MSD基数排序
接下来讲MSD基数排序.
最开始时也是遍历所有元素，取最大值，得到最大位数，建立10个桶。这时从百位取起。不足三位，对应位置为0.
0号桶： 45, 75, 90, 2, 24, 66 1号桶： 107 2-7号桶： 无 8号桶： 802 9号桶： 无
接下来就与LSD不一样。我们对每个长度大于1的桶进行内部排序。内部排序也是用基数排序。我们需要建立另10个桶，对0号桶的元素进行入桶操作，这时比原来少一位，亦即十位。
0号桶： 2 1号桶： 无 2号桶： 24 3号桶： 无 4号桶： 45 5号桶： 无 6号桶： 66 7号桶： 75 8号桶： 无 9号桶： 90
然后继续递归上一步，因此每个桶的长度，都没有超过1，于是开始0号桶的收集工作：
0号桶： 2，24，45，66，75，90 1号桶： 107 2-7号桶： 无 8号桶： 802 9号桶： 无
将这步骤应用其他桶，最后就排序完毕。
//by 司徒正美
function radixSort(array) {
var max = Math.max.apply(0, array),
times = getLoopTimes(max),
len = array.length;
msdRadixSort(array, len, times);
return array;
}
//或者这个
function getBucketNumer(num, i) {
return Math.floor((num / Math.pow(10, i)) % 10);
}
//获取数字的位数
function getLoopTimes(num) {
var digits = 0;
do {
if (num > 1) {
digits++;
} else {
break;
}
} while ((num = num / 10));
return digits;
}
function msdRadixSort(array, len, radix) {
var buckets = [[], [], [], [], [], [], [], [], [], []];
//入桶
for (let i = 0; i < len; i++) {
let el = array[i];
let index = getBucketNumer(el, radix);
buckets[index].push(el);
}
//递归子桶
for (let i = 0; i < 10; i++) {
let el = buckets[i];
if (el.length > 1 && radix - 1) {
msdRadixSort(el, el.length, radix - 1);
}
}
var k = 0;
//重写原桶
for (let i = 0; i < 10; i++) {
let bucket = buckets[i];
for (let j = 0; j < bucket.length; j++) {
array[k++] = bucket[j];
}
bucket.length = 0;
}
}
var arr = radixSort([170, 45, 75, 90, 802, 2, 24, 66]);
console.log(arr);字符串使用基数排序实现字典排序
此外，基数排序不局限于数字，可以稍作变换，就能应用于字符串的字典排序中。我们先来一个简单的例子，只对都是小写字母的字符串数组进行排序。
小写字母一共26个，考虑到长度不一样的情况，我们需要对够短的字符串进行补充，这时补上什么好呢？我们不能直接上0，而是补空白。然后根据字母与数字的对应关系，弄27个桶，空字符串对应0，a对应1，b对应2.... 字典排序是从左边开始比较， 因此我们需要用到MST基数排序。
//by 司徒正美
var character = {};
"abcdefghijklmnopqrstuvwxyz".split("").forEach(function(el, i) {
character[el] = i + 1;
});
function toNum(c, length) {
var arr = [];
arr.c = c;
for (var i = 0; i < length; i++) {
arr[i] = character[c[i]] || 0;
}
return arr;
}
function getBucketNumer(arr, i) {
return arr[i];
}
function radixSort(array) {
var len = array.length;
var loopTimes = 0;
//求出最长的字符串，并得它的长度，那也是最高位
for (let i = 0; i < len; i++) {
let el = array[i];
var charLen = el.length;
if (charLen > loopTimes) {
loopTimes = charLen;
}
}
//将字符串转换为数字数组
var nums = [];
for (let i = 0; i < len; i++) {
nums.push(toNum(array[i], loopTimes));
}
//开始多关键字排序
msdRadixSort(nums, len, 0, loopTimes);
//变回字符串
for (let i = 0; i < len; i++) {
array[i] = nums[i].c;
}
return array;
}
function msdRadixSort(array, len, radix, radixs) {
var buckets = [];
for (var i = 0; i <= 26; i++) {
buckets[i] = [];
}
//入桶
for (let i = 0; i < len; i++) {
let el = array[i];
let index = getBucketNumer(el, radix);
buckets[index].push(el);
}
//递归子桶
for (let i = 0; i <= 26; i++) {
let el = buckets[i];
//el.c是用来识别是桶还是我们临时创建的数字字符串
if (el.length > 1 && !el.c && radix < radixs) {
msdRadixSort(el, el.length, radix + 1, radixs);
}
}
var k = 0;
//重写原桶
for (let i = 0; i <= 26; i++) {
let bucket = buckets[i];
for (let j = 0; j < bucket.length; j++) {
array[k++] = bucket[j];
}
bucket.length = 0;
}
}
var array = ["ac", "ee", "ef", "b", "z", "f", "ep", "gaaa", "azh", "az", "r"];
var a = radixSort(array);
console.log(a);