排序算法 | 珠排序(bead sort)详解与Python实现

点击 机器学习算 法与Python学习 ，选择加星标

精彩内容不迷路

本篇为排序算法系列第一篇，详细讲述珠排序算法。后续代码默认使用Python3.9版本。

01 什么是bead sort(珠排序)？

这是一种自然排序算法，类似于算盘纵向平行柱上面的珠子，纵向平行柱的数量代表待排序数字的最大值，每根柱子上面的柱子数量代表待排序数个数（如待排序数组L = [1, 5, 3, 2, 7, 4]，则需要纵向平行柱m=7，每根柱子珠子数量n=6），然后珠子会在重力作用下自由降落。

然而这个算法在真实实现时性能比较『拉夸』，最好情况下时间复杂度为O(n^2)，而且只能对正整数进行排序。

02 算法流程

待排数组[6 2 4 1 5 9]（图A），让所有珠子在重力作用下自由落体，9、5、1都有支撑点，不需要滑落；4除第一个珠子不动外，其它三颗全部下落到1的位置（图B）；剩余几个数字做同样自由落地；最终从上到下顺序输出即可得到结果:[ 1 2 4 5 6 9]。

03 Python实现

def bead_sort


    
(sequence: list) -> list:
    """
    >>> bead_sort([6, 11, 12, 4, 1, 5])
    [1, 4, 5, 6, 11, 12]
    >>> bead_sort([9, 8, 7, 6, 5, 4 ,3, 2, 1])
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    >>> bead_sort([5, 0, 4, 3])
    [0, 3, 4, 5]
    >>> bead_sort([8, 2, 1])
    [1, 2, 8]
    >>> bead_sort([1, .9, 0.0, 0, -1, -.9])
    Traceback (most recent call last):
    ...
    TypeError: Sequence must be list of nonnegative integers
    >>> bead_sort("Hello world")
    Traceback (most recent call last):
    ...
    TypeError: Sequence must be list of nonnegative integers
    """
    if any(not isinstance(x, int) or x 0 for x in sequence):
        raise TypeError("Sequence must be list of nonnegative integers")
    for _ in range(len(sequence)):
        for i, (rod_upper, rod_lower) in enumerate(zip(sequence, sequence[1:])):
            if rod_upper > rod_lower:
                sequence[i] -= rod_upper - rod_lower
                sequence[i + 1] += rod_upper - rod_lower
    return sequence


if __name__ == "__main__":
    assert bead_sort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5]
    assert bead_sort([7, 9, 4, 3, 5]) == [3, 4, 5, 7, 9]