桶排序

 

>:  桶排序不是基于比较的排序，最好的时间复杂度可以达到O(n)，例如：9个数 10,20,30,40,50,60,70,80,90( 这些数字的顺序是任意的，任意多乱！ )，给9个桶，那么每个元素都进一个桶，且桶内无需排序(因为只有一个元素)，所以进桶后，在一次出来就可以了，就是线性的！原因就是因为桶排序并不是基于比较排序的，比较排序的限制最好的其情况是

O(nlgn)。

 

>: 思想：很像分治( 我说的仅仅是划为小块的部分的思想 ，都是这种大化小)，对于海量数据而言，特别是当内存一次装不下的时候，桶排序是很有效的~

 即：把[ a, b ]划分为n个大小相同的子区间，每一子区间是一个桶。然后将n个记录分配到各个桶中。因为关键字序列是均匀分布在[ n, m ]上的，所以一般不会有很多个记录落入同一个桶中。由于同一桶中的记录其关键字不尽相同，所以必须采用关键字比较的排序方法(通常用插入排序)对各个桶进行排 序，然后依次将各非空桶中的记录连接(收集)起来即可。

 

>: 桶排序适用于什么地方？我觉得桶排序虽然很强大，但是用错了地方还是不行的，用错地方其复杂度可以达到O(n^2)：我觉得对于数据量超级大，但是数据的范围确实在一个不是很大的区间内，那么用桶排序是非常有效的！特别是当均匀分布的时候，更高效。例如：考试成绩0--100分，可以分成10个桶，那么使用桶排序统计每个分数段的处理就是很优雅的！呵呵~！

 

基于以上的想法，简单实现一个桶排序的处理：

CODE：（ 仅仅是个演示而已~ ）

// 桶排序一般比较适合：数据量非常大，但数据的范围在一个区间内的情况

//

// 此处仅仅以1-100之间的数来处理，其他的数据类型，需要做相应的修改

// 思想都是一样的！

// 桶内使用有序链表比较法

 

[cpp]  

#include <stdio.h>  

#include <stdlib.h>  

   

typedef struct node  

{  

        intvalue;  

        structnode * next;  

}node, *p_node;  

   

void bucket( node buc[], intelem[], int n )  

{  

        inti = 0;  

        p_nodetmp, t;  

   

        for(i = 0; i < n; i++ )  

        {  

               tmp= &buc[elem[i]/10];        // 选择桶  

               t= ( p_node )malloc( sizeof( node ) );  

               t->value= elem[i];  

               t->next= NULL;  

   

               while(tmp!= NULL )  

               {  

                       if(tmp->next == NULL )  

                       {  

                               t->next= tmp->next;  

                               tmp->next= t;  

                               break;  

                       }  

                       elseif( tmp->next->value > t->value )  

                       {  

                               t->next= tmp->next;  

                               tmp->next= t;  

                               break;  

                       }  

                       else  

                       {  

                               tmp= tmp->next;  

                       }  

               }  

        }  

}  

   

int main()  

{  

        inti, n, *elem;  

        nodebuc[10];          // 我们准备十个桶  

        p_nodetmp;  

         

        while(scanf("%d", &n) != EOF )  

        {  

               elem= ( int * )malloc( sizeof( int ) * n );  

   

               for(i = 0; i < n; i++ )  

               {  

                       scanf("%d",&elem[i]);  

               }  

   

               for(i = 0; i < 10; i++ )      // 初始化桶  

               {                                                     //为了方便起见，数组节点只作为头结点，不存值  

                       buc[i].next= NULL;  

               }  

   

               bucket(buc, elem, n );  

                

               for(i = 0; i < 10; i++ )  

               {  

                       tmp= buc[i].next;  

                       while( tmp )  

                       {   www.zzzyk.com

                               printf("%d", tmp->value);  

                               tmp= tmp->next;  

                       }  

   

补充：软件开发 , C++ ,