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

陳凱

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

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

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

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

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

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

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

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

初始字符串：1011001101011110

結(jié)果字符串：0110101010111101

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

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