实现计数排序算法时遇到问题

Question

我正在尝试自学一些python中的排序算法，但是输出遇到了一些麻烦。 我正在尝试实现一种计数排序算法，我已经做到了这一点：

def counting_sort(l):
    nums = l
    highest = max(nums) + 1
    helper_list = [0] * highest
    s_list = []
    for i in range(len(nums)):
        value = nums[i]
        helper_list[value] += 1
    for j in range(len(helper_list)):
        s_list.append([j] * helper_list[j])
    return s_list

一切都进展顺利，但是当我给出诸如[5, 2, 2, 3, 1, 2]之类的输入时.

我得到的输出如下：[[], [1], [2, 2, 2], [3], [5]].

Answer 1

您只需要将"append"更改为"extend"。追加函数将一个元素添加到列表中，在本例中为另一个列表。extend 函数将您的列表与作为参数给出的列表连接起来。

您的函数应如下所示：

def counting_sort(elements):
     highest = max(elements) + 1
     helper_list = [0] * highest
     s_list = []
     for value in elements:
         helper_list[value] += 1
     for j in range(len(helper_list)):
         s_list.extend([j] * helper_list[j])
     return s_list

Answer 2

def counting_sort(unordered_list, k, desc=False):
  '''
  unordered_list is the input array to be sorted.
  k is the range of non-negative key values.
  desc lets the algorithm to sort the array in descending order.
  time complexity is the sum of the times for two steps, O(n + k).
  '''
  count_list = [0] * k
  for element in unordered_list:
    count_list[element] += 1
  if desc:
    enumerator = reversed(list(enumerate(count_list)))
  else:
    enumerator = enumerate(count_list)
  sorted_list = []
  for idx, count in enumerator:
    sorted_list += [idx] * count
  return sorted_list

Answer 3

问题是以下行：

s_list.append([j] * helper_list[j])

这表示将列表（[j]*helper_list[j]）附加到s_list，将该列表添加为新元素或s_list。

相反，您希望将一个列表添加到另一个列表上，这可以像这样完成：

s_list.append += ([j] * helper_list[j])