珠排序

珠排序（英語：Bead sort）是一種自然排序算法，由約書亞·J·阿魯拉南達姆（Joshua J. Arulanandham）、克里斯蒂安·S·卡魯德和邁克爾·狄寧Michael Dinneen於2002年發展而來，並且在歐洲理論計算機協會（EATCS）的新聞簡報上發表了該算法。無論是電子還是實物上的實現，珠排序都能在 $O(n)$ 時間內完成；然而，該算法在電子上的實現明顯比實物要慢很多，並且只能用於對正整數序列進行排序。並且，即使在最好的情況，該算法也需要 $O(n^{2})$ 的空間。

算法概述

第一步：將珠子懸掛在豎直杆上

第二步：讓珠子掉落

在珠排序中，一行（row）表示一個數字。如果一行里有2顆珠子，該行代表數字2；如果一行里有4顆珠子，該行代表數字4。當給定一個數組，數組裡有多少個數字，就要有多少行；數組裡最大的數字是幾，就要準備多少根杆子。

準備就緒後，釋放珠子，珠子按重力下落，就完成了排序。

珠排序可以類比於珠子在平行的豎直杆上滑動，就像算盤一樣。然而，每一豎直杆都有珠子數目的限制。因此，初始化就相當於在豎直的杆上懸掛珠子，在第一步中，排列就被顯示為n=5行的珠子在m=4列隊豎直杆上。每一行右邊的數字意味着該行在問題中被表示的數；第1，2行表示正整數3（因為它們都有3個珠子）而頂層的一行表示正整數2（因為它只含有2個珠子）。

如果我們要允許珠子掉落，那麼每行表示已排序的整數。第1行表示在集合中最大的數，而第n行表示最小的數。如果按照前面提到的規則（行包含一系列在豎直杆1到k的珠子，並且讓k+1到m豎直杆都空），那麼它會出現這種情況。

允許珠子掉落的行為在物理意義上就是允許珠子從高的行掉落至低的行。如果被行a表示的值小於被行a+1表示的值，那麼一些珠子就會從a+1掉落至a；因為行a不包含足夠的珠子防止珠從a+1行掉落，所以這一定會發生。

用機械裝置實現的珠排序類似於計數排序；每一杆上的數字與那些在所有數中等於或大於該數字的數量相當。

複雜度

珠排序可以是以下複雜度級別：

• O(1)：即所有珠子都同時移動，但這種算法只是概念上的，無法在計算機中實現。
• O(${\sqrt {n}}$)：在真實的物理世界中用引力實現，所需時間正比於珠子最大高度的平方根，而最大高度正比於n。
• O(n)：一次移動一列珠子，可以用模擬和數字的硬件實現。
• O(S)，S是所有輸入數據的和：一次移動一個珠子，能在軟件中實現。

Python 實現

def bead_sort(l):
    b = []
    l_len = len(l) - 1 
    index = 0 
    count = 0 
 
    while(any(l)):
        if l[index] != 0:
            count += 1
            l[index] -= 1
 
        if index == l_len:
            b.append(count)
            index = 0 
            count = 0 
        else:
            index += 1
 
    if count != 0:
        b.append(count)

    result = []
    for i, v in enumerate(b[:-1]):
        if v == b[i+1]:
            continue
        else:
            result.extend([i + 1 for _ in range(v - b[i + 1])])
 
    result.extend([len(b) for _ in range(max(b) - len(result))])
 
    return result

if __name__ == "__main__":
    print(bead_sort([2, 4, 1, 3, 3]))

外部連結

• The Bead Sort paperPDF (114 KiB)
• C# Bead Sort Implementation C# implementation of the Bead Sort Algorithm
• Bead Sort in MGS （頁面存檔備份，存於網際網路檔案館）, a visualization of a bead sort implemented in the MGS programming language
• Bead Sort on MathWorld （頁面存檔備份，存於網際網路檔案館）