最簡單的排序算法（續(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，用符號表示。……