最簡(jiǎn)單的排序算法（續(xù)）

陳凱

預(yù)設(shè)在記事本中有很多全部由0和1組成的字符串，可以進(jìn)行如下步驟：搜索字符串中所有的“10”，并將“10”替換成“01”，反復(fù)執(zhí)行此過程。那么，在若干次替換后，字符串中所有的“1”都會(huì)跑到字符串的右邊，而“0”都會(huì)跑到字符串的左邊。上一期文章提到，如果有一個(gè)二維的由0和1組成的字符串陣列，那么只要不停地執(zhí)行全部替換，就可以實(shí)現(xiàn)給數(shù)據(jù)排序的功能。例如，可以把“5，4，8，1，2，3，6，4”——即縱列的“1”的個(gè)數(shù)，排序成為“1，2，3，4，4，5，6，8”。這種排序方法被稱為珠排序（如圖1）。

雖然實(shí)現(xiàn)原理很簡(jiǎn)單，但畢竟還是用到了記事本這個(gè)軟件。實(shí)際上根據(jù)珠排序的原理，自己DIY一臺(tái)專門用來(lái)進(jìn)行數(shù)據(jù)排序的計(jì)算機(jī)也是很容易的，使用到的設(shè)備，僅僅是幾個(gè)邏輯門電路和移位寄存器。如果手頭沒有門電路的元件，那么用邏輯門電路模擬器也能實(shí)現(xiàn)設(shè)計(jì)，筆者使用的是Logisim，可從網(wǎng)上免費(fèi)下載到。

需要解決的關(guān)鍵問題是如何利用邏輯門，搜索出字符串中所有的“10”，使之變成“01”。在一個(gè)字符串中搜索數(shù)據(jù)，首先，需要取出字符串中第一個(gè)和第二個(gè)數(shù)字，把數(shù)字輸入到變量中；其次，匹配兩個(gè)變量的值是否是“1”和“0”，若是則把兩個(gè)變量的值重置為“0”和“1”，若不是則不用重置；再次，繼續(xù)取出后續(xù)的數(shù)字進(jìn)行匹配。如此多的步驟，實(shí)現(xiàn)起來(lái)似乎相當(dāng)復(fù)雜，但實(shí)際上，只需要四個(gè)邏輯門，就可以完成任務(wù)。

這個(gè)裝備需要用到與門和異或門兩種邏輯門，與門的作用是當(dāng)兩個(gè)輸入端均為1的時(shí)候，則輸出為1，否則輸出為0，用符號(hào)表示。異或門的作用是當(dāng)兩個(gè)輸入端輸入的值不相等時(shí)，輸出為1，若兩個(gè)輸入端輸入的值相等，則輸出為0，用符號(hào)表示。

電路有三個(gè)輸入端，一個(gè)輸出端，用一個(gè)實(shí)際的例子能夠更好地說(shuō)明這個(gè)邏輯電路的作用（如下頁(yè)圖2）。假設(shè)初始值是“101”，首先，第一個(gè)初始數(shù)值“1”和第二個(gè)初始數(shù)值“0”進(jìn)行邏輯門的與操作，得到中間結(jié)果A是“0”；其次，第二個(gè)初始數(shù)值“0”和第三個(gè)初始數(shù)值“1”進(jìn)行邏輯門的與操作，得到的中間結(jié)果B是“0”；再次，第一個(gè)初始數(shù)值“1”和中間結(jié)果A即“0”作異或操作，得到的中間結(jié)果C是“1”；最后，中間結(jié)果C“1”和中間結(jié)果B“0”作異或操作，得到的結(jié)果是“1”。于是輸入初始值“101”，得到結(jié)果為1。

不妨再來(lái)一個(gè)例子，假設(shè)初始值是“011”，首先，第一個(gè)初始數(shù)值“0”和第二個(gè)初始數(shù)值“1”進(jìn)行邏輯門的與操作，得到中間結(jié)果A是“0”；其次，第二個(gè)初始數(shù)值“1”和第三個(gè)初始數(shù)值“1”進(jìn)行邏輯門的與操作，得到的中間結(jié)果B是“1”；再次，第一個(gè)初始數(shù)值“0”和中間結(jié)果A即“0”作異或操作，得到的中間結(jié)果C是“0”；最后，中間結(jié)果C“0”和中間結(jié)果B“1”作異或操作，得到的結(jié)果是“1”。于是輸入初始值是“011”，得到結(jié)果為“1”。

大家也許會(huì)說(shuō)，在這里可一點(diǎn)也看不出“1”和“0”對(duì)調(diào)位置的效果。別著急，想象一下，如果對(duì)字符串“101”作“將10變?yōu)?1”的替換，那么這個(gè)字符串會(huì)變成“011”，中間那個(gè)數(shù)字是“1”。如果對(duì)字符串“011”作替換，那么這個(gè)字符串仍然是“011”，中間那個(gè)數(shù)字仍然是“1”。上面的那個(gè)邏輯電路的作用，就是把三個(gè)數(shù)字作為一組，計(jì)算出搜索和替換后中間那個(gè)數(shù)值的值。

例如，字符串“1011001101011110”，如果我們想要將字符串中的“10”變成“01”，可以先把整個(gè)字符串首尾各補(bǔ)一個(gè)“0”，使其變成“010110011010111100”，則可以把字符串放進(jìn)一個(gè)移位寄存器中（如圖3）。首先，邏輯電路獲得的數(shù)據(jù)是“010”，邏輯運(yùn)算后得到結(jié)果是“0”；接著，移動(dòng)一位，輸入的數(shù)據(jù)是“101”，得到的結(jié)果是“1”；然后，再移動(dòng)一位，輸入數(shù)據(jù)是“011”，得到的結(jié)果仍然是“1”，以此類推。整個(gè)數(shù)據(jù)全部經(jīng)邏輯電路運(yùn)算后，得到的字符串就是“0110101010111101”，把初始字符串和經(jīng)邏輯運(yùn)算后的字符串并列排放，我們就能看出替換的效果了（如圖4）。

初始字符串：1011001101011110

結(jié)果字符串：0110101010111101

既然能夠?qū)σ恍凶址M(jìn)行替換操作，那么對(duì)多行的字符串進(jìn)行替換操作其原理也完全相同。這樣的話，就能很容易打造出一個(gè)實(shí)體的排序計(jì)算機(jī)，所需要的僅僅是兩種邏輯門和若干移位寄存器。

實(shí)際上，科學(xué)家對(duì)這樣的字符串替換模型投入了不少精力，稍加改造就可以使之成為一個(gè)計(jì)算公路暢通程度的模型，因?yàn)椤?0”逐漸變成“01”的過程，和高速公路堵車時(shí)發(fā)生的狀況很類似。另外，還可以將這個(gè)模型當(dāng)成一個(gè)循環(huán)元胞自動(dòng)機(jī)來(lái)使用。僅僅是對(duì)調(diào)字符串中數(shù)值的位置，就可以引出如此多有趣的研究?jī)?nèi)容，實(shí)在讓人驚嘆，對(duì)此有興趣的朋友可自行深入探索其中更多的奧秘。