计数排序

摘要：计数排序，少种类

counting sort

• 适用于数据量大，但是数据的范围较小的情况
• 时间复杂度是O(1),空间复杂度是O(n)

代码

"""
# @Time    :  2020/10/29
# @Author  :  Jimou Chen
"""


def count_sort(array: list):
    max_val = max(array)
    cnt = [0 for _ in range(max_val + 1)]

    for i in array:
        cnt[i] += 1

    print(cnt)
    for i in range(len(cnt)):
        print(str(i) * cnt[i], end='')


if __name__ == '__main__':
    test = list(map(int, input().split()))
    count_sort(test)
'''
2 3 4 1 2 2 4
'''

• 结果

  2 3 4 1 2 2 4
  [0, 1, 3, 1, 2]
  1222344
  Process finished with exit code 0