Python中字符串的基数排序

Question

与 Python 的排序相比，我的基数排序函数输出排序但错误的列表：

My radix sort: ['aa', 'a', 'ab', 'abs', 'asd', 'avc', 'axy', 'abid']
Python's sort: ['a', 'aa', 'ab', 'abid', 'abs', 'asd', 'avc', 'axy']

* 我的基数排序不做填充
* 它的机制是最低有效位 (LSB)
* 我需要利用每个单词的长度

以下是我的代码。

def count_sort_letters(array, size, col, base):
    output   = [0] * size
    count    = [0] * base
    min_base = ord('a')

    for item in array:
        correct_index = min(len(item) - 1, col)
        letter = ord(item[-(correct_index + 1)]) - min_base
        count[letter] += 1

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

    for i in range(size - 1, -1, -1):
        item = array[i]
        correct_index = min(len(item) - 1, col)
        letter = ord(item[-(correct_index + 1)]) - min_base
        output[count[letter] - 1] = item
        count[letter] -= 1

    return output


def radix_sort_letters(array):
    size = len(array)

    max_col = len(max(array, key = len))

    for col in range(max_col):
        array = count_sort_letters(array, size, col, 26)

    return array

任何人都可以找到解决这个问题的方法吗？

Answer 1

正如我在评论中提到的：

在您的代码中：

correct_index = min(len(item) - 1, col)
letter = ord(item[-(correct_index + 1)]) - min_base

一旦 col 大于单词长度，则始终使用单词的第一个字母。一旦 col 大于单词长度，这会导致较短的单词根据它们的第一个字母进行排序。例如， ['aa', 'a'] 保持不变，因为在 for col 循环中我们比较了两个单词中的 'a'，结果保持不变。

代码更正

注意：尝试尽量减少对原始代码的更改

def count_sort_letters(array, size, col, base, max_len):
  """ Helper routine for performing a count sort based upon column col """
  output   = [0] * size
  count    = [0] * (base + 1) # One addition cell to account for dummy letter
  min_base = ord('a') - 1 # subtract one too allow for dummy character

  for item in array: # generate Counts
    # get column letter if within string, else use dummy position of 0
    letter = ord(item[col]) - min_base if col < len(item) else 0
    count[letter] += 1

  for i in range(len(count)-1):   # Accumulate counts
      count[i + 1] += count[i]

  for item in reversed(array):
    # Get index of current letter of item at index col in count array
    letter = ord(item[col]) - min_base if col < len(item) else 0
    output[count[letter] - 1] = item
    count[letter] -= 1

  return output

def radix_sort_letters(array, max_col = None):
  """ Main sorting routine """
  if not max_col:
    max_col = len(max(array, key = len)) # edit to max length

  for col in range(max_col-1, -1, -1): # max_len-1, max_len-2, ...0
    array = count_sort_letters(array, len(array), col, 26, max_col)

  return array

lst = ['aa', 'a', 'ab', 'abs', 'asd', 'avc', 'axy', 'abid']
print(radix_sort_letters(lst))

测试

lst = ['aa', 'a', 'ab', 'abs', 'asd', 'avc', 'axy', 'abid']
print(radix_sort_letters(lst))

# Compare to Python sort
print(radix_sort_letters(lst)==sorted(lst))

输出

['a', 'aa', 'ab', 'abid', 'abs', 'asd', 'avc', 'axy']
True

解释

Counting Sort是一种稳定排序的含义：

让我们通过一个示例来了解该函数的工作原理。

让我们排序： ['ac', 'xb', 'ab']

我们以相反的顺序遍历每个列表的每个字符。

迭代 0：

Key is last character in list (i.e. index -1):       
keys are ['c','b', 'b'] (last characters of 'ac', 'xb', and 'ab'

Peforming a counting sort on these keys we get ['b', 'b', 'c']

This causes the corresponding words for these keys to be placed in    
the order:    ['xb', 'ab', 'ac']

Entries 'xb' and 'ab' have equal keys (value 'b') so they maintain their 
order of 'xb' followed by 'ab' of the original list 
(since counting sort is a stable sort)

迭代 1：

Key is next to last character (i.e. index -2):

Keys are ['x', 'a', 'a'] (corresponding to list ['xb', 'ab', 'ac'])

Counting Sort produces the order ['a', 'a', 'a']
which causes the corresponding words to be placed in the order
['ab', 'ac', 'xb'] and we are done.

原始软件错误——您的代码最初是从左到右通过字符串而不是从右到左。我们需要从右到左，因为我们希望根据第一个字符对最后一个排序进行排序，根据第二个字符对倒数第二个排序进行排序，依此类推。

不同长度的字符串——上面的例子是等长的字符串。

前面的例子被简化为等长字符串。现在让我们尝试不等长的字符串，例如：

['ac', 'a', 'ab']

这立即提出了一个问题，因为单词的长度不同，我们不能每次都选择一个字母。

我们可以通过用一个虚拟字符（例如“*”）填充每个单词来修复，以获得：

['ac', 'a*', 'ab']

迭代 0：键是每个单词的最后一个字符，所以：['c', '*', 'b']

The understanding is that the dummy character is less than all other
characters, so the sort order will be:
['*', 'b', 'c'] causing the related words to be sorted in the order

['a*', 'ab', 'ac']

迭代 1：键在每个单词的最后一个字符旁边，因此：['a', 'a', 'a']

 Since the keys are all equal counting sort won't change the order so we keep

  ['a*', 'ab', 'ac']

Removing the dummy character from each string (if any) we end up with:

    ['a', 'ab', 'ac']

get_index 背后的想法是模仿没有实际填充的填充字符串的行为（即填充是额外的工作）。因此，它根据索引评估索引是否指向字符串的填充或未填充部分，并将适当的索引返回到计数数组中以进行计数。