c语言排序之桶排序

青旅半醒 2022-06-01 03:35 151阅读 0赞

桶排序 (Bucket sort)或所谓的箱排序，是一个[排序算法][Link 1]，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的[排序算法][Link 1]或是以递归方式继续使用桶排序进行排序）。桶排序是[鸽巢排序][Link 2]的一种[归纳][Link 3]结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（[Θ][Link 4]（n））。但桶排序并不是 比较排序，他不受到 O(n log n) [下限][Link 5]的影响。

假定：输入是由一个随机过程产生的\[0, 1)区间上均匀分布的实数。将区间\[0, 1)划分为n个大小相等的子区间（桶），每桶大小1/n：\[0, 1/n)， \[1/n, 2/n)， \[2/n, 3/n)，…，\[k/n, (k+1)/n )，…将n个输入[元素分配][Link 6]到这些桶中，对桶中元素进行排序，然后依次连接桶输入0 ≤A\[1..n\] <1辅助[数组][Link 7]B\[0..n-1\]是一[指针数组][Link 8]，指向桶（[链表][Link 9]）

桶排序算法要求，数据的长度必须完全一样，程序过程要产生长度相同的数据，使用下面的方法：Data=rand()/10000+10000上面提到的，每次下一次的扫描顺序是按照上次扫描的结果来的，所以设计上提供相同的两个桶数据结构。前一个保存每一次扫描的结果供下次调用，另外一个临时拷贝前一次扫描的结果提供给前一个调用。

数据结构设计：链表可以采用很多种方式实现，通常的方法是动态申请内存建立结点，但是针对这个算法，桶里面的链表结果每次扫描后都不同，就有很多链表的分离和重建。如果使用动态分配内存，则由于指针的使用，安全性低。所以，笔者设计时使用了数组来模拟链表（当然牺牲了部分的空间，但是操作却是简单了很多，稳定性也大大提高了）。共十个桶，所以建立一个二维数组，行向量的下标0—9代表了10个桶，每个行形成的一维数组则是桶的空间。

平均情况下桶排序以线性时间运行。像基数排序一样，桶排序也对输入作了某种假设， 因而运行得很快。具 体来说，基数排序假设输入是由一个小范围内的整数构成，而桶排序则 假设输入由一个随机过程产生，该过程将元素一致地分布在区间\[0，1)上。 桶排序的思想就是把区间\[0，1)划分成n个相同大小的子区间，或称桶，然后将n个输入数分布到各个桶中去。因为输入数均匀分布在\[0，1)上，所以一般不会有很多数落在一个桶中的情况。为得到结果，先对各个桶中的数进行排序，然后按次序把各桶中的元素列出来即可。

代码：

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<stdlib.h>
    #include<math.h>
    #define max(a,b)a>b?a:b
    #define min(a,b)a>b?b:a
    using namespace std;
    int main()
    {
        int test;
        scanf("%d",&test);
        while(test--)
        {
            int n,i,j=0,t;
            int b[10001];
            scanf("%d",&n);//输入想要排序的数的个数
            memset(b,0,sizeof(b));//对b数组初始化
            for(i=1; i<=n; i++)
            {
                scanf("%d",&t);//输入要排序的数
                b[t]++;//将某个数出现的次数记录下来例如输入1，1将被存入b[1]这个数组中
            }
            for(i=0; i<10001; i++)//从b[0]开始输出
            {
                for(j=1; j<=b[i]; j++)//输出该数的个数
                    printf("%d ",i);
            }
    
        }
        return 0;
    }

[Link 1]: https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95
[Link 2]: https://baike.baidu.com/item/%E9%B8%BD%E5%B7%A2%E6%8E%92%E5%BA%8F
[Link 3]: https://baike.baidu.com/item/%E5%BD%92%E7%BA%B3
[Link 4]: https://baike.baidu.com/item/%CE%98
[Link 5]: https://baike.baidu.com/item/%E4%B8%8B%E9%99%90
[Link 6]: https://baike.baidu.com/item/%E5%85%83%E7%B4%A0%E5%88%86%E9%85%8D
[Link 7]: https://baike.baidu.com/item/%E6%95%B0%E7%BB%84
[Link 8]: https://baike.baidu.com/item/%E6%8C%87%E9%92%88%E6%95%B0%E7%BB%84
[Link 9]: https://baike.baidu.com/item/%E9%93%BE%E8%A1%A8