最简单的排序算法

一提到算法，大部分人的第一反应都是排序。实在是排序算法太经典了，感觉能独占算法的半壁江山。无论是算法课，还是笔试面试，排序算法都是必须掌握的基本内容。而提到算法，绝大多数人，哪怕是研究生毕业的，高学历的人才，最爱的就是“冒泡排序”，为啥啊？简单呗！冒泡排序实在是大名鼎鼎啊，就算我没接触算法和数据结构时，我都如雷贯耳，排序只知“冒泡”而不知其他。但是其实冒泡还不算最简单。现在来说一说最简单的排序：桶排序。

桶排序，一句话概括，就是“一个萝卜一个坑”。假设我们要给一组100以内的数排序，比如3，90，3，9，1，7，34... ...等等吧，瞎写一通，只要在100以内就行。那我们首先得需要100个空“桶”，编号1~100，用来存放它所对应的数的个数。好了，现在这100个空桶已经按照1到100的编号摆好位置了，并且全部初始化为0。接下来开始往里面放东西了。来一个数就把它放到它所对应的的那个编号的桶里。比如来了一个3，就把它放到3号桶里，3号桶就由0变成了1；又来了一个90，就把它放到90号桶里，90号桶由0变成了1；又来了一个3，把它放到3号桶里，3号桶由1变成了2... ...就这样把所有的数都放到桶里。

输出就简单多了，其实把所有数装完，就相当于排好序了。假设要从小到大输出，就从1号桶到100号桶依次把数取出来就行了。

代码如下：

#include <stdio.h>
#include <stdlib.h>

int main()
{
    //freopen("input.txt","r",stdin);
    int a;
    int arr[101];
    memset(arr,0,sizeof(arr));//把arr数组清0
    while(scanf("%d",&a)==1)//来一个数就把它放到桶里。这里注意如果输入不用文件的话，输入结束要按ctrl+z+enter告诉系统输入结束。
        arr[a]++;

    int i,j;
    for(i=1;i<=100;i++)//循环判断arr1到arr100
        for(j=1;j<=arr[i];j++)//每个桶里有几个数就输出几次
            printf("%d ",i);

    return 0;
}

桶排序虽然简单但是有很大的限制。比如本例，只能排1到100的整数，负数和小数排不了。而且十分浪费存储空间。假设我只需要排10个数，但是里面有一个一亿，那就需要申请一亿个空间。但是优点也有，它是速度最快的排序算法，时间复杂度为O(M+N)。其中M表示桶的个数，N表示排序数的个数。