从今天开始，小猿会不定期的推出有关算法的文章。一方面来巩固自己的学习，另一方面也想和广大的读者一起交流，共同学习算法~

首先，小猿准备从基础的排序算法开始。

生活中，细心的你会发现到处都是被排序过的东西。考试的名次需要按分数排序，站队按身高的高矮排序，电脑上的文档按最后修改过的时间排序····总之，排序是到处可见，无处不在的。下面就举个例子说明一下排序算法中的桶排序。

考试成绩出来了，老师要对参加考试的5名学生的考试成绩进行从高到低排序。分数分别为9分，5分，3分，2分，7分。小明为老师写了一个C小程序，输出了排序后的成绩。不多说，上代码：

代码

#include <stdio.h>
int main()
{
    int score[11]; //定义存分数的数组 
    int i,j,k;
    for(i=0;i<=10;i++)
    score[i]=0; //数组初始化为0 
    for(i=1;i<=5;i++) //循环读入5个分数
    {
        scanf("%d",&k); //每个分数赋值给k
        score[k]++; //进行计数
    }
    for(i=0;i<=10;i++)
        for(j=1;j<=score[i];j++)
            printf("%d ",i);
    return 0;
}

分析一下代码：

这里借助了一维数组score[11]来存放五位同学的分数，先都初始化为0.score[0]代表目前没有人分数为0分，同理score[1],score[2],……都没有人得了零分。

下面依次输入五个人的分数，比如第一个人9分，那么score[k]++; 就表示对应的score[9]的值增加了1，score[9]从0变为1，表示9分出现了一次。（如果.score[9]=2表示9分有两个）同理，第二个是5分，score[5]变为1，以此类推···最后，score[9] .score[5] .score[3] .score[2] .score[7] .score[4]都是1.也就是每个分数出现了一次。接下来，我们只需要打印出出现过的分数就可以了，分数出现几次就打印几次。

score[0]=0，表示0分没有出现过，不打印

···

score[2]=1,2分出现过1次，打印1次

···

score[9] =1,9分出现过1次，打印1次

最后打印结果如图：

怎么样，是不是既简单又好玩呢，快去自己也写写吧~

然而这只是入门级别的桶排序，下面上升一点难度，介绍一下真正的桶排序。

桶排序的步骤：

1.设置一个定量的数组当作空桶子。

2.寻访序列，并且把项目一个一个放到对应的桶子去。

3.对每个不是空的桶子进行排序。

4.从不是空的桶子里把项目再放回原来的序列中。

算法代码：

桶排序代价分析

桶排序利用函数的映射关系，对于N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为：

O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)

当N=M时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。

总结： 桶排序的平均时间复杂度为的O(N+C)，其中C=N*(logN-logM)。如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达O(N)。 当然桶排序的空间复杂度为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。此外，桶排序是稳定的。

以上就是小猿向大家介绍的第一个排序算法-桶排序。对于排序算法还有很多，比如快速排序，冒泡排序，堆排序，希尔排序，归并排序等等。剩下的排序算法，接下来小猿会挑重点的几个来介绍给大家，和大家一起学习。

学习算法，需要不断地思考和大量的练习。日积月累，你就会熟练的掌握和运用算法，还等什么，一起跟着小猿来开启算法的学习之旅吧~

ps:小猿学习算法时间也不长，有写的不好的地方还请大佬们多多指出，还请大家多多关注小猿，支持小猿，谢谢大佬们~ 嘻嘻٩(๑❛ᴗ❛๑)۶

比心٩(๑>◡<๑)۶

笔芯~