def counting_sort(a, k, reverse=False):
    """
    计数排序
    基本思想：对每一条记录，计算小于这条记录的记录个数。利用这一信息，就可以直接确定该记录的位置。
    当有几条记录相同时，则需要调整一下位置。
    记录值分布在0-k之间，建立C[0...k]，根据记录值找到在C中的位置，该位置计数器+1。
    数组C中某个位置Ci，C[0...i-1]的所有值相加，即为小于i的记录的个数。依次计算C[1...k]的值，即C[i]=C[i]+C[i-1]。
    根据C中数据重新确定待排序列中记录的位置。

    :param a:
    :param k:
    :param reverse:
    :return:
    """
    b = [0] * len(a)  # 有序序列输出辅助
    c = [0] * (k + 1)  # 计数辅助
    # 计数
    for v in a:
        c[v] += 1

    if reverse:
        # 计算比记录i大的记录的个数
        for i in range(len(c) - 2, -1, -1):
            c[i] += c[i + 1]
    else:
        # 计算比记录i小的记录的个数
        for i in range(1, len(c)):
            c[i] += c[i - 1]

    for v in a:
        # 根据C数据，定位记录到输出序列
        b[c[v] - 1] = v
        # 如果有多条相同的记录，调整位置
        c[v] -= 1

    return b