在python中实现LSD基排序

Question

我正在尝试在python中实现LSD基排序，但是我的代码使用了4循环，有任何方法可以在3或更短的时间内完成吗？

下面是4个循环：

第一个循环遍历输入列表，将其转换为所需的基数，并将每个数字更改为反向列表，如下所示：

123 --> 173 --> [3, 7, 1] #radix == 8

第二个循环遍历新创建的列表，通过添加0使它们具有相同的长度，在输入列表中添加指向相应元素的指针，然后反转list.Like如下：

input: [1234, 56, 7]
After first loop: [[4, 3, 2, 1], [6, 5], [7]]
After the second loop: [[0, 1, 2, 3, 4], [1, 0, 0, 5, 6], [2, 0, 0, 0, 7]]

第三个循环排序元素按LSD顺序使用计数排序，代码如下。

第四个循环使用指针将每件东西放入一个新的列表中，并使用排序顺序。

下面是基排序的代码：

def radix_sort(collection, radix):

    new_collect = []
    max_len = 0

    #loop through collection, convert them to desired form and put in new_collect
    for i in collection:
        num = []
        while i >= radix:
            remain = i % radix
            num.append(remain)
            i = i // radix
        num.append(i)
        new_collect.append(num)

        if len(num) > max_len:
            max_len = len(num)

    #loop through new_collect, extend the each item to same length
    for i in range(0, len(new_collect)):
        space = max_len - len(new_collect[i])
        patch = [0 for j in range(space)]
        new_collect[i].extend(patch)

        #add a pointer to the corresponding element in collection
        new_collect[i].append(i)
        new_collect[i].reverse()

    #sort by digit with counting_sort
    for i in range(-1, -1 - max_len, -1):
        new_collect = counting_sort(new_collect, radix - 1, i)

    #create a new list with same length as collection
    return_list = list(range(len(collection)))

    #put elements in collection to return_list, using the pointer in new_collect
    for i in range(0, len(collection)):
        return_list[i] = collection[new_collect[i][0]]

    return return_list

下面是计数排序的代码：

def counting_sort(collection, d_range, digit = -1):

    d_range += 1

    B = list(range(len(collection) + 1))
    C = list(range(d_range))

    for i in range(d_range):
        C[i] = 0

    for j in collection:
        #C[j] = |{key = j}|
        C[j[digit]] += 1

    for i in range(1, d_range):
        #C[i] = |{key <= i}|
        C[i] = C[i] + C[i - 1]

    for i in range(len(collection) - 1, -1, -1):
        B[C[collection[i][digit]]] = collection[i]
        C[collection[i][digit]] -= 1

    return B[1:]

回复加雷斯·里斯S的答案。

。

哇，谢谢你的详细回答！

1.我想我在命名和记录方面很差。

2.从来都不想使用\{key

3.第二个参数不是键的数目，至少我不打算这样做，它应该是输入的范围，并添加1，使其包含0。所以我想这都是钥匙的可能价值。在代码的改进版本中，seq的值可能大于绑定的长度，我认为这将导致超出范围的错误。

4.关于您在4.1中所说的，由于我的radix_sort函数需要一个基来排序，而且我使用值的范围而不是键的数目，那么仅仅输入基-1或基而不是max()不是更快吗？

5.关于您在4.2中所说的，在我的基排序函数中，我需要将输入的raidx更改为一个给定的值，所以我需要使用一个循环来更改它，而且由于我不希望基数大于10的字母涉及到，所以我需要将每个数字分开，这就是我使用列表的原因。所以，除非我遗漏了什么，否则我认为我无法在这个特定的场景中使用您的方法。

6.您是否使用timeit来计算运行时？或者其他模块？

再次感谢你的回答！

PS:关于我的基数排序函数的一般逻辑，你有什么可以说的吗？有什么可以改进的吗？

Answer 1

无论如何，我没有找到改变一般逻辑的方法，但有了@Gareth 's的答案，我就能够修改代码，使radix_sorted运行速度快30%左右。

1. 我没能对第一个循环做任何事。
2. 在第二个循环中，我避免了重复的查找。在结束时移除反向，因为更改运行counting_sorted的顺序可以做到这一点。另外，我没有添加指针，而是将原始值添加到新的seq中。在我所做的测试中，这似乎更好，但我不确定它将如何以更大的数字依次执行。
3. 在第三个循环中，我颠倒了排序顺序，这样就可以避免第二个循环中的反向排序。
4. 第四个循环现在与返回合并。

以下是新代码：

def radix_sorted(seq, radix):
    """
    Return a new list containing all elements from seq in ascending order.
    Second argument is required to convert seq to desired form.

    """

    converted_seq = []
    max_len = 0

    #loop through seq, convert them to desired form and put in converted_seq
    for i in seq:
        num = []
        while i >= radix:
            remain = i % radix
            num.append(remain)
            i = i // radix
        num.append(i)
        converted_seq.append(num)

        #find the max length for converted number
        if len(num) > max_len:
            max_len = len(num)

    #make every element in converted seq have same length by adding 0s
    #put original key in converted_seq
    for key, item in zip(seq, converted_seq):
        space = max_len - len(item)
        patch = [0] * space
        item.extend(patch)

        #add the element in seq to the new list
        item.append(key)

    #sort by digit with counting_sort
    for i in range(max_len):
        converted_seq = counting_sorted(converted_seq, radix - 1, i)

    #return the sorted list, using the pointer in converted_seq
    return [item[-1] for item in converted_seq]