计数排序(Python)

def counting(data):
    "data里的value作为计数数组counts的index，然后把counts的value转换成data的index"
    # 计数列表，存储每个值有多少个，以data的值作为索引，所以数组长度以最大值+1为准
    counts = [0 for i in range(max(data)+1)]  # 同时给数组赋初值0，等会逐个计数
    print(counts)

    # Finds the "counts" for each individual number
    for value in data:
        counts[value] += 1
    print(counts)    

    # Finds the cumulative sum counts
    # 对counts列表，每个index对应的值是data中value的个数，索引从0开始，已经排序过了，
    # 所以现在要把counts中每个index的value加上前面位置的个数的和，这样它的value就是data排序后的index的一个区间
    # 比如: counts[0]=5,则代表排序后data的前五个,排序后将在ar[4]、3、2、1、0的位置
    #       counts[1]=2本来，现在要加上前面的变成counts[1]=7;即2将会在排序后ar[6]和ar[5]的位置
    for index in range(1, len(counts)):
        counts[index] = counts[index-1] + counts[index]
    print(counts)

    # Sorting Phase  操作一个data中的值就将counts列表对应的删一个值，即代表索引减一
    # 比如: 一开始counts[1] = 5;则代表遇到data中第一个value为1的值时，让它排到ar[5-1]的位置，
    #       然后，counts[1] = 4;这样遇到下一个1时，它将排到ar[4-1]的位置，从右往左这样
    arr = [0 for loop in range(len(data))]
    for value in data:
        index = counts[value] - 1
        arr[index] = value
        counts[value] -= 1 

    return arr
   

data = [2, 7, 16, 20, 15, 1, 3, 10]
print(counting(data))

# 原文链接：https://coderslegacy.com/python/counting-sort-algorithm/