最简单的排序--桶排序

谁践踏了优雅 2022-09-25 02:26 159阅读 0赞

期末考试完了老师要将同学们的分数按照从高到低排序。班上只有5个同学，这5个同学分别考了5分、3分、5分、2分和8分，哎，考得真是惨不忍睹（满分是10分）。接下来将分数进行从大到小排序，排序后是8 5 5 3 2。你有没有什么好方法编写一段程序，这里我们用桶排序来实现：

我们这里只需借助一个一维数组就可以解决这个问题。

首先我们需要申请一个大小为11的数组int a\[11\]。OK，现在你已经有了11个变量，编号从a\[0\]~a\[10\]。刚开始的时候，我们将a\[0\]~a\[10\]都初始化为0，表示这些分数还都没有人得过。例如a\[0\]等于0就表示目前还没有人得过0分，同理a\[1\]等于0就表示目前还没有人得过1分……a\[10\]等于0就表示目前还没有人得过10分。

[![wKioL1OJayyhsaIJAAA2jLLcmR4805.jpg][]][wKioL1OJayyhsaIJAAA2jLLcmR4805.jpg]

下面开始处理每一个人的分数，第一个人的分数是5分，我们就将相对应的a\[5\]的值在原来的基础增加1，即将a\[5\]的值从0改为1，表示5分出现过了一次。

[![wKiom1OJa2KywW-QAAAlFKy8AJ4133.jpg][]][wKiom1OJa2KywW-QAAAlFKy8AJ4133.jpg]

第二个人的分数是3分，我们就把相对应的a\[3\]的值在原来的基础上增加1，即将a\[3\]的值从0改为1，表示3分出现过了一次。

[![wKioL1OJa0yxgw6lAAAlERsTOLs758.jpg][]][wKioL1OJa0yxgw6lAAAlERsTOLs758.jpg]

注意啦！第三个人的分数也是5分，所以a\[5\]的值需要在此基础上再增加1，即将a\[5\]的值从1改为2，表示5分出现过了两次。

[![wKiom1OJa4LibX9_AAAlCwmV6EA971.jpg][]][wKiom1OJa4LibX9_AAAlCwmV6EA971.jpg]

按照刚才的方法处理第四个和第五个人的分数。最终结果就是下面这个图啦。

[![wKiom1OJa5qw9TAiAAAnIW_J2Fw389.jpg][]][wKiom1OJa5qw9TAiAAAnIW_J2Fw389.jpg]

你发现没有，a\[0\]~a\[10\]中的数值其实就是0分到10分每个分数出现的次数。接下来，我们只需要将出现过的分数打印出来就可以了，出现几次就打印几次，具体如下。

a\[0\]为0，表示“0”没有出现过，不打印。

a\[1\]为0，表示“1”没有出现过，不打印。

a\[2\]为1，表示“2”出现过1次，打印2。

a\[3\]为1，表示“3”出现过1次，打印3。

a\[4\]为0，表示“4”没有出现过，不打印。

a\[5\]为2，表示“5”出现过2次，打印5 5。

a\[6\]为0，表示“6”没有出现过，不打印。

a\[7\]为0，表示“7”没有出现过，不打印。

a\[8\]为1，表示“8”出现过1次，打印8。

a\[9\]为0，表示“9”没有出现过，不打印。

a\[10\]为0，表示“10”没有出现过，不打印。

以SDUT上的一道题为例：

## 数据结构实验之排序三：bucket sort ##

####  ####

##### Time Limit: 100ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

根据人口普查结果，知道目前淄博市大约500万人口，你的任务是帮助人口普查办公室按年龄递增的顺序输出每个年龄有多少人，其中不满1周岁的按0岁计算，1到2周岁的按1岁计算，依次类推，大于等于100岁的老人全部按100岁计算。

## 输入 ##

输入第一行给出一个正整数N(<=5000000)，随后连续给出N个整数表示每个人的年龄，数字间以空格分隔。

## 输出 ##

按年龄递增的顺序输出每个年龄的人口数，人口数为0的不输出，每个年龄占一行，数字间以一个空格分隔，行末不得有多余空格或空行。

## 示例输入 ##

10
    16 71 17 16 18 18 19 18 19 20

## 示例输出 ##

16 2
    17 1
    18 3
    19 2
    20 1
    71 1

## 提示 ##

## 代码如下： ##

#include<cstdio>
    #include<cstring>
    using namespace std;
    
    int age[200];
    int flag[200];
    
    int main()
    {
        int n;
        scanf("%d",&n);
        memset(age,0,sizeof(age));
        memset(flag,0,sizeof(flag));
        for(int i=0;i<n;i++)
        {
            int x;
            scanf("%d",&x);
            if(x>=100)
            {
                x=100;
            }
            age[x]++;
            flag[x]=1;
        }
        for(int i=0;i<200;i++)
        {
            if(flag[i]!=0)
            {
                printf("%d %d\n",i,age[i]);
                flag[i]=0;
            }
        }
        return 0;
    }

[wKioL1OJayyhsaIJAAA2jLLcmR4805.jpg]: /images/20220719/c613448d08f0408eaa9c2d4e109c8304.png
[wKiom1OJa2KywW-QAAAlFKy8AJ4133.jpg]: /images/20220719/200f76186f9f47ab945a55acd5e0d3d9.png
[wKioL1OJa0yxgw6lAAAlERsTOLs758.jpg]: /images/20220719/52df582a7e334349abf1fc30b1cbc658.png
[wKiom1OJa4LibX9_AAAlCwmV6EA971.jpg]: /images/20220719/002c6df03db34b03bf760c597defef9f.png
[wKiom1OJa5qw9TAiAAAnIW_J2Fw389.jpg]: /images/20220719/6f566361694e407cba793c563be9b713.png