最简单的排序算法（续）.doc

最简单的排序算法（续）.doc最简单的排序算法(续) 预设在记事本中有很多全部由 0和1 组成的字符串,可以进行如下步骤: 搜索字符串中所有的“ 10”, 并将“ 10”替换成“ 01”, 反复执行此过程。那么,在若干次替换后,字符串中所有的“1”都会跑到字符串的右边,而“0”都会跑到字符串的左边。上一期文章提到,如果有一个二维的由 0和1 组成的字符串阵列, 那么只要不停地执行全部替换, 就可以实现给数据排序的功能。例如,可以把“5,4,8,1,2,3,6,4”――即纵列的“1”的个数, 排序成为“1,2,3,4,4,5,6,8”。这种排序方法被称为珠排序(如图 1)。虽然实现原理很简单, 但毕竟还是用到了记事本这个软件。实际上根据珠排序的原理, 自己 DIY 一台专门用来进行数据排序的计算机也是很容易的, 使用到的设备, 仅仅是几个逻辑门电路和移位寄存器。如果手头没有门电路的元件, 那么用逻辑门电路模拟器也能实现设计, 笔者使用的是 Logisim ,可从网上免费下载到。需要解决的关键问题是如何利用逻辑门,搜索出字符串中所有的“ 10”, 使之变成“ 01”。在一个字符串中搜索数据, 首先, 需要取出字符串中第一个和第二个数字, 把数字输入到变量中; 其次, 匹配两个变量的值是否是“1”和“0”, 若是则把两个变量的值重置为“0”和“1”, 若不是则不用重置;再次,继续取出后续的数字进行匹配。如此多的步骤,实现起来似乎相当复杂,但实际上,只需要四个逻辑门,就可以完成任务。这个装备需要用到与门和异或门两种逻辑门, 与门的作用是当两个输入端均为 1 的时候,则输出为 1 ,否则输出为 0 ,用符号表示。异或门的作用是当两个输入端输入的值不相等时,输出为 1 ,若两个输入端输入的值相等,则输出为 0 ,用符号表示。电路有三个输入端, 一个输出端, 用一个实际的例子能够更好地说明这个逻辑电路的作用( 如下页图 2)。假设初始值是“ 101 ”, 首先, 第一个初始数值“1”和第二个初始数值“0”进行逻辑门的与操作, 得到中间结果A是“0”; 其次, 第二个初始数值“0”和第三个初始数值“1”进行逻辑门的与操作,得到的中间结果 B是“0”;再次,第一个初始数值“1”和中间结果 A即“0”作异或操作,得到的中间结果 C是“1”;最后,中间结果 C“1”和中间结果 B“0”作异或操作,得到的结果是“1”。于是输入初始值“ 101 ”,得到结果为 1。不妨再来一个例子, 假设初始值是“ 011 ”, 首先, 第一个初始数值“0”和第二个初始数值“1”进行逻辑门的与操作,得到中间结果 A是“0”; 其次, 第二个初始数值“1”和第三个初始数值“1”进行逻辑门的与操作, 得到的中间结果 B是“1”;再次,第一个初始数值“0”和中间结果 A即“0”作异或操作,得到的中间结果 C是“0”;最后,中间结果 C“0”和中间结果 B“1”作异或操作, 得到的结果是“1”。于是输入初始值是“ 011 ”, 得到结果为“1”。大家也许会说, 在这里可一点也看不出“1”和“0”对调位置的效果。别着急,想象一下,如果对字符串“ 101 ”作“将 10 变为 01”的替换,那么这个字符串会变成“ 011 ”, 中间那个数字是“1”。如果对字符串“ 011 ”作替换, 那么这个字符串仍然是“ 011 ”, 中间那个数