珠排序

珠排序係一種自然排序演算法，係Joshua J. Arulanandham、Cristian S. Calude、Michael J. Dinneen嚮2002年發明嘅，喺歐洲理論電腦科學協會嘅新聞簡報度發表過。唔理係用數碼定係類比嘅硬體嚟做珠排序，都係用O(n)嘅時間就搞掂，不過，一改用軟體嚟做嘅話就會慢咗好多。呢種方法淨係可以直接用嚮非負整數嘅資料度，如果無特殊處理係排唔到負數、定點小數或者浮點小數嘅。就算嚮最理想嘅情況下，至少都要O(n2)嘅空間。

概要 

珠排序需要一個特製嘅類似算盤噉樣嘅裝置，係實物嘅或者用電腦模擬嘅都得，擧個例，將下面呢五個數由細到大排好：

開始嗰陣要將個裝置打平放，方便好似右上圖一樣將算珠排好，喺最頂嗰列擺兩粒珠代表頭一個數字「2」，喺佢下面嗰列擺四粒珠代表第二個數字「4」，如此類推，直到代表每個數字嘅珠仔都擺好嗮為止，啲珠通常都會全部靠向同一邊咁排嘅。

跟住就將個裝置靠向第一列嘅一邊搦起，等啲珠自己滑落，直到所有算珠嘅下底嗰列都填滿為止，就會好似右下圖噉樣。家陣由最頂嗰列開始睇：

每一列算珠嘅數目正正就等如嗰五個數由細到大排嘅結果。

由於重力嘅作用，下底無承托嘅算珠會向下跌，直到碰到嚮佢下面嗰粒珠或者跌到底嗰列為止。因為大啲嘅數有多啲珠，細啲嘅數就少啲，所以多出嚟嘅珠一定會跌落去，噉就做到越大嘅數越沉底，越細嘅數就越浮面嘅情況。

複雜度 
對應唔同嘅做法，珠排序嘅複雜度都有唔同：

改良版 
電腦軟體式嘅珠排序可以改良，假設數列有個非負整數，先搵出最細嗰個數，然後將每個數都減，得到一個新數列，以珠排序排列，可以將複雜度由O()改良為O()。最後將還原返做就搞掂嘞。

呢個版本重可以令珠排序處理到負整數，代價係用多咗時間同空間，因為係負數，。

C++嘅實例 
呢個例子利用C++嘅標準模板庫裏面嘅「位元集」嚟模擬算珠，係「改良版」，可以排負整數、字元。程式用C++14標準語法嚟寫，編譯嗰陣可能要加選項，例如GNU C++要加「-std=c++14」。

排序演算法
自然演算法

Bead Sort in MGS, a visualization of a bead sort implemented in the MGS programming language
Bead Sort on MathWorld

排序演算法