珠排序

珠排序是一種自然排序演算法，由 Joshua J . Arulanandham、Cristian S . Calude 和 Michael J . Dinneen 佇二空空二年發展來的，並且佇歐洲理論電腦協會（簡稱 EATCS）的新聞簡報上發表矣這个演算法。無論是電子抑是實物的實現，珠排序攏會當佇 O ( n ) 時間內完成；毋過，該演算法佇電子上的實現明顯比實物愛慢慢真濟，並且只會當提供對正整數序列進行排序。並且，就算講佇上好的狀況，該演算法嘛需要 O ( n 二 ) 的空間。

伊算法概述

佇珠排序當中，一列（row）表示一个數字。若一列里有二粒珠仔，該行代表數字二；若是一列里有四粒珠仔，該行代表數字四。當予定一个陣列，陣列里有偌濟字，就愛有偌濟行；陣列里上大的數字是幾，著愛攢偌濟支杆仔。

準備好勢了後，釋放珠仔，珠仔照重力下落，就完成矣排序。

珠排序會當類似珠仔佇平行的徛予直杆仔頂懸滑動，若像盤仔仝款。毋過，每一條直杆攏有珠仔數目的限制。所以，初初化就誠倚佇徛直的杆仔頂懸掛珠仔，佇第一步內底，排列就予人顯示 n=五行的珠仔佇咧 m=四列隊徛予直杆頂懸。每一列正爿的數字意味對該行佇咧問題中被表示的數；第一，二行表示正整數三（因為𪜶攏有三个珠仔）若頂層的一列表示正整數二（因為伊干焦有含兩个珠仔）。

咱若欲允准珠仔落落來，遐爾仔逐行表示已經排序的整數。第一行表示佇咧集合中上大的數，啊若第 n 行表示上細的數。若照頭前講著的規則（行包含一系列佇徛直杆一到 k 的珠仔，並且予 k + 一到 m 徛予直杆攏空）， 就是伊會出現這款狀況。

允准珠仔落落的行為佇物理意義頂頭就是允准珠仔對懸懸的行落落到低的行。若予人行 a 表示的值得小於被行 a + 一表示的值，遐爾一寡珠仔就會對 a + 落落來到地 a；因為行 a 無包含有夠珠仔防止珠對 a + 落一行，所以這一定會發生。

用機械裝置實現的珠排序類似於計數排序；每一箠頂頭的數字佮遐的佇咧所有數中等於抑是大於這个數字的數量比起來。

複雜度

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

• _ O _ ( 一 )：即所有的珠仔攏做伙振動，但是這種演算法只是概念的，無法度佇咧電腦中實現。
• _ O _ ( $ { \ sqrt { n } } $ )：佇真實的物理世界內底用引力實現，所需要時間當比珠仔上大懸度的平方根，上大懸度比 n。
• _ O _ ( n )：一擺徙一擺珠仔，會當用類比和數字的硬體實現。
• _ O _ ( S )，S 是所有輸入資料的佮：一擺徙一个珠仔呢，會當佇軟體中實現。

外部連結

• The Bead Sort paperPDF  ( 一百十四  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