BeadSort重力排序

最近在看好玩的算法, 重力排序是一个根据重力(Gravity)原理的自动排序, 这个排序是自然排序的一种, 非人为操作便可实现. 这种排序非常适合给小孩子解释排序的原理和自然需求.

上面这个图就是重力排序, 首先找出最大的数, 上图中是4, 然后设为m, 就是有m个pole(杆子), 这图就是4个杆子. 然后横着看, 每个row就是当前数字有几便有几个球. 比如row 1 (ary[0] = 2) 是2, 就是两个珠子.

然后让数字随着重力下落即可排序, 具体证明和复杂度wiki有. https://en.wikipedia.org/wiki/Bead_sort 可以看出这种排序用机械实现还可以, 用算法实现效率并不好.

上面是一个实现, 具体来说, 最难的地方在于如何实现珠子下落

代码首先计算一个pole上有几个珠子, 然后计算有几个空位, 把空位补上珠子,就是下落后的个数.

最后这个算法的弱点是只能sort正整数, 而且如果数字很离散, 那么效率就太低了