珠排序是一种自然排序算法，由Joshua J. Arulanandham、Cristian S. Calude和Michael J. 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()：在真实的物理世界中用引力实现，所需时间正比于珠子最大高度的平方根，而最大高度正比于n。
  • O(n)：一次移动一行珠子，可以用模拟和数字的硬件实现。
  • O(S)，S是所有输入数据的和：一次移动一个珠子，能在软件中实现。

Python 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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]))

原文地址：https://zh.wikipedia.org/wiki/%E7%8F%A0%E6%8E%92%E5%BA%8F

在知识共享 署名-相同方式共享 3.0协议之条款下提供