计数排序–计数排序算法。按照？是的！就这样！
该算法至少涉及两个数组，第一个 –要排序的整数列表，第二个 –大小 = (最大数 – 最小数) + 1 的数组，最初仅包含零。接下来，从第一个数组中取出数字，并使用数字元素获取第二个数组中的索引，该索引加一。遍历整个列表后，我们将得到一个完全填充的第二个数组，其中包含第一个数组中数字的重复次数。 该算法有严重的开销——第二个数组还包含不在第一个列表中的数字的零，即所谓的。内存开销
收到第二个数组后，我们迭代它并按索引写入数字的排序版本，将计数器递减至零。最初，零计数器被忽略。
计数排序算法的非优化操作示例：
- 输入数组 1,9,1,4,6,4,4
- 那么要计数的数组将为 0,1,2,3,4,5,6,7,8,9（最小数字 0，最大数字 9）
- 计数器总数为 0,2,0,0,3,0,1,0,0,1
- 排序数组总数 1,1,4,4,4,6,9
Python 3 中的算法代码：
numbers = [42, 89, 69, 777, 22, 35, 42, 69, 42, 90, 777]
minimal = min(numbers)
maximal = max(numbers)
countListRange = maximal - minimal
countListRange += 1
countList = [0] * countListRange
print(numbers)
print(f"Minimal number: {minimal}")
print(f"Maximal number: {maximal}")
print(f"Count list size: {countListRange}")
for number in numbers:
index = number - minimal
countList[index] += 1
replacingIndex = 0
for index, count in enumerate(countList):
for i in range(count):
outputNumber = minimal + index
numbers[replacingIndex] = outputNumber
replacingIndex += 1
print(numbers)Из-за использования двух массивов, временная сложность алгоритма O(n + k)
Ссылки
https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/countingSort
Источники
https://www.youtube.com/watch?v=6dk_csyWif0
https://www.youtube.com/watch?v=OKd534EWcdk
https://en.wikipedia.org/wiki/Counting_sort
https://rosettacode.org/wiki/Sorting_algorithms/Counting_sort
https://pro-prof.com/forums/topic/%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC-%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8-%D0%BF%D0%BE%D0%B4%D1%81%D1%87%D0%B5%D1%82%D0%BE%D0%BC
