7.堆排序
这种排序方式呢，理论性太强，看动图的时候满脸写着懵逼，多看几遍似乎明白了编者的意图，但是要把这种理论的概念写成代码却不容易，且看代码：
function heapSort(array) {
console.time('堆排序耗时');
//建堆
var heapSize = array.length, temp;
for (var i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
heapify(array, i, heapSize);
}
//堆排序
for (var j = heapSize - 1; j >= 1; j--) {
temp = array[0];
array[0] = array[j];
array[j] = temp;
console.log(array)
heapify(array, 0, --heapSize);
}
console.timeEnd('堆排序耗时');
return array;
}
function heapify(arr, x, len) {
var l = 2 * x + 1, r = 2 * x + 2, largest = x, temp;
if (l < len && arr[l] > arr[largest]) {
largest = l;
}
if (r < len && arr[r] > arr[largest]) {
largest = r;
}
if (largest != x) {
temp = arr[x];
arr[x] = arr[largest];
arr[largest] = temp;
console.log(arr)
heapify(arr, largest, len);
}
}
var arr=[91,60,96,13,35,65,46,65,10,30,20,31,77,81,22];
console.log(heapSort(arr));//[10, 13, 20, 22, 30, 31, 35, 46, 60, 65, 65, 77, 81, 91, 96]；
这种算法有两个难点，一是建堆，而是堆排序。首先明白什么是堆，堆其实可以这么理解，类似金字塔，一层有一个元素，两层有两个元素，三层有四个元素，每层从数组中取元素，从左到右的顺序放到堆相应的位置上，也就是说每一层元素个数为2n-1 ；（n 代表行数），这就完成了建堆。
那么想，堆排序中最后一位不就是2n-m（n代表总行数，m代表差多少位不到完成堆的位数），那该元素的父级是谁，2n-1-m/2，2n-1-m/2是谁？拿总位数除以2就知道了，没错就是数组的中间值，这也是编者为什么从中间值入手的原因了。
而对于 l = 2*x +1 与 r = 2*x+2 ，不正是每个父级元素对应的子堆么，每一层的堆排序都能够把本层的最大值剔除出来，这样当所有 层循环结束之后，序列也就完成了。
这一点小编觉得和归并排序有点类似，都是细分到最小单元，从最小单元比较，但是同归并排序有两大点不同，一是堆排序并不像归并那么无序，只是一味的平分数组，而堆排序则是按原始序列排出金字塔式的结构，把最大值一层层往上冒，冒到金字塔最顶端的时候把它踢出来，这样达到排序的效果。
附动图，不多看几遍是看不出来什么门道的：
8.计数排序
计数排序就是遍历数组记录数组下的元素出现过多次，然后把这个元素找个位置先安置下来，简单点说就是以原数组每个元素的值作为新数组的下标，而对应小标的新数组元素的值作为出现的次数，相当于是通过下标进行排序。
看代码：
function countingSort(array) {
var len = array.length,
B = [],
C = [],
min = max = array[0];
console.time('计数排序耗时');
for (var i = 0; i < len; i++) {
min = min <= array ? min : array;
max = max >= array ? max : array;
C[array] = C[array] ? C[array] + 1 : 1;
console.log(C)
}
// 计算排序后的元素下标
for (var j = min; j < max; j++) {
C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);
console.log(C)
}
for (var k = len - 1; k >= 0; k--) {
B[C[array[k]] - 1] = array[k];
C[array[k]]--;
console.log(B)
}
console.timeEnd('计数排序耗时');
return B;
}
var arr = [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2];
console.log(countingSort(arr)); //[1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9]；
这种算法的亮点就是在于利用下标存数据，利用数据存出现的次数。然后这种算法还有一个亮点就是第二个循环，计算排序后的下标，也就是说在这个地方已经把每个元素对应在排序后的数组的位置已经确定了，在第三个循环中只需要安插在对应的位置即可!
其实这里小编还另外一种算法，没有上面那种复杂，小编感觉更容易理解，仅供参考：
function countingSort(array) {
var len = array.length,
B = [],
C = [],
min = max = array[0];
console.time('计数排序耗时');
for (var i = 0; i < len; i++) {
min = min <= array ? min : array;
max = max >= array ? max : array;
C[array] = C[array] ? C[array] + 1 : 1;
}
for (var k = 0; k <len; k++) {
var length = C[k]；
for(var m = 0 ;m <length ; m++){
B.push(k);
}
}
console.timeEnd('计数排序耗时');
return B;
}
var arr = [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2];
console.log(countingSort(arr)); //[1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9]；
思想主要是既然我们已经根据下标进行排序了，C数组的下标对应的数值就是该下标出现的次数，那何不吧该次数作为二层循环的长度遍历一遍直接推送到新得数组中呢？
附动图便于理解：
9. 桶排序
一看到这个名字就会觉得奇特，几个意思，我排序还要再准备几个桶不成？还真别说，想用桶排序还得真准备几个桶，但是此桶非彼桶，这个桶是用来装数据用的。其实桶排序和计数排序还有点类似，计数排序是找一个空数组把值作为下标找到其位置，再把出现的次数给存起来，这似乎看似很完美，但也有局限性，不用小编说相信读者也能明白，既然计数是把原数组的值当做下标来看待，那么该值必然是整数，那假如出现小数怎么办？这时候就出现了一种通用版的计数排序——桶排序。
小编觉得桶排序可以这么理解，它是以步长为分隔，将最相近数据分隔在一起，然后再在一个桶里排序。好了，现在有个概念，步长是什么玩意？这么来说吧，比如在知道十位的情况下48和36有比较的必要吗？显然没有，十位就把你干下去了，还比什么？那在这里可以简单的把步长理解为10，桶排序就是这样，先把同一级别的分到一组，由同一级别的元素进行排序。
代码实现：
@param array 数组
@param num 桶的数量
function bucketSort(array, num) {
if (array.length <= 1) {
return array;
}
var len = array.length, buckets = [], result = [], min = max = array[0], space, n = 0;
var index = Math.floor(len / num) ;
while(index<2){
num--;
index = Math.floor(len / num) ;
}
console.time('桶排序耗时');
for (var i = 1; i < len; i++) {
min = min <= array ? min : array;
max = max >= array ? max : array;
}
space = (max - min + 1) / num; //步长
for (var j = 0; j < len; j++) {
var index = Math.floor((array[j] - min) / space);
if (buckets[index]) { // 非空桶，插入排序
var k = buckets[index].length - 1;
while (k >= 0 && buckets[index][k] > array[j]) {
buckets[index][k + 1] = buckets[index][k];
k--;
}
buckets[index][k + 1] = array[j];
} else { //空桶，初始化
buckets[index] = [];
buckets[index].push(array[j]);
}
}
while (n < num) {
result = result.concat(buckets[n]);
n++;
}
console.timeEnd('桶排序耗时');
return result;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bucketSort(arr,4));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50];
但是这边有个坑点，就是桶的数量不能过多，也就说说至少两个桶！为什么？你试下就知道了！
附图理解：
10.基数排序
其实基数排序和桶排序挺类似的，都是找一个容器把属于同一类的元素装起来，然后进行排序。可以把基数排序类比成已知该序列的最高位，然后以除去相对来说的最低位（可能是个位，可能是十位）剩余的位数为桶数，这样一来步长就是10或者100了。但是基数排序相对桶排序又有多了一个亮点，那就是基数排序是先排最低位（个位），把最低位一致的放在一个桶里，然后依次取出，再进一位（十位），把十位相同的再放到一个桶里，然后再取出，这样经过两次重排序就能得到百位以内的排序序列了，百位，千位也是如此。
/**
* 基数排序适用于：
* (1)数据范围较小，建议在小于1000
* (2)每个数值都要大于等于0
* @author damonare
* @param arr 待排序数组
* @param maxDigit 最大位数
*/
//LSD Radix Sort
function radixSort(arr, maxDigit) {
var mod = 10;
var dev = 1;
var counter = [];
console.time('基数排序耗时');
for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
for(var j = 0; j < arr.length; j++) {
var bucket = parseInt((arr[j] % mod) / dev);
if(counter[bucket]== null) {
counter[bucket] = [];
}
counter[bucket].push(arr[j]);
}
var pos = 0;
for(var j = 0; j < counter.length; j++) {
var value = null;
if(counter[j]!=null) {
while ((value = counter[j].shift()) != null) {
arr[pos++] = value;
}
}
}
}
console.timeEnd('基数排序耗时');
return arr;
}
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(radixSort(arr,2)); //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]；
但是基数排序也有个弊端，就是必须知道最高位有多少位。
附动图：