一种新的排序方法

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

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

1. 专家排序法

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

（1）       初始化一个存储器M1；

（2）       输入一个无符号整数；

（3）       比较最大数寄存器max最小数寄存器mini，定值；

（4）       将该数送入指针A；

（5）       将该数送入指针A所指存储单元；

（6）       重复（2）～（4）直至输入结束；

（7）       初始化指针B为1；

（8）       以最小寄存器mini值做起始地址，送入指针A；

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

（10）   指针A加一、指针B完成传送一次数据后加一；

（11）   判断A>max，是，转（12），否则转（9）；

（12）   指针B所指示过M2的n个存储单元就是做好排序的数列；

（13）   排序结束。

2. 算法时间复杂度

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

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

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

3. 专家排序法的效率

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

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

姜咏江

2016-8-8