【NOIP试题】桶排序(做题感悟)-少儿编程教育网

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

桶排序特点:

  1. 桶排序是稳定的
  2. 桶排序是常见排序里最快的一种,比快排还要快…大多数情况下
  3. 桶排序非常快,但是同时也非常耗空间,基本上是最耗空间的一种排序算法

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

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

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

下面举例子来讲吧:Codevs1487 大批整数排序

【题目描述】

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,是几就输出几。

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