def count_sort(array=[]):
    """
    计数排序（不稳定）
        4, 4, 6, 5, 3, 2, 8, 1, 7, 5, 6, 0, 10
        ------------------------------------------找到最大值 --> 10
        创建一个长度为10 + 1的数组
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
        ------------------------------------------
        遍历原数组
        将原数组的元素值作为新数组的索引，逐个+1
        ------------------------------------------
        比如，第一个元素是4
        新数组索引4的值+1
        0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0
        ------------------------------------------
        第二个元素是4
        0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0
        ------------------------------------------
        第三个元素是6
        0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 0
        ------------------------------------------
        。。。。
        ------------------------------------------
        最终
        1, 1, 1, 1, 2, 2, 2, 1, 1, 0, 1
        ------------------------------------------
        再遍历这个新数组
        将新数组的索引作为值，值作为数量，输出
        ------------------------------------------
        比如，索引0，数量是1
        所以第一个元素是0
        0
        ------------------------------------------
        索引1，数量是1
        0, 1
        ------------------------------------------
        索引2，数量是1
        0, 1, 2
        ------------------------------------------
        索引3，数量是1
        0, 1, 2, 3
        ------------------------------------------
        索引4，数量是2
        0, 1, 2, 3, 4, 4
        ------------------------------------------
        索引5，数量是2
        0, 1, 2, 3, 4, 4, 5, 5
        ------------------------------------------
        。。。。。。。。。。
        ------------------------------------------
        0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 7, 8, 10
    """
    # 1.得到数列的最大值
    max_value = array[0]
    for i in array[1:]:
        if i > max_value:
            max_value = i
    # 2.根据数列最大值确定统计数组的长度
    count_array = [0] * (max_value+1)
    # 3.遍历数列，填充统计数组
    for i in array:
        count_array[i] += 1
    # 4.遍历统计数组，输出结果
    sorted_array = []
    for i in range(len(count_array)):
        for j in range(count_array[i]):
            sorted_array.append(i)
    return sorted_array


def count_sort_v2(array=[]):
    """
    计数排序2(稳定)
        -----------------------------------
        95, 94, 91, 110, 90, 99, 93, 91, 92
        找到最大值110和最小值90，计算差值20
        -----------------------------------
        创建一个统计数组，长度为差值20
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
        ----------------------------------
        遍历原数组，减去最小值就是统计数组得索引
        索引（95 - 90） = 5
        0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
        ----------------------------------
        索引（94 - 90） = 4
        0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
        ----------------------------------
        索引（91 - 90） = 1
        1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
        ----------------------------------
        。。。。。。

        1, 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1
        ----------------------------------
        统计数组做变形，后面的元素等于前面的元素之和
        '''
        这样做的用意是什么呢？
            未变形之前，索引的位置就是原数组即将要被排序定位的位置，但是重复的数据，占用同一个位置时，就分不清先后了
            比如，有两个92，大家都在索引3的话，在上面的方法中，直接遍历输出，是不知道谁在前谁在后的
            这个时候，做一个累加，92会跑到索引4的位置，
            遍历原数组的时候，定位元素92，第一个放在了索引4，然后索引4 - 1
            再遇到92，就会放到索引3
            这样的话，是否会发现，后面的92跑到前面来了
            所以遍历原数组的时候，要逆序遍历，这样就能保证相同元素保持原数组的顺序进行排序

        变形的统计数组，最后被减了多少次，最后成了什么样子，是无所谓的
        '''
        1, 3, 4, 5, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9
        ----------------------------------
        在新建一个排序数组存储最终的结果（原数组长度）
        0, 0, 0, 0, 0, 0, 0, 0, 0
        ----------------------------------
        倒序遍历原数组
        92
        减去最小值得到统计数组的索引92 - 90 = 2
        索引2对应4，4 - 1 = 3就是排序数组的索引
        0, 0, 0, 92, 0, 0, 0, 0, 0
        索引2对应值 - 1
        ----------------------------------
        91
        减去最小值得到统计数组的索引91 - 90 = 1
        索引1对应3，3 - 1 = 2就是排序数组的索引
        0, 0, 91, 92, 0, 0, 0, 0, 0
        索引1对应值 - 1
        。。。。。。。。
        [90, 91, 91, 92, 93, 94, 95, 99, 110]
    """
    # 1.得到数列的最大值最小值，并算出差值d
    max_value = array[0]
    min_value = array[0]
    for i in range(1, len(array)):
        if array[i] > max_value:
            max_value = array[i]
        if array[i] < min_value:
            min_value = array[i]
    d = max_value - min_value
    # 2.创建统计数组并统计对应元素个数
    count_array = [0] * (d+1)
    for i in array:
        count_array[i-min_value] += 1
    # 3.统计数组做变形，后面的元素等于前面的元素之和
    for i in range(1, len(count_array)):
        count_array[i] += count_array[i-1]
    # 4.倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组
    sorted_array = [0] * len(array)
    for i in range(len(array)-1, -1, -1):
        sorted_array[count_array[array[i]-min_value]-1] = array[i]
        count_array[array[i] - min_value] -= 1
    return sorted_array


my_array = list([4, 4, 6, 5, 3, 2, 8, 1, 7, 5, 6, 0, 10])
print(count_sort(my_array))
my_array = list([95, 94, 91, 110, 90, 99, 93, 91, 92])
print(count_sort_v2(my_array))