python - 解密在 O(N) 时间内运行的基数排序的字符串排序版本

Question

我一直在尝试编写一个需要 O(N) 时间的基数排序版本（其中 N 是数组中所有字符串的组合长度）而不是 O(Nk)（其中 N 是数组的长度和k 是数组中最长字符串的长度）。这是伪代码：

基数排序伪代码

到目前为止，这是我的尝试：

def radix_sort(array):
    array = counting_sort_length(array)
    n = len(array) - 1
    k = len(array[n]) - 1
    m = n
    for j in range(k,-1, -1):
        while m>1 and len(array[m-1]) >= j+1:
            m-=1

        count = [0 for i in range(27)]
        for i in range(m,n+1):
            count[get_idx(array[i][j])] += 1
            

        position = [0 for i in range(27)]
        position[get_idx('a')] = 1

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

        temp = [None for i in range((n  - m + 1)+1)]
       
        for i in range(m, n + 1):
            pos = position[get_idx(array[i][j])]
            temp[pos-1] = array[i]
            position[get_idx(array[i][j])] += 1
        for i in range(m, n+1):
            array[i] = temp[i - m]
    return array
        

        
def get_idx(char):
    return ord(char) % 97

def get_character(idx):
    return chr(idx + 97)


def counting_sort_length(array):
    res= []
    for word in array:
        res.append(len(word))
    u = max(res)
    count = [0 for i in range(u+1)]
    n = len(array)
    for i in range(n):
        count[res[i]] += 1
    position = [0 for i in range(u+1)]
    position[0] = 1
    for i in range(1,u+1):
        position[i] = count[i-1] + position[i-1]
    temp = ["" for i in range(n)]
    for i in range(n):
        temp[position[res[i]] - 1] = array[i]
        position[res[i]] += 1
    array = temp
    return array

我设法得到一个输出，但数组没有排序。有人可以帮我吗，如果可能的话，请指出我在代码中犯的错误？

TIA

标签： pythonarraysstringsortingradix-sort