教程目录

想要实际看看算法是如何工作的吗?

通过交互式可视化深入理解算法运行过程

查看算法可视化

介绍

计数排序(Counting Sort)是一种非比较型的排序算法,核心思想是通过统计元素出现的次数进行排序,利用数组的索引来确定元素的正确位置。

计数排序特别适合于已知范围不大的整数序列排序,其时间复杂度为 O(n+k),其中 n 是待排序数组的长度,k 是整数的范围。当 k 不是很大时,计数排序可以实现线性时间排序,这是基于比较的排序算法(快速排序、归并排序等)无法达到的。

算法步骤

  1. 找出待排序数组中的最大值和最小值,确定计数数组的大小
  2. 创建一个计数数组,统计每个元素出现的次数
  3. 对计数数组进行累加,得到每个元素在排序后数组中的位置
  4. 创建一个临时数组,从后向前扫描原数组,根据计数数组确定元素位置
  5. 将临时数组复制回原数组

核心特性

  • 非比较排序:不通过比较元素大小进行排序
  • 稳定排序:相等元素的相对位置在排序后不会改变
  • 时间复杂度:O(n+k),其中 k 是数据范围

...

目录