珠排序是一種自然排序算法，由Joshua J. Arulanandham, Cristian S. Calude 和 Michael J. Dinneen 在2002年發展而來，並且在歐洲理論計算機協會（European Association for Theoretical Computer Science，簡稱EATCS）的新聞簡報上發表了該算法。
基本介紹
- 中文名：珠排序
- 外文名：Bead Sort
基本信息,算法概述,複雜度,C語言實現,
基本信息
珠排序是一種自然排序算法，由Joshua J. Arulanandham, Cristian S. Calude 和 Michael J. Dinneen 在2002年發展而來，並且在歐洲理論計算機協會（European Association for Theoretical Computer Science，簡稱EATCS）的新聞簡報上發表了該算法。無論是電子還是實物上的實現，珠排序都能在O(n)時間內完成；然而，該算法在電子上的實現明顯比實物要慢很多，並且只能用於對正整數序列進行排序。並且，即使在最好的情況，該算法也需要O(n2) 的空間。
算法概述
珠排序可以類比於珠子在平行的豎直桿上滑動，就像算盤一樣，然而，每一豎直桿都有珠子數目的限制。因此，初始化就相當於在豎直的桿上懸掛珠子，在第一步中，排列就被顯示為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(√n)：在真實的物理世界中用引力實現，所需時間正比於珠子最大高度的平方根，而最大高度正比於n。
O(n)：一次移動一列珠子，可以用模擬和數字的硬體實現。
O(S)，S是所有輸入數據的和：一次移動一個珠子，能在軟體中實現。
C語言實現
void beadSort(int *a, int size)//傳入參數: a:待排序數組,size:數組長度{ int len = getMax(a, size);//獲取待排序數組的最大值 char *bead = (char*)malloc(sizeof(char)*(size*len)); int x, y, k; for (y = 0; y<size; y++)//初始化算盤 { for (x = 0; x<len; x++) { bead[y*len + x] = 0; } } for (y = 0, k = 0; y < size; y++, k++)//掛珠子 { for (x = 0; x < len&&a[k] > 0; x++) { bead[y*len + x] = 1; a[k]--; } } for (y = 1; y<size; y++)//珠子下墜 { for (x = 0; x<len; x++) { int temp = y; while (temp>0 && (bead[temp*len + x] >bead[(temp - 1)*len + x])) { bead[temp*len + x] ^= 1; bead[(temp - 1)*len + x] ^= 1; temp--; } } } for (y = 0, k = size - 1; y < size; y++, k--)//讀取 { for (x = 0; x < len&&bead[y*len + x] != 0; x++) { a[k]++; } } free(bead);}