关于桶排序的文章，我几乎是没有见过。见过也看不懂===所以只好学会以后自己写一个了。

桶排序特点：

1,桶排序是稳定的

2,桶排序是常见排序里最快的一种,比快排还要快…大多数情况下

3,桶排序非常快,但是同时也非常耗空间,基本上是最耗空间的一种排序算法

桶排序与其他排序的比较：

基数排序，与选择，冒泡，插入排序不同的是，前者都属于【比较性】排序，而基数排序是【分配式】排序，所以他又称”桶排“；

桶排，顾名思义，就是透过数据的部分资讯，将待排序的元素分配至某些【桶】中，从而达到排序的作用，他属于稳定性的排序。

下面用【栗子】来讲吧：

Codevs1487 大批整数排序

题目描述 Description

！！！CodeVS开发者有话说：

codevs自从换了评测机，新评测机的内存计算机制发生变化

计算内存的时候会包括栈空间 swap空间

这题的2M是单指内存空间。。。

十分十分抱歉

抱歉

！！！

现在有一大批（总数不超过10000000个）1到10之间的整数，现在请你从小到大进行排序输出。

（测试数据将超过11MB。）

输入描述 Input Description

第一行表示将下排序的个数N；

第2行到最后一行，每行一个数，表示有待排序的数（均是1-10之间的数，含1和10）

（注：最后有一空行）

输出描述 Output Description

输出N个从小到大排列好的数，每行一个（注：最后有一空行）

样例输入 Sample Input

11
9
10
1
2
3
4
5
6
7
8
9

样例输出 Sample Output

1
2
3
4
5
6
7
8
9
9
10

分析：根据题目不难想起解题方法。肯定是排序之后又是什么排序。我最先想到的是STL的sort。之后试了一下。

出现了这个结果。第二个数据点没有过。之后我重新审了一下题目【现在有一大批（总数不超过10000000个）1到10之间的整数】很明显。SORT承受不了这么多组数。受不了受不了受不了，这日子没发过了啊。怎么办……

之后呢，聪明的古人发明了快速简洁的排序——桶排序（没找到发明人和日期。）

对此题目有了其他解法。（桶排序似乎出现早

#include <cstdio>

#include <iostream>

using namespace std;

int n,a[11],x;

int main()

{

   menset（a，0，sizeof（a））；

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

    {

        scanf("%d",&x);

        a[x]++;

    }

    for(int i=1;i<=10;i++)

    if(a[i]!=0)

    {

        for(int j=1;j<=a[i];j++)

        printf("%d\n",i);

    }

    return 0;

}

首先n为输出N个从小到大排列好的数。之后就进入了核心代码。【1到10之间的整数】这一个条件，就可以得到需要10个【桶】就OK。在学数组的时候学过，需要把数组开大一点。【桶】也要大一点。就开十一个。下面就考虑桶的表示。等等==刚刚说了什么数组？

嗯？数组=桶。

for(int i=1;i<=n;i++)

    {

        scanf("%d",&x);

        a[x]++;

    }

就将其分为11个桶（一个桶备用）。X为1~10的数。也为每输入一个数就判断在哪一个桶里并放入。桶内数量+1.这段代码应该不难理解。看下一段。

for(int i=1;i<=10;i++)

    if(a[i]!=0)

    {

        for(int j=1;j<=a[i];j++)

        printf("%d\n",i);

    }

判断并输出。首先遍历10个桶。之后判断桶内数量是否为0.如果0下一个，如果不是0，是几就输出几。

好哒，桶排就这么简单，下次再见