排序算法之线性时间排序:计数排序,基数排序,桶排序详解

前言

在排序算法的大家族中，比较排序算法（如快速排序、归并排序等）的时间复杂度下限为$O(n\log n)$。而线性时间排序算法另辟蹊径，在特定条件下能够实现$O(n)$的时间复杂度，大大提高了排序效率。本文我将深入介绍计数排序、基数排序和桶排序这三种典型的线性时间排序算法，从原理、实现到性能分析，结合具体代码示例，带大家全面了解它们的应用场景与优势。

一、计数排序（Counting Sort）

1.1 算法原理

计数排序是一种非比较排序算法，它适用于待排序元素的取值范围相对较小的情况。其核心思想是：统计每个元素在数组中出现的次数，然后根据统计结果将元素依次放置到正确的位置上。

具体步骤如下：

确定范围：找出待排序数组中的最大值$max$和最小值$min$，计算出元素的取值范围$range=max-min+1$。

统计计数：创建一个长度为$range$的计数数组$count$，用于统计每个元素出现的次数。遍历待排序数组，将每个元素$num$对应的$count[num-min]$的值加 1。

累计计数：对计数数组$count$进行累计操作，即$count[i]=count[i]+count[i-1]$（$i>0$），此时$count[i]$表示小于等于$i+min$的元素个数。

排序输出：创建一个与原数组长度相同的结果数组$output$，倒序遍历原数组，根据$count$数组确定每个元素在$output$数组中的位置，并将元素放入，同时将$count$数组中对应的值减 1。

1.2 代码实现（Python）

def counting_sort(arr):if not arr:return arrmax_val = max(arr)min_val = min(arr)range_val = max_val - min_val + 1count = [0] * range_valfor num in arr:count[num - min_val] += 1for i in range(1, range_val):count[i] += count[i - 1]output = [0] * len(arr)for num in reversed(arr):output[count[num - min_val] - 1] = numcount[num - min_val] -= 1return output

上述 Python 代码首先计算出元素的取值范围，创建计数数组并统计每个元素的出现次数，然后进行累计计数，最后根据计数结果将元素放入结果数组中，完成排序。

1.3 性能分析

时间复杂度：计数排序的时间复杂度为$O(n+k)$，其中$n$是待排序数组的长度，$k$是元素的取值范围。当$k$与$n$同阶或$k$相对$n$较小时，算法的时间复杂度接近$O(n)$，表现出高效性。

空间复杂度：计数排序需要额外的计数数组和结果数组，空间复杂度为$O(n+k)$。

稳定性：计数排序是稳定的排序算法，因为在将元素放入结果数组时，是按照原数组的顺序倒序处理的，相同元素的相对顺序不会改变。

1.4 适用场景

计数排序适用于元素取值范围有限且相对较小的场景，例如对学生成绩（分数范围通常固定）进行排序，或者对一定范围内的整数进行排序等。

二、基数排序（Radix Sort）

2.1 算法原理

基数排序也是一种非比较排序算法，它基于数字的每一位（如个位、十位、百位等）进行排序。基数排序从最低位开始，依次对每一位数字进行排序，直到最高位排序完成，最终得到有序数组。

具体步骤如下（以十进制整数为例）：

确定位数：找出待排序数组中最大的数，确定其位数$d$，例如最大数是$987$，则$d=3$。

按位排序：从个位（第 0 位）开始，依次对每一位进行排序。对于每一位，使用计数排序或其他稳定排序算法，根据该位数字的大小将元素分配到不同的桶中，然后按照桶的顺序依次取出元素，形成新的数组。重复这个过程，直到最高位排序完成。

2.2 代码实现（Java）

import java.util.ArrayList;
import java.util.List;public class RadixSort {public static int[] radixSort(int[] arr) {if (arr == null || arr.length == 0) {return arr;}int max = getMax(arr);for (int exp = 1; max / exp > 0; exp *= 10) {countingSort(arr, exp);}return arr;}private static int getMax(int[] arr) {int max = arr[0];for (int num : arr) {if (num > max) {max = num;}}return max;}private static void countingSort(int[] arr, int exp) {int[] output = new int[arr.length];int[] count = new int[10];for (int num : arr) {count[(num / exp) % 10]++;}for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}for (int i = arr.length - 1; i >= 0; i--) {output[count[(arr[i] / exp) % 10] - 1] = arr[i];count[(arr[i] / exp) % 10]--;}System.arraycopy(output, 0, arr, 0, arr.length);}public static void main(String[] args) {int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};int[] sortedArr = radixSort(arr);for (int num : sortedArr) {System.out.print(num + " ");}}
}

在上述 Java 代码中，radixSort方法首先找到数组中的最大值，确定排序的位数。然后通过循环，从个位开始，每次调用countingSort方法对当前位进行排序，最终完成整个数组的排序。

2.3 性能分析

