OpenJudge

1:桶式排序

总时间限制:
100ms
内存限制:
1024kB
描述

桶式排序从需要进行排序的正整数的一维数组开始,而且有一个整数的二维数组,其中行下标从09,列下标从0n – 1。在这里,n是需要进行排序的数组中元素的数目。二维数组的每行称为一个桶。编写一个程序,读入15个正整数,并按从小到大的顺序排序。桶式排序的算法如下:

  1. 在一维数组内循环,并根据它的个位将每个值安排在桶数组的某行中。例如,97安排在行73安排在行3,而100安排在行0

  2. 在桶数组内循环,并将值复制回到最初的数组。上面的数值在一维数组中的新顺序是100397

  3. 对每个后面的数位(十位、百位、千位等等)重复这个过程,当处理了最大数字的最高位时,就停止这个过程。

在对数组进行第2轮处理时,100安排在行03安排在行0(它仅有一个数位),而97安排在行9。一维数组中值的顺序是100397。在第3轮处理时,100安排在行13安排在行0,而97安排在行0(在3之后)。桶式排序可以确保在处理了最大数字的最高位之后正确排列所有值的顺序。

注意,桶的二维数组的大小是要排序的整数数组大小的10倍。这种排序方法的性能比冒泡排序方法要高,但需要更多的存储空间。冒泡排序仅仅需要为要排序的数据类型准备另外的内存位置,而桶式排序则要兼顾空间和时间。桶式排序使用更多的内存,但性能更好。

输入
15个正整数
输出
每次分派收集之后得到的一维数组,每个整数之间以空格隔开。每次输出占一行。
样例输入
6634 9796 435 1405 6123 10001 11459 12018 10372 19874 12860 11326 7096 30205 27010
样例输出
12860 27010 10001 10372 6123 6634 19874 435 1405 30205 9796 11326 7096 12018 11459 
10001 1405 30205 27010 12018 6123 11326 6634 435 11459 12860 10372 19874 9796 7096 
10001 27010 12018 7096 6123 30205 11326 10372 1405 435 11459 6634 9796 12860 19874 
10001 30205 10372 435 11326 1405 11459 12018 12860 6123 6634 27010 7096 9796 19874 
435 1405 6123 6634 7096 9796 10001 10372 11326 11459 12018 12860 19874 27010 30205 
提示
伪代码:
读入需要排序的15个正整数
求出其中的最大数,然后求出最大数的位数m
for (n = 1; n <= m; n++)
{
按第n位数的值分派一维数组中的元素到二维数组中
收集二维数组中的有效元素到一维数组中
按题目要求,输出当前的一维数组
}
来源
重庆科技学院 WJQ
全局题号
16437
添加于
2017-11-27
提交次数
85
尝试人数
52
通过人数
48