手记

对数据结构和算法的总结和思考(六)--计数排序

计数排序是我所知排序里面速度最快得排序方式(元素分布均匀),也是所学里面第一种不需要比较的排序方式。那么现在问题来了,既然这个排序方式这么棒,但是为什么有很多小伙伴都没有听说过~这就不得不提这个排序算法的缺陷了,它只支持整数排序,是不是很尴尬,是不是很难受~,下面我就来分享下这个排序算法。

核心思想:
计数排序的基本思想是对于给定的输入序列中的每一个元素x,确定该序列中值小于x的元素的个数(此处并非比较各元素的大小,而是通过对元素值的计数和计数值的累加来确定)。一旦有了这个信息,就可以将x直接存放到最终的输出序列的正确位置上。例如,如果输入序列中只有17个元素的值小于x的值,则x可以直接存放在输出序列的第18个位置上。当然,如果有多个元素具有相同的值时,我们不能将这些元素放在输出序列的同一个位置上,因此,上述方案还要作适当的修改,即如果元素相同,则同一个位置值加一。

具体实现如下:

// 计数排序法
function countingSort(array) {
    var len = array.length,
        B = [],
        C = [],
        min = max = array[0];
    console.time('计数排序耗时');
    //找出最大和最小值,并把元素放到新数组中它的值所对应的位置上,入a[1] = 5 , 则C[5] = 1.如果该位置已经存在元素,那该位置值+1
    for (var i = 0; i < len; i++) {
        min = min <= array[i] ? min : array[i];
        max = max >= array[i] ? max : array[i];
        C[array[i]] = C[array[i]] ? C[array[i]] + 1 : 1;
    }

    //这一步是关键,计算每个位置前面有多少小于或等于它的元素。例如本来C为[, 1, 0, 1, 2] 那么在C[1]前面有多少个比C[1]小的值,1个,在C[2]
    //前面有多少个比C[2]小的值,1 + 0 = 1个,在C[3]前有 1+0+1 = 2个,以此类推。
    for (var j = min; j < max; j++) {
        C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);
    }
    // 现在C中存储的C[i]元素为小于i的元素个数

    // 扫描整个数组,对数组中的每一个元素C[array[k]],将C[array[k]]放在输出数组的第C(C[array[k] - 1])个位置上,并将C[array[k]]减1。
    for (var k = 0; k < len; k++) {
        B[C[array[k]] - 1] = array[k];
        C[array[k]]--;
    }
    console.timeEnd('计数排序耗时');
    return B;
}

var sortArr = [];
for (var i = 0;i < 1000; i ++) {
    sortArr.push(Math.floor(Math.random() * 10000));
}
console.time('计数排序耗时 ');
console.log(countingSort(sortArr)); 
console.timeEnd('计数排序耗时 ');

计数排序主要就是把元素先放到一个新数组中值对应的位置,就能知道自己前面有多少个比自己小的元素,然后一次遍历放置就行。原理还是比较简单,主要需要理解两个地方,一个是计算自己前面有多少个元素,另一个就是把自己放在哪个位置。好了,排序算法就分享完了,如有不懂,请留言,后续会讲解查找算法和数据结构,thx~

0人推荐
随时随地看视频
慕课网APP