常用排序-基数排序,计数排序

基数排序
将整数每个位数分别比较,先找出最长位,针对每个位(个位,十位…)利用桶的思想,将每个位的元素个数统计,倒序读入temp[10]列表中,
时间复杂度O(d(n+K)),k是10进制,n为最大位数,空间复杂度O(n+k)
计数排序
利用数组的下标确定元素的正确位置,适用于一定范围内的整数排序,最大值最小值差距太大不适用于计数排序,
在取值范围不是很大的情况下,性能超过快速排序。
求得最大整数MAX和最小整数MIN,数列最小值为偏移量,创建的数组长度就是MAX-MIN+1。
时间复杂度O(n+m),空间复杂度O(m),n是排序个数,m是最大最小的差值。
计数排序的最终步骤:
1、取无序数组list中的最大值max和最小值min,新建(max-min +1)长度的数组newArr和统计数组countArr。
2、遍历原数组list,将其值作为newArr的键,元素的个数作为值存放在该键处。
3、遍历newArr,使统计数组countArr和newArr相同索引处存放的是newArr该索引之前元素的和。
4、新建一个最终数组result,反向遍历原数组,取原数组的值arr[i]-min作为索引,从统计数组countArr取出该索引的值减1,作为最终数组result的索引,值为原数组的arr[i],同时统计数组该索引处值减1,遍历结束后,最终数组result为排序后的数组。

相关推荐

  1. 排序-基数排序计数排序

    2023-12-24 19:24:02       56 阅读
  2. python实现计数排序、桶排序基数排序算法

    2023-12-24 19:24:02       18 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2023-12-24 19:24:02       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2023-12-24 19:24:02       101 阅读
  3. 在Django里面运行非项目文件

    2023-12-24 19:24:02       82 阅读
  4. Python语言-面向对象

    2023-12-24 19:24:02       91 阅读

热门阅读

  1. 迭代器模式(Iterator)

    2023-12-24 19:24:02       61 阅读
  2. 408真题笔记

    2023-12-24 19:24:02       39 阅读
  3. 微服务项目遇到的小问题

    2023-12-24 19:24:02       56 阅读
  4. 如何在Vim/Vi中使用“搜索”功能

    2023-12-24 19:24:02       63 阅读
  5. IO的多路复用

    2023-12-24 19:24:02       65 阅读
  6. 交叉熵损失(Cross Entropy Loss)学习笔记

    2023-12-24 19:24:02       63 阅读