珠排序

出自維基百科,自由嘅百科全書
跳去: 定向搵嘢

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

概要[編輯]

先將算珠按數字一列列放好
然後畀啲算珠跌落嚟

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

2 4 1 3 3

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

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

1 2 3 3 4

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

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

複雜度[編輯]

對應唔同嘅做法,珠排序嘅複雜度都有唔同:

做法 複雜度 說明
思想實驗 O(1) 所有算珠同時瞬間移動,嚮現實中係無法實現嘅。
物理機械 O(\sqrt{n}) 喺重力作用下,算珠下跌嘅時間同算珠嘅高度嘅平方根成正比,呢個高度同數列長度n成正比。
電子硬體 O(n) 無論係數碼定係類比型式嘅硬體,啲算珠都係逐行逐行噉搬,所以用嘅時間同n成正比。
電腦軟體 O(S) S係算珠嘅總數(等如數列嘅總和),因為軟體要逐粒珠去搬,所以時間複雜度同S成正比。

改良版[編輯]

電腦軟體式嘅珠排序可以改良,假設數列Ln個非負整數i_j: 1 \le j \le n,先搵出最細嗰個數i_{min},然後將每個數i_j都減i_{min},得到一個新數列L_{opt},以珠排序排列L_{opt},可以將複雜度由O(S)改良為O(S - ni_{min})。最後將L_{opt}還原返做L就搞掂嘞。

呢個版本重可以令珠排序處理到負整數,代價係用多咗時間同空間,因為i_{min}係負數,S - ni_{min} > S

C++嘅實例[編輯]

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


睇埋[編輯]

出面網頁[編輯]