算法1 - 桶排序算法

桶排序算法是一种最快最简单的排序方法。

算法说明

举例说明：
例如当前有一个一维数组有几个数字例如（1-10）之间，我们如何才能最快速的将其从小到大排序呢？
简单的做法就是，初始化一个一维数组 a[11] 为 0 。 代表所有的数组都没有出现过。遍历随机数字，例如出现5 ，就改变 a[5] = 1,再次出现5那么a[5]=2，同理出现6，那么a[6]=1。

算法代码

void bucket_sort() {
    int a[11],i,j,t;
    
    for (i=0; i<11; i++) {
        a[i] = 0; // 初始化
    }
    
    printf("请输入数字\n");
    for (i=1; i<=5; i++) { // 循环读入5个数字
        scanf("%d",&t); // 把每一个数读入到变量t中
        a[t]++; // 进行计数
    }
    
    for (i=0; i<=10; i++) {
        for (j=1; j<=a[i]; j++) {
            printf("%d",i);
        }
    }
}

这种算法就好比我们这里有11个桶，编号从0-10开始。每出现一个数字，我们聚在对应编号的桶中做一个标志，最后我们只需要数数每个桶中间出现的标志就行。例如3号桶中有一个标志表示2出现了一次。

桶排序-01

算法时间复杂度

代码中第4行的循环一共循环了m次（m为桶的个数），
第9行的循环一种循环了n次（n为待排序的个数），
第14，15行一共循环了m+n次。
所以整个排序算法一共执行了 m+n+m+n 次。
该时间复杂度就是O(m+n+m+n) = O(2*(m+n))，我们在讲时间复杂度的时候可以忽略较小的常数，最终桶排序的时间复杂度为O(m+n)。
即 桶排序的时间复杂度 O(M+N) 。