最簡單的排序算法（續）

陳凱

預設在記事本中有很多全部由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”，中間那個數字仍然是“1”。上面的那個邏輯電路的作用，就是把三個數字作為一組，計算出搜索和替換后中間那個數值的值。

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

初始字符串：1011001101011110

結果字符串：0110101010111101

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

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