无法实现计数排序算法
Trouble implementing a counting sort algorithm
我正在尝试自学 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]]
。
您只需将 "append" 更改为 "extend"。 append 函数将一个元素添加到您的列表中,在本例中是另一个列表。 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
问题在于线路:
s_list.append([j] * helper_list[j])
这表示将列表 ([j]*helper_list[j]
) 附加到 s_list
,将该列表添加为新的 元素 或 s_list
。
相反,您希望将一个列表添加到另一个列表中,可以这样做:
s_list.append += ([j] * helper_list[j])
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
我正在尝试自学 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]]
。
您只需将 "append" 更改为 "extend"。 append 函数将一个元素添加到您的列表中,在本例中是另一个列表。 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
问题在于线路:
s_list.append([j] * helper_list[j])
这表示将列表 ([j]*helper_list[j]
) 附加到 s_list
,将该列表添加为新的 元素 或 s_list
。
相反,您希望将一个列表添加到另一个列表中,可以这样做:
s_list.append += ([j] * helper_list[j])
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