CMP设计分享 http://blog.sciencenet.cn/u/accsys 没有逆向思维就没有科技原创。 不自信是科技创新的大敌。

博文

专家排序法一种新的排序方法

已有 6594 次阅读 2016-8-8 07:27 |个人分类:机器计算|系统分类:科研笔记| 算法时间复杂度, 专家排序法

一种新的排序方法

     一般说的排序方法有七种,本文介绍一种我想到的计算机专家应该使用的排序方法,就叫“专家排序法”吧。

    在计算机中所有的数都是用无符号的二进制数表示的,因而只要存储空间充分大,每个数都可以做为一个存储地址。这是计算机专家排序法的基础。为使问题简单,实数如何变为无符号二进制整数的过程不赘述(请参阅《自己设计制作CPU与单片机》一书第10章),仅以无符号整数n次输入加以说明。

1. 专家排序法

    下面介绍专家排序法算法:

(1)       初始化一个存储器M1

(2)       输入一个无符号整数;

(3)       比较最大数寄存器max最小数寄存器mini,定值;

(4)       将该数送入指针A

(5)       将该数送入指针A所指存储单元;

(6)       重复(2)~(4)直至输入结束;

(7)       初始化指针B1

(8)       以最小寄存器mini值做起始地址,送入指针A

(9)       A所指M1非空存储单元内容通过指针B送入另外一个存储器M2

(10)   指针A加一、指针B完成传送一次数据后加一;

(11)   判断A>max,是,转(12),否则转(9);

(12)   指针B所指示过M2n个存储单元就是做好排序的数列;

(13)   排序结束。

2. 算法时间复杂度

    专家排序法分为两个过程。

    第一个过程是将输入的无符号整数送入M1存储单元,顺便找出最大值和最小值。显然这是O(n)算法时间复杂度。

    第二个过程是n个数按值大小放在M21n号存储单元。这一过程需要查看max-miniM1的存储单元是否有数,有数传送,无数通过。由于最大和最小值都与n无关,因而是一个常数次查看过程。不妨设K=max-mini。于是知,专家排序法的算法时间复杂度为O(K+n)= O(n)

3. 专家排序法的效率

    不难想到,maxmini之间的数越稠密,专家排序法的效率就越高。最好的情况是n个数填满了maxmini之间的所有整数。反之,当K很大,n相对较小时,效率会较低。为了更快地提高效率,可以对存储器M1的每个存储单元安放一个有无数据的标志,进行第二个过程时,由这些标志线逻辑来控制对M1的访问次数,这样会通过n次访问就能完成按序放数据。目前的计算机还没人设计出这种逻辑电路。我相信,将来一定会有。

    前文(http://blog.sciencenet.cn/blog-340399-993790.html)粗略地提出了专家排序法,有网友匿名提出质疑,此文就算对质疑的完整回答吧。

 

姜咏江

 

2016-8-8

 

 



https://blog.sciencenet.cn/blog-340399-995138.html

上一篇:快速排序去重?计算机专家与程序员的不同
下一篇:过于重视名誉不重视成果的科研氛围难出大成就
收藏 IP: 120.52.24.*| 热度|

1 liudazhe

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-3-29 23:39

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部