非比较排序算法举例

1. 计数排序

计数排序是一种非比较排序算法，它利用了输入数据中的数值范围来优化排序效率。算法的基本思想是统计每个值出现次数，然后按照这些信息构建输出序列。其时间复杂度为O(n+k)，其中n是输入数组的大小，k是数组中最大值与最小值之间的差距。

实现步骤

1. 寻找待排序数组中的最小值和最大值。
2. 创建一个计数数组count[]，长度为max-min+1。
3. 遍历输入数组，根据每个元素的值增加count[]中对应位置的计数值。
4. 重新遍历count[]数组，将每个值按出现次数输出到结果数组中。

2. 基数排序

基数排序是一种基于位数进行分配和收集的非比较排序算法。它通常以小数点为界，把所有要排序的数值分成整数部分和小数部分，按照位来分别对数据进行排序。时间复杂度为O(d*(n+b))，其中d表示数字的基数（通常为10），n表示数组长度，b表示用于存储的桶数量。

实现步骤

1. 确定数字中最大的位数。
2. 从最低有效位开始，到最高有效位结束进行排序。每次使用一个位的数据值作为排序的标准来进行分配和收集操作。
3. 重复上述过程直到所有位都处理完毕。

3. 桶排序

桶排序是一种分而治之的非比较排序算法。它将数组分隔成若干子区间，然后分别对这些子区间的元素进行排序。通常用于当输入数据均匀分布在一定范围内的场景下。时间复杂度为O(n+k)，其中n是待排序的元素总数，k表示桶的数量。

实现步骤

1. 创建一个足够大的数组作为“桶”。
2. 遍历输入数组中的每个元素，并将它们放入相应的桶中。
3. 对每个非空的桶进行内部排序（通常采用简单排序算法）。
4. 合并所有桶中的元素，形成有序序列。

4. 基于哈希表的排序

基于哈希表的排序利用了哈希函数来实现数据的快速查找。当输入的数据具有良好的分布特性时，这种方法可以在O(n)的时间复杂度内完成排序。

实现步骤

1. 创建一个足够大的哈希表。
2. 遍历输入数组中的每个元素，并将它们插入到哈希表中。
3. 从哈希表中按序号取出所有元素，形成有序序列。

这些非比较排序算法适用于特定场景下提高数据处理效率。选择合适的排序算法能够显著降低时间和空间复杂度，提升程序性能。