编程知识 cdmana.com

算法:计数排序

目录

一、简述

二、算法思路

三、图解实例

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))

 

 

 
 

 

 

 

 

 

 

 

版权声明
本文为[Amae]所创,转载请带上原文链接,感谢
https://blog.csdn.net/Smart_look/article/details/125380349

Scroll to Top