桶排序

  桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket so rt)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以 递归方式继续使用桶排序进行排
  人为设置一个BucketSize,作为每个桶所能放置多少个不同数值(例如当BucketSize==5时,该桶可以存放{1,2,3,4,5} 这几种数字,但是容量不限,即可以存放100个3); 遍历输入数据,并且把数据一个一个放到对应的桶里去; 对每个不是空的桶进行排序,可以使用其它排序方法,也可以递归使用桶排序; 从不是空的桶里把排好序的数据拼接起来。 注意,如果递归使用桶排序为各个桶排序,则当桶数量为1时要手动减小BucketSize增加下一循环桶的数量,否则会陷入死循环,导致内存溢出。;

动图演示

桶排序1 桶排序2

C代码

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int key;
    struct node *next;
}KeyNode;

void bucket_sort(int keys[],int size,int bucket_size) {
    int i,j;
    KeyNode **bucket_table = (KeyNode **)malloc(bucket_size * sizeof(KeyNode*));
    for(i = 0;i < bucket_size;i++) {
        bucket_table[i] = (KeyNode*)malloc(sizeof(KeyNode));
        bucket_table[i]->key = 0;
        bucket_table[i]->next = NULL;
    }
    for(j = 0;j < size;j++) {
        KeyNode *node = (KeyNode *)malloc(sizeof(KeyNode));
        node->key = keys[j];
        node->next = NULL;
        int index = keys[j]/10;
        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)++;
        }
    }
    //print result
    KeyNode * k = NULL;
    for(i = 0;i < bucket_size;i++)
        for(k = bucket_table[i]->next;k!=NULL;k=k->next)
            printf("%d ",k->key);
    printf("\n");
}


int main()
{
    int raw[] = {49,38,65,97,76,13,27,49};
    int size = sizeof(raw)/sizeof(int);
    bucket_sort(raw,size,10);

}

分析:

  桶排序最好情况下使用线性时间O(n),桶排序的时间复杂度,取决与对各个桶之间数据进行排序的时间复杂度,因为其它部分的时间复杂度都为O(n)。很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。但相应的空间消耗就会增大。 最佳情况:T(n) = O(n+k) 最差情况:T(n) = O(n+k) 平均情况:T(n) = O(n2)  

Copyright © zs0813.com 2020 all right reserved,powered by Gitbook该文件修订时间: 2020-10-09 10:41:12

results matching ""

    No results matching ""