线性时间排序算法：计数排序、桶排序与基数排序详解

引言

排序算法的时间复杂度通常被限制在O(n log n)，如快速排序、归并排序和堆排序。然而，在某些特定场景下，线性时间排序算法（时间复杂度为O(n)）则可以更高效地完成任务。

今天，我们将深入探讨计数排序、桶排序和基数排序的核心思想和实现方法。它们利用了数据的特点和分布规律，通过避免比较操作，达到了更优的时间复杂度。尽管适用范围有限，但在合适的场景下，它们可以成为绝佳的排序工具。

一、计数排序（Counting Sort）

1.1 算法思想

计数排序是一种基于计数统计的排序算法，适用于元素范围有限且为非负整数的数据。其核心思想是：

1. 根据数据的值，统计每个元素出现的次数。
2. 累加计数，确定每个元素在结果数组中的位置。
3. 根据计数结果，将元素放置到正确位置。

1.2 算法过程

假设待排序的数组为 ，范围为 ：

1. 计数统计：创建一个大小为的计数数组，统计每个值的出现次数。
2. 累加计数：对进行累加，用于确定每个元素的最终位置。
3. 输出结果：遍历原数组，根据中的位置信息，将元素存入结果数组。

1.3 C语言实现

1.4 时间和空间复杂度

• 时间复杂度：O(n + k)，其中是数组大小，是最大值范围。
• 空间复杂度：O(n + k)，需要额外的计数数组和输出数组。

1.5 特点与适用场景

• 特点：
  • 稳定排序。
  • 适用于元素范围小的整数数据。
• 适用场景：
  • 数据范围有限，数据分布均匀（如考试成绩统计）。

二、桶排序（Bucket Sort）

2.1 算法思想

桶排序通过将数据分配到若干个“桶”中，每个桶内的数据进行单独排序后再合并。其核心思想是分而治之：

1. 根据数据分布，将元素分配到不同的桶中。
2. 对每个桶内的元素单独排序。
3. 按顺序合并所有桶内的元素，得到最终结果。

2.2 算法过程

1. 分桶：创建若干个桶，每个桶对应一个数据范围。
2. 入桶：将元素根据其值分配到对应的桶中。
3. 桶内排序：对每个桶单独排序。
4. 合并结果：依次将所有桶的元素合并。

2.3 C语言实现

2.4 时间和空间复杂度

• 时间复杂度：

  
  

  • 平均：O(n + k)（假设桶内排序为线性时间）。
  • 最坏：O(n²)（所有数据集中在一个桶内）。
• 空间复杂度：O(n + k)。

2.5 特点与适用场景

• 特点：
  • 非比较排序，效率高。
  • 稳定排序。
• 适用场景：
  • 数据分布均匀，范围已知（如浮点数排序）。

三、基数排序（Radix Sort）

3.1 算法思想

基数排序通过对数据的位（如个位、十位、百位）依次排序来完成整体排序。它使用稳定的排序算法（如计数排序）作为子过程。

3.2 算法过程

1. 从最低位开始，对数组按每一位的值进行排序。
2. 每次排序完成后，按当前位的顺序重新组织数组。
3. 重复上述过程，直到最高位。

3.3 C语言实现

四、总结与展望

线性时间排序算法在特定场景下效率极高，适合对数据范围明确、特点清晰的任务。下一篇文章中，我们将总结排序算法的整体特点，并通过实战案例展示如何选择合适的排序算法。