python实现LSD算法

LSD（Least Significant Digit）是一种基于字符串排序的排序算法，用于对数字字符串进行排序。下面是一个用Python实现LSD算法的示例代码：

def counting_sort(arr, digit):
    n = len(arr)
    count = [0] * 10
    output = [0] * n

    for i in range(n):
        index = int(arr[i][digit])
        count[index] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    for i in range(n - 1, -1, -1):
        index = int(arr[i][digit])
        output[count[index] - 1] = arr[i]
        count[index] -= 1

    for i in range(n):
        arr[i] = output[i]

def lsd_sort(arr):
    max_length = max(len(x) for x in arr)
    
    for d in range(max_length - 1, -1, -1):
        counting_sort(arr, d)

    return arr

# 测试示例
arr = ['123', '456', '789', '321', '654', '987']
sorted_arr = lsd_sort(arr)
print(sorted_arr)

这段代码实现了LSD排序算法。首先，定义了一个计数排序函数`counting_sort`，用于按照指定的位数进行排序。然后，在`lsd_sort`函数中，计算出待排序数字串的最大位数，然后从最高位开始依次调用`counting_sort`函数进行排序，直到最低位。最后返回排序后的结果。

在上述示例中，输入的数字串为`['123', '456', '789', '321', '654', '987']`，经过LSD排序后得到的结果为`['123', '321', '456', '654', '789', '987']`。