桶排序

女爷i 2022-03-20 01:42 221阅读 0赞

如我这几天的风格一样，概念不多说，直接正题：

>:  桶排序不是基于比较的排序，最好的时间复杂度可以达到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之间的数来处理，其他的数据类型，需要做相应的修改

// 思想都是一样的！

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

#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 )
                           {
                                   printf("%d", tmp->value);
                                   tmp= tmp->next;
                           }
                   }
     
                   printf("\n");
     
                   free(elem );
            }
     
            return0;
    }

更多请见：http://www.baike.com/wiki/%E6%A1%B6%E6%8E%92%E5%BA%8F