js排序下篇（归并排序、计数排序、桶排序、基数排序、堆排序「请看后面的第二篇博客」）_综合

归并排序（递归法 - 自上而下）

归并排序(MergeSort)是创建在归并操作上的一种有效的排序算法，是采用分治法的一个典型应用。
归并操作指的是将两个已经排序的序列合并成一个序列的操作。有递归和迭代两种方法。

工作原理

递归法原理如下：
1．申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2．设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3．比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4．重复步骤3直到某一指针到达序列尾；
5．将另一序列剩下的所有元素直接复制到合并序列尾。

js代码实现 + 效率测试

运算10次，平均耗时40.14 ms

// 创建 20000 个随机数，数值范围：1 - 100000
let ary = [];
for (let i = 0; i < 20000; i++) {
    ary.push( Math.floor( Math.random()*99999 + 1 ) );
}// 归并排序 - 递归
function mergeSortTopDown(arr) {
    if (arr.length < 2) return arr;let mid = Math.floor(arr.length / 2);let left = arr.slice(0, mid),right = arr.slice(mid);return _merge(mergeSortTopDown(left), mergeSortTopDown(right));
}function _merge(left, right) {
    let result = [];while (left.length > 0 && right.length > 0) {
    if (left[0] <= right[0]) {
    result.push( left.shift() );}else {
    result.push( right.shift() );}}return result.concat(left).concat(right);
}console.time( '归并排序 - 递归 - 自上而下' );
ary = mergeSortTopDown( ary );
console.timeEnd( '归并排序 - 递归 - 自上而下' );

归并排序（迭代法 - 自下而上）

工作原理

迭代法原理如下：
1．将序列每对相邻两个数字进行归并操作，形成n/2个序列，排序后每个序列包含
一或两个元素；
2．若此时序列数不是1个则将上述序列再次归并，形成n／4个序列，每个序列包三或四个元素；
3．重复步骤2，直到所有元素排序完毕，即序列数为1。

js代码实现 + 效率测试

运算10次，平均耗时30.88 ms

