function countSort(array, keyName){ var length = array.length, output = new Array(length), max, min, simpleArray = keyName ? array.map(function(v){ return v[keyName]; }) : array; // 如果keyName是存在的，那么就创建一个只有keyValue的简单数组 // 获取最大最小值 max = min = simpleArray[0]; simpleArray.forEach(function(v){ v > max && (max = v); v < min && (min = v); }); // 获取计数数组的长度 var k = max - min + 1; // 新建并初始化计数数组 var countArray = new Array(k); simpleArray.forEach(function(v){ countArray[v - min]= (countArray[v - min] || 0) + 1; }); // 累加计数，存储不同值的初始下标 countArray.reduce(function(prev, current, i, arr){ arr[i] = prev; return prev + current; }, 0); // 从原数组挨个取值(因取的是原数组的相应值，只能通过遍历原数组来实现) simpleArray.forEach(function(v, i){ var j = countArray[v - min]++; output[j] = array[i]; }); return output; }
以上实现不仅支持了数值序列的排序，还支持根据对象的某个属性值来排序。测试如下：
var a = [2, 1, 1, 3, 2, 1, 4, 2], b = [ {id: 2, s:'a'}, {id: 1, s: 'b'}, {id: 1, s: 'c'}, {id: 3, s: 'd'}, {id: 2, s: 'e'}, {id: 1, s: 'f'}, {id: 4, s: 'g'}, {id: 2, s: 'h'} ]; countSort(a); // [1, 1, 1, 2, 2, 2, 3, 4] countSort(b, 'id'); // [{id:1,s:'b'},{id:1,s:'c'},{id:1,s:'f'},{id:2,s:'a'},{id:2,s:'e'},{id:2,s:'h'},{id:3,s:'d'},{id:4,s:'g'}]
Tips: 计数排序不改变相同元素之间原本相对的顺序, 因此它是稳定的排序算法.
桶排序桶排序即所谓的箱排序, 它是将数组分配到有限数量的桶子里. 每个桶里再各自排序(因此有可能使用别的排序算法或以递归方式继续桶排序). 当每个桶里的元素个数趋于一致时, 桶排序只需花费O(n)的时间. 桶排序通过空间换时间的方式提高了效率, 因此它需要额外的存储空间(即桶的空间).
算法的基本思想:
桶排序的核心就在于怎么把元素平均分配到每个桶里, 合理的分配将大大提高排序的效率.
如下是算法实现:
function bucketSort(array, bucketSize) { if (array.length === 0) { return array; } var i = 1, min = array[0], max = min; while (i++ < array.length) { if (array[i] < min) { min = array[i]; //输入数据的最小值 } else if (array[i] > max) { max = array[i]; //输入数据的最大值 } } //桶的初始化 bucketSize = bucketSize || 5; //设置桶的默认大小为5 var bucketCount = ~~((max - min) / bucketSize) + 1, //桶的个数 buckets = new Array(bucketCount); //创建桶 for (i = 0; i < buckets.length; i++) { buckets[i] = []; //初始化桶 } //将数据分配到各个桶中,这里直接按照数据值的分布来分配,一定范围内均匀分布的数据效率最为高效 for (i = 0; i < array.length; i++) { buckets[~~((array[i] - min) / bucketSize)].push(array[i]); } array.length = 0; for (i = 0; i < buckets.length; i++) { quickSort(buckets[i]); //对每个桶进行排序，这里使用了快速排序 for (var j = 0; j < buckets[i].length; j++) { array.push(buckets[i][j]); //将已排序的数据写回数组中 } } return array; }
Tips: 桶排序本身是稳定的排序, 因此它的稳定性与桶内排序的稳定性保持一致.
实际上, 桶也只是一个抽象的概念, 它的思想与归并排序,快速排序等类似, 都是通过将大量数据分配到N个不同的容器中, 分别排序, 最后再合并数据. 这种方式大大减少了排序时整体的遍历次数, 提高了算法效率.
基数排序基数排序源于老式穿孔机, 排序器每次只能看到一个列. 它是基于元素值的每个位上的字符来排序的. 对于数字而言就是分别基于个位, 十位, 百位 或千位等等数字来排序. (不明白不要紧, 我也不懂, 请接着往下读)
按照优先从高位或低位来排序有两种实现方案:
MSD: 由高位为基底, 先按k1排序分组, 同一组中记录, 关键码k1相等, 再对各组按k2排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码kd对各子组排序后. 再将各组连接起来, 便得到一个有序序列. MSD方式适用于位数多的序列.
LSD: 由低位为基底, 先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列. LSD方式适用于位数少的序列.
如下是LSD的动图效果:
如下是算法实现:
function radixSort(array, max) { var buckets = [], unit = 10, base = 1; for (var i = 0; i < max; i++, base *= 10, unit *= 10) { for(var j = 0; j < array.length; j++) { var index = ~~((array[j] % unit) / base);//依次过滤出个位,十位等等数字 if(buckets[index] == null) { buckets[index] = []; //初始化桶 } buckets[index].push(array[j]);//往不同桶里添加数据 } var pos = 0, value; for(var j = 0, length = buckets.length; j < length; j++) { if(buckets[j] != null) { while ((value = buckets[j].shift()) != null) { array[pos++] = value; //将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞 } } } } return array; }
以上算法, 如果用来比较时间, 先按日排序, 再按月排序, 最后按年排序, 仅需排序三次.
基数排序更适合用于对时间, 字符串等这些整体权值未知的数据进行排序.
Tips: 基数排序不改变相同元素之间的相对顺序, 因此它是稳定的排序算法.
小结各种排序性能对比如下: