【排序】1.1简单桶排序

最新推荐文章于 2024-06-21 18:55:16 发布

书中自有姚柯璐

最新推荐文章于 2024-06-21 18:55:16 发布

阅读量446

点赞数

分类专栏：姚姚的数据结构算法实现

本文链接：https://blog.csdn.net/YAwDeep/article/details/78480894

版权

姚姚的数据结构算法实现专栏收录该内容

5 篇文章

订阅专栏

博客介绍了简单桶排序算法的应用，通过两个实例展示了如何利用该算法对分数进行排序。在第一个例子中，对5个学生的分数进行了从大到小的排序。在第二个更复杂的例子中，使用更大的数据范围进行排序，说明了桶排序的时间复杂度为O(M+N)，适用于特定场景。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

简单的“桶排序”：书中介绍的桶排序是借助一维数组解决问题。将数组下标作为已经排序的序列，将值存入数组中对应的位置，达到排序的目的。
题目一：5个同学分别考了5分、3分、5分、2分、8分，满分为10分；让计算机随机读入这5个数，按照分数从大到小输出。
输出结果：8 5 5 3 2
解：
思路：1.初始化大小为11的数组a[0]-a[10]；
   2.分数对于数组下标，存在则+1，代表出现的次数，比如，若5分，a[5]=1；
   3.顺序输出，数组中值表示输出次数。
实现（C）：

#include<stdio.h>
int main()
{
    int a[11],i,j,x;
    for(i=0;i<=10;i++)
    {
        a[i]=0;
    }

    for(i=0;i<5;i++)
    {
        scanf("%d",&x);
        a[x]++;
    }

    for(i=10;i>=0;i--)
    {
        for(j=1;j<=a[i];j++)
        {
            printf("%d",i);
        }
    }

    getchar();getchar();
    return 0;

}

题目二：若对0-1000范围内的整数进行排序呢？

解：

思路：如上题，需要大小为1001的数组，1001个桶，来表示0-1000之间每个数出现的次数。

实现（C）：

#include<stdio.h>

int main()
{
    int a[1001],i,j,x,n;

    for(i=0;i<=1000;i++)
    {
        a[i]=0;
    }

    scanf("%d",&n);

    for(i=0;i<n;i++)
    {
        scanf("%d",&x);
        a[x]++;
    }

    for(i=0;i<=1000;i++)
    {
        for(j=1;j<=a[i];j++)
        {
            printf("%d ",i);
        }
    }
    return 0;
}

时间复杂度（如题二）：

第一个循环执行m次（m为桶的个数），第二个循环执行n次（n为待排序数的个数）,第三、四个循环共执行m+n次，共2*（m+n）次；

表示为O(2*(m+n))，忽略掉较小的常数，时间复杂度表示为O(M+N)。

总结：简化版的桶排序，速度非常快，但有局限性。