时间复杂度：假设待排序数组的长度为$n$，元素的最大位数为$d$，每一位上元素的取值范围为$k$（如十进制中$k=10$）。基数排序需要对每一位进行排序，每次排序的时间复杂度为$O(n+k)$，总共进行$d$次，所以时间复杂度为$O(d(n+k))$。当$d$和$k$相对固定时，时间复杂度接近$O(n)$。

空间复杂度：基数排序在每一位排序时需要额外的计数数组和临时数组，空间复杂度为$O(n+k)$。

稳定性：由于在每一位排序时使用的是稳定排序算法（如计数排序），所以基数排序是稳定的排序算法。

2.4 适用场景

基数排序适用于对整数进行排序，特别是当整数的位数相对固定且取值范围不是特别大时，效果较好。例如对身份证号码、银行卡号等固定长度的数字序列进行排序。

三、桶排序（Bucket Sort）

3.1 算法原理

桶排序的基本思想是将待排序数组分到有限数量的桶子里，每个桶子再分别进行排序（可以使用其他排序算法，如插入排序），最后将各个桶中的元素依次取出，得到有序数组。

具体步骤如下：

确定桶的数量和范围：根据待排序数组的特点，确定桶的数量$m$。同时，找出数组中的最大值$max$和最小值$min$，计算每个桶的范围$range=(max-min+1)/m$。

分配元素到桶中：遍历待排序数组，根据元素的值将其分配到对应的桶中。通常可以通过公式$index=(num-min)/range$计算元素应该放入的桶的索引。

对每个桶进行排序：使用合适的排序算法（如插入排序）对每个桶中的元素进行排序。

合并桶中元素：按照桶的顺序，依次将每个桶中的元素取出，放入结果数组中，得到最终的有序数组。

3.2 代码实现（C++）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;void bucketSort(vector<double>& arr) {int n = arr.size();if (n == 0) return;vector<vector<double>> buckets(10);double max_val = *max_element(arr.begin(), arr.end());double min_val = *min_element(arr.begin(), arr.end());double range = (max_val - min_val + 1) / 10;for (double num : arr) {int index = (num - min_val) / range;buckets[index].push_back(num);}for (auto& bucket : buckets) {sort(bucket.begin(), bucket.end());}arr.clear();for (const auto& bucket : buckets) {for (double num : bucket) {arr.push_back(num);}}
}

上述 C++ 代码中，首先确定桶的数量为 10，计算每个桶的范围，然后将元素分配到对应的桶中。接着使用std::sort函数对每个桶中的元素进行排序，最后将各个桶中的元素合并到原数组中，完成排序。

3.3 性能分析

时间复杂度：桶排序的时间复杂度与桶的数量、每个桶中元素的数量以及桶内使用的排序算法有关。如果桶的数量合理，且每个桶中的元素数量较少，桶内排序时间复杂度较低，整体时间复杂度可以接近$O(n)$。但在最坏情况下，所有元素都分配到同一个桶中，此时时间复杂度退化为桶内排序算法的最坏时间复杂度（如使用插入排序时为$O(n^2)$）。

空间复杂度：桶排序需要额外的空间存储桶和桶内的元素，空间复杂度为$O(n+m)$，其中$m$是桶的数量。

稳定性：如果桶内使用的是稳定排序算法，那么桶排序是稳定的排序算法。

3.4 适用场景

桶排序适用于数据分布较为均匀的情况，例如对大量的浮点数进行排序，或者对一定范围内的整数，且数据分布比较分散时，桶排序能够发挥较好的性能。

四、三种线性时间排序算法的对比与应用选择

排序算法	时间复杂度	空间复杂度	稳定性	适用场景
计数排序	$O(n+k)$	$O(n+k)$	稳定	元素取值范围有限且较小
基数排序	$O(d(n+k))$	$O(n+k)$	稳定	对整数排序，位数固定且取值范围不大
桶排序	理想$O(n)$，最坏$O(n^2)$	$O(n+m)$	取决于桶内算法	数据分布均匀的场景

在实际应用中，应根据数据的特点（如数据类型、取值范围、分布情况等）来选择合适的线性时间排序算法。如果数据满足相应算法的适用条件，线性时间排序算法能够带来比比较排序算法更高的效率，在处理大规模数据时具有显著优势。

总结

计数排序、基数排序和桶排序作为线性时间排序算法的代表，通过独特的设计思路突破了比较排序的时间限制，在特定场景下展现出高效性。它们的原理、实现方式和适用场景各有不同，理解并掌握这些算法，能够帮助我们在面对不同的排序需求时，选择最合适的解决方案。随着数据规模的不断增大，线性时间排序算法的应用价值也将愈发凸显，值得我们深入学习和研究。

That’s all, thanks for reading!
创作不易，点赞鼓励；
知识无价，收藏备用；
持续精彩，关注不错过！