第39讲：什么是计数排序（上）

问题 1： 什么是计数排序？
回答： 计数排序是一种非比较型的排序算法，它通过统计数组中每个元素出现的次数来实现排序，适用于数据范围有限且分布均匀的情况。

问题 2： 计数排序适用于什么样的数据？
回答： 计数排序适用于数据范围有限且分布均匀的情况，例如整数排序，尤其是当数据范围不大时。

问题 3： 计数排序的时间复杂度是多少？
回答： 计数排序的时间复杂度为 O(n+k)，其中 n 是待排序数组的长度，k 是数据的范围大小。

问题 4： 计数排序的空间复杂度是多少？
回答： 计数排序的空间复杂度为 O(k)，因为需要额外的空间来存储每个元素的计数。

问题 5： 计数排序与比较排序算法（如快速排序、归并排序）有什么不同？
回答： 计数排序是一种非比较型排序算法，它通过统计元素出现的次数来排序，而比较排序算法则是通过比较元素的大小来进行排序。

问题 6： 计数排序的步骤是什么？
回答： 计数排序的步骤包括：1) 统计每个元素出现的次数；2) 计算每个元素在排序后数组中的位置；3) 将元素放入正确的位置。

问题 7： 计数排序的优缺点是什么？
回答： 计数排序的优点是时间复杂度低，适用于特定类型的数据；缺点是空间复杂度较高，且仅适用于整数排序。

问题 8： 计数排序是否稳定？
回答： 是的，计数排序是一种稳定的排序算法，相同元素的相对顺序在排序后不会改变。

问题 9： 计数排序在实际应用中有哪些场景？
回答： 计数排序常用于数据范围有限且需要稳定排序的场景，例如统计成绩、年龄等整数数据的排序。

问题 10： 计数排序与桶排序有什么区别？
回答： 计数排序是桶排序的一种特殊情况，它使用固定大小的“桶”来统计元素出现的次数，而桶排序则可以根据数据分布动态调整桶的大小。