简析计数排序

echosoar 原创发表于 2015/12/26 22:34:29
#排序

什么是计数排序?

计数排序是一个非基于比较的排序算法,该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围),快于任何比较排序算法。
计数排序的基本思想是对于给定的输入序列中的每一个元素x,确定该序列中值小于x的元素的个数。
知道了有多少个小于x的元素,那么就可以将x直接存放到最终的输出序列的正确位置上。
例如,如果输入序列中只有20个元素的值小于x的值,则x可以直接存放在输出序列的第21个位置上。
但是如果存在多个重复的值,比如说有下面这样的一个数组:
[100,93,97,92,96,99,92,89,93,97,90,94,92,95]
这里面有3个92,2个93,如果按照上面的方法这几个相等的值就会出现在同一个位置上,所以需要想一个办法解决这个问题。

计数排序的实现

function jishuSort(/*Array*/a){
    var len=a.length;
    var min=a[0],max=a[0],k,i;
    for(i=0;i<len;i++){
        if(a[i]>max)max=a[i];
        if(a[i]<min)min=a[i];
    }
    k=max-min;
    var b=[],c=[];
    for(i=0;i<=k;i++){
        c[i]=0;
    }
    for(i=0;i<len;i++){
        c[a[i]-min]+=1;
    }
    for(i=1;i<=k;++i){
        c[i]=c[i]+c[i-1];
    }
    for(i=len-1;i>=0;--i){
       b[--c[a[i]-min] ]=a[i];
    }
    return b;
}
上面这段代码中,首先是计算最大值与最小值之间的差值,建立一个宽度为这个差值的用来储存差值个数的数组,然后计算每一个值与最小值之间的差值,把对应的差值的个数加一。 然后使用一个循环来计算每一个差值所代表的数字在排序后的数组中出现的最后的位置,实现的方法就是从第二个值开始每一个值加上它前面那个差值的数目。 最后就是将每一个原始值按照它应该被摆放的位置存入结果数组。