计数排序以及桶排序

何为计数排序

比如有10个数的数组arr=[0,4,39,0,2,44,39,6,4,0],范围是0-50,要求对这100个数进行排序.计数排序是这么做的(对这个简单的例子来说,计数排序并不是最优的):

计数排序的分析和使用情景

假设counter数组的大小为k,则由于还需要结果数组保存结果,因此计数排序的空间复杂度为O(k+n).时间上计数排序需.要初始化counter,迭代arr,迭代counter,迭代arr,因此时间复杂度为O(k+n+k+n)=O(k+n).

数字范围是0-50的10个数字序列的例子过于简单,考虑其他的情况:

  1. 1000个数字,数字的范围是1-2^31
  2. 1000000个数字,数字范围是1-100
  3. 1000000个数字,数字范围是999,999,000-1,000,000,000
  4. 100个数字,数字范围是1-100.

情况1中如果用计数排序,将需要非常大的内存空间,而且初始化counter耗去大部分的时间.空间和时间效率上都比基于比较的排序方法差太多了(基于比较的排序方法的时间复杂度下限是O(nlg(n)) . 情况2是典型的计数排序场景.
情况3中虽然数字的数值很大,但是范围也仅仅在1000之内,开辟一个1001的数组也就足够了,也非常适合利用计数排序.
情况4数字范围小,问题规模也小,这时候用计数排序效果就不明显了.虽然时间复杂度是O(n+k),看起来好像比基于比较的排序方法的O(nlg(n))好,但其实不然,原因是计数排序的系数比较大,问题上了规模才能体现他的效率.

综上所述,只有问题规模大,数字范围小时,才比较适合使用计数排序

计数排序的实现

根据第一部分的说明,不难得出计数排序的实现:

当然这个版本只能处理裸数据(没有其他卫星数据),而不像之前的版本一样可以处理一些复合数据(有其他数据附加在键上).

参考3中说:

不过这种方法不再是计数排序,而是桶排序(Bucket Sort),确切地说,是桶排序的一种特殊情况。

但是我觉得这两者并没有本质区别

何为桶排序

有时候,当数据数值范围太大时,我们无法开出足够大的数组,这时候又该怎么办?
比如有100w个数据,数据范围0-100w.那么我们可以开辟出1000个桶(bucket),第一个桶存放0-999这1000个数,第二个桶存放1000-1999这1000个数...以此类推.将数据全部分配到桶中之后,再依次对有数据的桶进行排序(可以采用插入排序,计数排序等稳定排序方法),最后再依次将所有桶中的数据串在一起即可.
这就是桶排序.)

计数排序和桶排序的区别

按照我的理解,其实计数排序和桶排序并没有本质上得区别.计数排序仅仅是桶排序的一种特殊情况(在这种情况下,每个桶中只放相同的数值.而其他情况每个桶要放若干个数值.而由于计数排序中每个桶的数值相等,也就免去了对桶中数据进行排序的过程).
桶排序要想得到较好的效率,还必须要求输入数据是均匀分布在各个桶中的,这种情况下,桶排序以线性期望时间运行.如果不幸所有数据都落入了同一个桶中,那么桶排序的时间复杂度就取决于对桶中数据采取的排序方法了. 因此,除了对内存的需求不同外,计数排序和桶排序的第二个区别就是:是否要求输入数据符合正态分布..无论数据分布如何,计数排序的效率不会受到影响.

桶排序的效率分析

关于桶排序的效率分析,<<算法导论>>中有大篇幅的推导,看不明白.
倒是比较认可参考6中的分析:

对于N个待排数据,M个桶,平均每个桶[N/M]个数据的桶排序平均时间复杂度为:
O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)
当N=M时,即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。

桶排序的实现

桶排序应用范围比较窄,他的具体设计与应用场景是息息相关的,实现高效实用的桶排序,需要对输入数据的分布有清晰的了解.

针对场景一,参考6中有一个具体的实现:

#include<iostream.h>  
#include<malloc.h>  
  
typedef struct node{  
    int key;  
    struct node * next;  
}KeyNode;  
  
void inc_sort(int keys[],int size,int bucket_size){  
    KeyNode **bucket_table=(KeyNode **)malloc(bucket_size*sizeof(KeyNode *));  
    for(int i=0;i<bucket_size;i++){  
        bucket_table[i]=(KeyNode *)malloc(sizeof(KeyNode));  
        bucket_table[i]->key=0; //记录当前桶中的数据量  
        bucket_table[i]->next=NULL;  
    }  
    for(int j=0;j<size;j++){  
        KeyNode *node=(KeyNode *)malloc(sizeof(KeyNode));  
        node->key=keys[j];  
        node->next=NULL;  
        //映射函数计算桶号  
        int index=keys[j]/10;  
        //初始化P成为桶中数据链表的头指针  
        KeyNode *p=bucket_table[index];  
        //该桶中还没有数据  
        if(p->key==0){  
            bucket_table[index]->next=node;  
            (bucket_table[index]->key)++;  
        }else{  
            //链表结构的插入排序  
            while(p->next!=NULL&&p->next->key<=node->key)  
                p=p->next;     
            node->next=p->next;  
            p->next=node;  
            (bucket_table[index]->key)++;  
        }  
    }  
    //打印结果  
    for(int b=0;b<bucket_size;b++)  
        for(KeyNode *k=bucket_table[b]->next; k!=NULL; k=k->next)  
            cout<<k->key<<" ";  
    cout<<endl;  
}  
  
void main(){  
    int raw[]={49,38,65,97,76,13,27,49};     
    int size=sizeof(raw)/sizeof(int);     
    inc_sort(raw,size,10);  
}  

参考资料