计数排序

计数排序,  只适用于都是整数的列表
时间复杂度:O(n)

列表  list_datas  =  [88,  6,  57,  72,  60,  42,  83,  73,  48,  85]
方式一：可以支持所有整数，包括负整数
        1、找到最小值和最大值,  分别为  6，88
        2、建立计数器从  {6:0,  7:0,  8:0,  ....  88:0}
        3、重新迭代列表，遇到某个数，则计数器对应值  +1
        4、通过计数器回填到列表中

def counting_sort(datas):
    if not datas:
        return datas
    max = datas[0]
    min = datas[0]
    for data in datas:
        if data > max:
            max = data
        if data < min:
            min = data
    counting = {data: 0 for data in range(min, max + 1)}
    for data in datas:
        counting[data] += 1
    index = 0
    for data in range(min, max + 1):
        for x in range(0, counting[data]):
            datas[index] = data
            index += 1
    return datas

方式二：只支持0和正整数
        1、找到最大值，max_value  =  88
        2、建立计数数组，[0]  *  (max_value  +  1),  直接使用数组下标值代替哈希表的键
        3、重新迭代列表，遇到某个数，则计数器对应值  +1
        4、通过计数器回填到列表中

def counting_sort2(datas):
    if not datas:
        return
    max_value = datas[0]
    for data in datas:
        if data > max_value:
            max_value = data
    counting = [0] * (max_value + 1)
    for data in datas:
        if data < 0:
            raise Exception("不支持负数")
        counting[data] += 1
    data_index = 0
    for i in range(0, max_value + 1):
        while counting[i]:
            datas[data_index] = i
            counting[i] -= 1
            data_index += 1

    return datas