"""  
这个是在原来的数组上  
进行重新写入覆盖的实现方式  
"""  

from random import shuffle  

def counting_sort(array, maxval):  
    # 数组长度为最大值+1  
    m = maxval + 1  
    # 新建一个长度为m全部为0的数组  
    count = [0] * m  
    # 遍历所有的文字  
    for a in array:  
        # a此时虽然为数组里的数字，但是作为index加入到了计数数组里面  
        count[a] += 1  
    # 默认i为0，用来计数全新产生的数组                  
    i = 0  
    # 遍历所有的m，这个时候a就是0～m，0.1.2.3.4...  
    for a in range(m):  
        # 遍历第2个数组，这时候数值为count[a] 其实是index为0，1，2，3里面所有值的个数  
        # 比如这样一个数字 0出现了3次。  
        # 0 1 2 3 4 5    
        # 3 0 3 1 1 2  
        # 那么下面这个for c in range(count(0)) = for c in range(3)  
        # 那么c就应该是0，1，2  
        # i = 0 =>array[0] = 0,array[1] = 0,array[3] = 0结束           
        for c in range(count[a]):   
            array[i] = a  
            i += 1  
    return array  


arr = [1, 1, 2, 3, 4, 4, 5, 6, 7, 8, 8, 8, 10, 10, 12, 14, 14, 15]  

print("原始数组\n",arr)  
shuffle(arr)  

print("打乱之后\n",arr)  
maxval = max(arr)  

counting_sort(arr,maxval)  
print("排序之后\n",arr)  

# 原始数组  
#  [1, 1, 2, 3, 4, 4, 5, 6, 7, 8, 8, 8, 10, 10, 12, 14, 14, 15]  
# 打乱之后  
#  [1, 14, 7, 1, 8, 2, 15, 4, 8, 10, 8, 3, 14, 5, 12, 4, 6, 10]  
# 排序之后  
#  [1, 1, 2, 3, 4, 4, 5, 6, 7, 8, 8, 8, 10, 10, 12, 14, 14, 15]  

def counting_sort(arr, maxVal, minVal):  
    n =len(arr)  
    # 计数数组长度  
    length = maxVal + minVal + 1  
    # 新建一个 排序好的数组  
    outArr = [0 for _ in range(n)]  
    # 新建一个 计数数组  
    countArr = [0 for _ in range(length)]  
    # 遍历所有的数字  
    # 然后放入 countArr  
    # 第一个遍历结束之后得到的数组 print(countArr)  
    # [1, 3, 1, 1, 1, 0, 2, 0, 3, 0, 0, 1, 1, 1, 0, 0, 2]  
    for number in arr:  
        # 这里是 根据最小数字为基准，找到合适的位置  
        countArr[number - minVal] += 1  

    # 对计数数组进行遍历  
    # 从第二个index开始遍历，得到一个数组  
    # 每个位置的值=当前值+前一个位置的值 用来统计出小于等于当前下标的元素个数  
    # [1, 4, 5, 6, 7, 7, 9, 9, 12, 12, 12, 13, 14, 15, 15, 15, 17]  
    for j in range(1, length):  
        countArr[j] = countArr[j] + countArr[j - 1]  
    print(countArr)  
    # 第三个反向遍历  
    # arr[i] 数组最后一个数字 - minVal 最小值 - 1 = 就是这个数字的该在的位置  
    for i in range(n-1, -1, -1):  
        # arr[16] = 1  
        # countArr[1-0] =  countArr[1] = 4  
        # outArr[4-1] = outArr[3] 也就是说 1 应该在outArr[3]的上面  
        outArr[countArr[arr[i] - minVal] - 1] = arr[i]  
        # countArr[1-0] =  countArr[1-0] - 1 = countArr[1] -1  = 4-1 = 3  
        # countArr[arr[i] - minVal] 自减 1  
        countArr[arr[i] - minVal] -= 1  

    return outArr  


arr = [12, 4, 11, 1, 3, 6, 8, 6, 1, 8, 2, 0, 13, 16, 16, 8, 1]  
print("排序之前", arr)  

maxVal = max(arr)  
minVal = min(arr)  
print("排序之后", counting_sort(arr, maxVal,minVal))  

# 排序之前 [12, 4, 11, 1, 3, 6, 8, 6, 1, 8, 2, 0, 13, 16, 16, 8, 1]  
# 排序之后 [0, 1, 1, 1, 2, 3, 4, 6, 6, 8, 8, 8, 11, 12, 13, 16, 16]