按长度和字母顺序对字符串进行基数排序

Question

我正在尝试为字符串实现基数排序，但我只能按字符串长度进行排序。我想按长度和字母顺序对字符串数组进行排序。甚至可以用基数排序来做吗？

这是我的代码：

def flatten(arr):
    flatten_arr = []
    for item_arr in arr:
        for item in item_arr:
            flatten_arr.append(item)
    return flatten_arr


count_size = 256


def get_max_length(book_content_arr):
    size = 0
    for word in book_content_arr:
        word_size = len(word)
        if word_size > size:
            size = word_size
    return size


def radix_sort(arr):
    word_length = get_max_length(arr)
    for index in range(0, word_length):
        buckets = [[] for i in range(count_size)]
        for item in arr:
            if len(item) > index:
                num = ord(item[index])
                buckets[num].append(item)
            else:
                buckets[0].append(item)

        arr = flatten(buckets)
    return arr
    
    
example = ["A", "Z", "AB", "EWASADAS", "BY", "SDA" "ZA", "BD", "BA", "DSADSA", "BZ", "KA", "ES"]
print(radix_sort(example))

我的示例数组是这样的

example = ["A", "Z", "AB", "EWASADAS", "BY", "SDA" "ZA", "BD", "BA", "DSADSA", "BZ", "KA", "ES"]

以及预期输出：

["A", "Z", "AB", "BD", "BY", "BZ", "ES", "KA", "DSADSA", "EWASADAS"]

Answer 1

看来我已经解决了。

我只是根据单词的大小将它们放入桶中，然后我使用常规基数排序对每个桶进行排序，计数排序作为子程序，然后我将数组展平。

我正在发布代码，这样它可能对某些人有用

signs = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"]  
def flatten(arr):
    flatten_arr = []
    for item_arr in arr:
        for item in item_arr:
            flatten_arr.append(item)
    return flatten_arr


def get_max_length(arr):
    size = 0
    for word in arr:
        word_size = len(word)
        if word_size > size:
            size = word_size
    return size

def counting_sort_for_letters(arr, index):
    count = [0] * len(signs)
    output = [0] * len(arr)

    for item in arr:
        idx = signs.index(item[index])
        count[idx] += 1

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

    for j in range(len(arr) - 1, -1, -1):
        idx = signs.index(arr[j][index])
        count[idx] -= 1
        output[count[idx]] = arr[j]
    return output


def radix_sort(arr, world_length):
    for i in range(world_length - 1, -1, -1):
        arr = counting_sort_for_letters(arr, i)
    return arr
    

def custom_sort(arr):
    word_length = get_max_length(arr)
    buckets = [[] for i in range(word_length)]
    for item in arr:
        num = len(item) - 1
        buckets[num].append(item)
    for j in range(0, len(buckets)):
        buckets[j] = radix_sort(buckets[j], j + 1)
        
    arr = flatten(buckets)
    return arr
    
    
example = ["A", "Z", "AB", "EWASADAS", "BY", "SDA" "ZA", "BD", "BA", "DSADSA", "BZ", "KA", "ES"]
print(custom_sort(example))

按长度和字母顺序对字符串进行基数排序

Radix Sort for Strings by length and alphabetical order

python

arrays

string

sorting

radix-sort