// 创建 20000 个随机数，数值范围：1 - 100000let ary = [];for (let i = 0; i < 20000; i++) {
    ary.push( Math.floor( Math.random()*99999 + 1 ) );}// 归并排序 - 迭代 - 自下而上function mergeSortDownTop(arr) {
    function _merge(arr, leftStart, leftEnd, rightStart, rightEnd) {
    let leftArr = [], rightArr = [];for (let i = leftStart; i < leftEnd; i++) {
    leftArr.push( arr[i] );}for (let i = rightStart; i < rightEnd; i++) {
    rightArr.push( arr[i] );}leftArr.push( Infinity );rightArr.push( Infinity );let m = 0, n = 0;for (let i = leftStart; i < rightEnd; i++) {
    if (leftArr[m] <= rightArr[n]) {
    arr[i] = leftArr[m];m++;}else {
    arr[i] = rightArr[n];n++;}}}let step = 1, len = arr.length, left, right;while (step < len) {
    left = 0, right = step; // 初始化相邻两个区间的起始位置while (right + step < len) {
     // 如果足够两个当前 step 的完整区间再排序_merge(arr, left, left + step, right, right + step);left = right + step;right = left + step;}if (right < len) {
     // 如果最终还有一个不足完整 step 区间未排序_merge(arr, left, left + step, right, len);}step *= 2;}}console.time( '归并排序 - 迭代 - 自下而上' );mergeSortDownTop( ary );console.timeEnd( '归并排序 - 迭代 - 自下而上' );

计数排序

工作原理

计数排序是一种稳定的线性时间排序算法。
当输入的元素是n个0到k之间的整数时，它的运行时间是Θ(n+k)。
计数排序不是比较排序，排序的速度快于任何比较排序算法。
算法的步骤如下：

找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去1。

js代码实现 + 效率测试

运算10次，平均耗时7.06 ms

// 创建 20000 个随机数，数值范围：1 - 100000
let ary = [];
for (let i = 0; i < 20000; i++) {
    ary.push( Math.floor( Math.random()*99999 + 1 ) );
}// 计数排序
function countingSort(arr) {
    let maxNum = Math.max( ...arr );let ans = new Array( maxNum + 1 ).fill( 0 );for (let i = 0, len = arr.length; i < len; i++) {
    ans[ arr[i] ] ++;}let k = 0;for (let i = 0, len = ans.length; i < len; i++) {
    let count = ans[i];while (count > 0) {
    arr[k] = i;k++;count--;}}
}console.time( '计数排序' );
countingSort( ary );
console.timeEnd( '计数排序' );

桶排序

工作原理

将数组分到有限数量的桶里，再对每个桶分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）
桶排序以下列程序进行：

设置一个定量的数组当作空桶；
遍历序列，并且把项目逐一放到对应的桶中；
对每个不是空的桶进行排序；
从不是空的桶里把项目再放回到原来的序列中。

js代码实现 + 效率测试

运算10次，平均耗时22.04 ms

// 创建 20000 个随机数，数值范围：1 - 100000
let ary = [];
for (let i = 0; i < 20000; i++) {
    ary.push( Math.floor( Math.random()*99999 + 1 ) );
}// 桶排序
function bucketSort(arr, bucketSize) {
    const DEFAULT_BUCKET_SIZE = 5;let len = arr.length;if (len < 2) return arr;let min = max = arr[0];for (let i = 0; i < len; i++) {
    let curr = arr[i];if (curr > max) {
    max = curr;}if (curr < min) {
    min = curr;}}if (max === min) return arr;bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;let bucketCount = Math.floor((max - min) / bucketSize) + 1;let bucket = new Array( bucketCount );for (let i = 0; i < bucketCount; i++) {
    bucket[i] = [];}for (let i = 0; i < len; i++) {
    // 这里我选择在放入桶中的同时使用插入排序 -- 重点学习这种排序的思想哈// （当然也可以把元素全部分好桶，在进行排序，快排等等别的排序也是可以的。。。）let bucketIndex = Math.floor( (arr[i] - min) / bucketSize ),curr = arr[i],bLength = bucket[ bucketIndex ].length;if (bLength === 0) {
    bucket[ bucketIndex ].push( curr );}else {
    let j = bLength - 1;while (j >= 0 && bucket[ bucketIndex ][j] > curr) {
    bucket[ bucketIndex ][j + 1] = bucket[ bucketIndex ][j];j--;}bucket[ bucketIndex ][j + 1] = curr;}}// 此时，每个桶中的序列都已经排好序，把他们拼接起来，直接在原数组操作let p = 0;for (let i = 0, len = bucket.length; i < len; i++) {
    let currBucket = bucket[i];for (let j = 0, cLen = currBucket.length; j < cLen; j++) {
    arr[p] = currBucket[j];p++;}}
}console.log( '原数组', ary );
console.time( '桶排序' );
bucketSort( ary );
console.timeEnd( '桶排序' );

基数排序

工作原理

基数排序是一种非比较型整数排序算法。其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串和特定格式的浮点数，所以基数排序也不是只能使用于整数。

将所有待比较数值（正整数）统一为同样的数字长度，数字较短的数前面补零；
然后，从最低位开始，依次进行一次排序。
这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

js代码实现 + 效率测试

运算10次，平均耗时37.51 ms

// 创建 20000 个随机数，数值范围：1 - 100000
let ary = [];
for (let i = 0; i < 20000; i++) {
    ary.push( Math.floor( Math.random()*99999 + 1 ) );
}// 桶排序 - 针对十进制的数字
function radixSort(arr, long) {
    // 1.没有传字符数的话，那就取数组的第一个数字的长度为 longif (arr.length < 2) return arr;const DEFAULT_LONG = 5;long = long || DEFAULT_LONG;// 2.建立1个桶的集合，将放置 10 个桶 - { 0 - 9 }let bucket = [];// 3.循环 long 次，从最后一位开始比较let arrLength = arr.length;for (let i = long - 1; i >= 0; i--) {
    for (let i = 0; i < 10; i++) {
    bucket[i] = [];}for (let j = 0; j < arrLength; j++) {
    let str = String( arr[j] );str = str.length < long ? '0'.repeat( long - str.length ) + str : str;let index = Number( str.substr( i, 1 ) );bucket[ index ].push( arr[j] );}let p = 0;for (let m = 0, bucketLen = bucket.length; m < bucketLen; m++) {
    let currBucket = bucket[m];for (let n = 0, currLen = currBucket.length; n < currLen; n++) {
    arr[p] = currBucket[n];p++;}}}
}console.time( '基数排序' );
radixSort( ary, 5 );
console.timeEnd( '基数排序' );

不仅没有按照上篇博客的计划写完这篇，而且，堆排序要放到下一个周末来写了，因为还有别的事情要做，先写到这吧，我先忏悔3分钟。。。