#include <vld.h>
#include <queue>
#include <iostream>
#include <iomanip>
#include "_CRandom.h"
using namespace std ;
/*
* 描 述:在早期计算中,常用排序机来对一组穿孔卡片排序。即排序机上有十个箱子,把数放入,排序后拿出
* 假定卡片上的数为两位整数,范围为00~99。
* 排序机有十个箱子,编号0~9。排序机处理卡片两遍,第1遍处理个位数,第2遍处理十位数。
* 比如编号1里面放十位数为1的,编号2里放十位数为2的。然后取卡片通过排序机时掉入相应的箱子里。
* 这种方法称为基数排序。
* 步骤 :按个位分到箱子,拿出,按十位分到箱子,拿出,输出结果
* 摘 要:穿孔卡片派序
* 作 者:
* 完成日期:
*/
enum DigitKind{ones, tens};
void Collect(queue<int> digitQueue[], int L[]);
void Distribute(int L[], queue<int> digitQueue[], int n, DigitKind kind);
int main()
{
int i=0;
int L[50];
_CRandom _rand;
queue<int> digitQueue[10];
srand( (unsigned)time( NULL ) );
for(i=0; i<50; i++)
{
L[i]=_rand.getINT(100);
}
//打印随机数
cout<<"排序前: "<<endl;
for(i=0; i<50; i++)
{
cout<<setw(4)<<L[i];
if( (i+1)%10==0)
{
cout<<endl;
}
}
Distribute(L, digitQueue, 50, ones);
Collect(digitQueue, L);
Distribute(L, digitQueue, 50, tens);
Collect(digitQueue, L);
cout<<endl<<endl<<endl;
cout<<"排序后: "<<endl;
for(i=0; i<50; i++)
{
cout<<setw(4)<<L[i];
if( (i+1)%10==0)
{
cout<<endl;
}
}
return 0;
}
void Distribute(int L[], queue<int> digitQueue[], int n, DigitKind kind)
{
int i;
for(i = 0; i<n; i++)
{
//个位
if(kind == ones)
{
digitQueue[L[i] % 10].push(L[i]);
}
//十位
else
{
digitQueue[L[i]/10].push(L[i]);
}
}
}
void Collect(queue<int> digitQueue[], int L[])
{
int i=0, digit=0;
for(digit=0; digit<10; digit++)
{
while( !digitQueue[digit].empty())
{
L[i++] = digitQueue[digit].front();
digitQueue[digit].pop();
}
}
}
/*
排序前:
53 24 27 25 18 21 52 39 75 42
4 57 54 57 70 9 73 36 91 45
23 89 47 81 80 38 14 95 95 40
51 49 19 35 5 26 57 13 33 68
13 18 71 2 71 85 36 78 14 28
排序后:
2 4 5 9 13 13 14 14 18 18
19 21 23 24 25 26 27 28 33 35
36 36 38 39 40 42 45 47 49 51
52 53 54 57 57 57 68 70 71 71
73 75 78 80 81 85 89 91 95 95
Press any key to continue
*/
图法:
比如数
31,46,85,15,92,35,91,22
队列有10个,0~9,按个位放入数据
0 1 2 3 4 5 6 7 8 9
31 92 85 46
91 22 15
35
按队列读出得
31 91 92 22 85 15 35 46
按十位放入
0 1 2 3 4 5 6 7 8 9
15 22 31 46 85 91
35 92
读出
15 22 31 35 46 85 91 92
算法复杂度
复杂度为O(2N)。扩展到对m位的n个数排序,复杂度为O(mn).但是在空间上消耗很大,至少要10个队列。队列中需要有front,rear指针,计数器,数组,对内存管理等等。如果数据量和位数增大,mn所需要的性能更大,
还有个问题,比如遇上负数可能还要另外开个队列来进行维护等等。。。
分享到:
相关推荐
非常好的文档,把进程讲得很形象,非常好理解。可以帮助我们去理解进程,线程等比较容易混淆的概念。
能简单计算穿孔板穿孔率计算
通过大量的分类、 比较和表格绘制的机器运行数百万穿孔卡片来进行数据的处理,其运行结果在纸上打印 出来或者制成新的穿孔卡片。而数据管理就是对所有这些穿孔卡片进行物理的储存和处 理。然而,1 9 5 1 年雷明顿...
穿孔字排版软件
穿孔速度与穿孔针直径对铝材挤压过程的讨论,史艳国,李敏,穿孔速度与穿孔针直径是穿孔过程中很重要的两个参数,他们对挤压成品、穿孔力、模具寿命和生产效率等有直接影响。本文采用七种挤
第1章操作系统概述 1.1操作系统的概念、特征、功能和提供的服务 1.1.1操作系统的概念 操作系统是计算机系统中最重要、最基本的系统软件,操作系统位于硬件和用户程序之间。一方面,它能向用户提供使用计算机的...
微穿孔板吸声系数仿真代码。微穿孔板(Micro-perforated panel,MPP)吸声体由我国著名声学专家马大猷教授于1975年提出,并建立了相关理论模型,称为马氏理论模型。
消化道穿孔临床路径.doc
以矿用对旋轴流局部通风机为研究对象,对风机叶片部分做了穿孔设计,建立了叶片穿孔前后风机的整体模型,在Fluent中进行了稳态模拟、非稳态模拟、噪声预估。结果证明,叶片穿孔能有效抑制叶顶泄流及叶片非工作面涡流产生...
异物性食管穿孔感染护理.doc
通过对矿山常用穿孔设备对比,分别对设备动力、成本和工作效率进行分析,综合现有穿孔设备的优缺点,对技术成熟的牙轮钻机和潜孔钻机做以简要叙述,为矿山选择穿孔设备提供参考数据。
通过大量的 分类、比较和表格绘制的机器运行数百 万穿孔卡片来进行数据的处理,其运行 结果在纸上打印出来或者制成新的穿孔 卡片。而数据管理就是对所有这些穿孔 卡片进行物理的储存和处理。 然而,1 9 5 1 年雷明顿...
CSS3模糊背景穿孔动画特效是一款模糊背景透明遮罩效果,局部区域高亮显示动画特效,适合做大气的引导页代码。
以哈尔乌素露天煤矿穿孔作业环节为研究对象,对穿孔作业过程中存在的危险源及事故类型,从人、机、环、管四大管理对象进行了分析,提出了以危险源识别为核心的安全管控标准与措施。
体内电穿孔法转基因技术的应用,巨兴达,俞华莉,体内电穿孔法进行转基因是将外源基因通过电场作用活体导入动物目标组织或器官细胞中的技术,它已经成为在医学和生命科学领域上逐
有限元法分析比较穿孔板和正三棱柱吸声体,龙万峰,赵菲菲,本文利用有限元法分别对穿孔板和正三棱柱进行模态分析。在分析过程中,同时改变穿孔板和正三棱柱的板厚、穿孔直径、穿孔率和材料
微穿孔板消声器结构参数优化研究
matlab开发-软决策维特比编码与穿孔。使用Simulink(R)在awgn信道上进行软decison-viterbi解码。
YPF穿孔电流变送器 样本册pdf,YPF穿孔电流变送器 样本册
经皮给药电穿孔仪的研制,王文强,宋永磊,本文给出了一种经皮给药电穿孔仪的新的设计方法.本仪器利用电容充放电产生高压脉冲,通过单片机控制脉冲的宽度、幅值以及脉冲率