目录

一、简述

二、算法思路

三、图解实例

3.1 整体过程图解​编辑 

 3.2 把待要排序的列表用列表示出来​编辑

3.3 找出待排序列表中最大的数，构造新的数组：累计计数数组，数组内容全部为0 【蓝色部分】,长度为：待排序数组最大值+1

 3.4 在计数数组上，统计待排序数组，中元素出现的次数 【蓝色部分】​编辑

3.5  把计数数组变更为累计数组【确定其在排序好列表中位置】

 3.6 进行最终结果排序

四，代码实现

一、简述

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

二、算法思路

• 找出待排序的数组中最大和最小的元素；
• 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
• 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
• 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

三、图解实例

3.1 整体过程图解
 

 3.2 把待要排序的列表用列表示出来

3.3 找出待排序列表中最大的数，构造新的数组：累计计数数组，数组内容全部为0 【蓝色部分】,长度为：待排序数组最大值+1

 3.4 在计数数组上，统计待排序数组，中元素出现的次数 【蓝色部分】

3.5  把计数数组变更为累计数组【确定其在排序好列表中位置】

绿色部分计算方式 = 计数数组1.2 中蓝色框中后一个数字+累计数组2.1中绿色框中前一个数组

如：6【累计数组2.1中的绿色框中数字】 = 2 【计数数组1.2中蓝色框中数字】 +4 【累计数字1.2中前一位绿色框中数字】

 3.6 进行最终结果排序

1. 对原始数组进行排序，取出第一个：4
   
   
2. 在累计数组2.2中，4对应的坐标位置8，那种最终结果列表中它的位置7【因为有0，需要-1】
   同时累计数组对应4上面的引用计数也需要-1，更新为7
3. 对原始数组进行排序，取出第一个：9，
   在累计数组2.2中，9对应的坐标位置14，那种最终结果列表中它的位置13【因为有0，需要-1】
   同时累计数组对应9上面的引用计数也需要-1，更新为13
   
4. 重复上述3的操作，终止可排序得出
   

四，代码实现
 

listJ = [4, 48, 3, 50, 4, 47, 5, 48, 15, 46, 4, 47, 27, 36, 48]

def countimgSort(arr):
    maxValue = max(arr)      #求出待排列表的最大值
    bucketLen = maxValue+1   #求出计数数组的列表的个数
    bucket = [0]*bucketLen
    arrLen=len(arr)
    sortedIndex = 0

    #构建累计数组
    for i in range(arrLen):
        if not bucket[arr[i]]:  #判断计数数组中下标中，对应的原始数组中的数字存在不，存在引用计数自增+1，
            bucket[arr[i]] =0  #不在原始数字中存在的，置为0
        bucket[arr[i]]+=1  #存在引用计数自增

    # bucket = [0, 0, 0, 1, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 0, 1]
    #进行最终结果的写入
    for j in range(bucketLen):
        while bucket[j] >0:   #逐个对累计数组中，遍历
            arr[sortedIndex]=j  #交换arr中数字
            sortedIndex+=1 
            bucket[j]-=1  
            print(arr)
    return arr

print(countimgSort(listJ))