计数排序（Counting Sort）是一种非比较型整数排序算法，其核心思想是使用一个额外的数组（称为计数数组）来存储每个整数值出现的次数。然后根据这些计数来确定每个元素在排序数组中的位置。计数排序不是基于比较的算法，因此它不受输入数据的初始排序状态影响，且排序的速度很快，特别适用于一定范围内的整数排序。计数排序是一种非比较型整数排序算法，特别适合于非负整数的排序，尤其是当数字范围不大时。它的工作原理是统计数组中每个元素出现的次数，然后根据这些计数来确定每个元素在排序数组中的位置。计数排序的时间复杂度为O(n+k)，其中n是数组长度，k是数值范围。

特点：

  1. 非比较排序：不通过元素之间的比较来确定顺序。
  2. 空间消耗：需要额外的空间来存储计数数组。
  3. 适用范围：适用于整数且整数的范围不是很大时效率较高。
  4. 稳定性：计数排序是稳定的排序算法，相等的元素在排序后不会改变顺序。
  5. 时间复杂度：在最坏的情况下，计数排序的时间复杂度为 (O(n + k))，其中 (n) 是数组长度，(k) 是数值范围。

步骤：

  1. 找出数组中最大值：确定计数数组的大小。
  2. 创建并初始化计数数组：创建一个长度为 (k+1) 的计数数组并初始化为0，其中 (k) 是数组中的最大值。
  3. 填充计数数组：遍历原数组，将每个元素的值作为计数数组的索引，并将其对应的计数加1。
  4. 累加计数数组：将计数数组中的每个元素进行累加，累加值表示该元素在排序后数组中的最终位置。
  5. 构建排序数组：根据累加后的计数数组构建排序数组，将每个元素放到其最终位置。
  6. 复制到原数组：（可选）将排序数组复制回原数组，完成排序。

应用场景

  1. 整数排序：当需要对一系列整数进行排序，且整数的数值范围不大时，计数排序可以非常高效地完成排序任务。
  2. 统计频率：计数排序可以用来统计一个数字序列中每个数字出现的次数，这在数据分析和处理中非常有用。
  3. 简单查找表：在某些情况下，计数排序可以用来构建一个简单的查找表，例如，快速查找一个数字在序列中出现的索引位置。
  4. 机器学习：在机器学习领域，计数排序可以用于构建输入数据的直方图，或者在处理分类变量时进行快速排序和统计。
  5. 数据库索引：在数据库中，计数排序可以用于快速生成索引，提高查询效率。
  6. 文本处理：在文本处理中，计数排序可以用来快速统计字符出现的频率，例如在处理自然语言处理任务时统计单词出现的次数。
  7. 游戏开发：在游戏开发中，计数排序可以用来快速排序游戏中的得分或者状态更新。

局限性

计数排序算法在处理浮点数排序时存在一些局限性，主要是因为计数排序的设计和优化主要是针对整数排序。

  1. 整数范围假设：计数排序算法通常假设输入数据是整数，并且整数的范围是有限的。对于浮点数，如果没有适当的转换或缩放，计数排序可能无法直接应用。
  2. 数值范围：浮点数的数值范围通常很大，远远超出了整数的范围。如果直接使用计数排序，可能需要一个非常大的计数数组来覆盖所有可能的浮点数值，这会导致巨大的内存消耗。
  3. 精度问题：浮点数具有小数部分，这使得直接计数变得复杂。在计数排序中，需要决定如何处理浮点数的小数部分，是否四舍五入，以及如何处理相等的小数值。
  4. 稳定性问题：计数排序的一个优点是它的稳定性，即相等元素的相对顺序在排序后保持不变。但是，当处理浮点数时，由于精度和表示的问题，可能会破坏这种稳定性。
  5. 实现复杂性：为了使计数排序能够处理浮点数，可能需要对算法进行修改，例如通过缩放浮点数到整数范围，或者使用桶排序的思想来处理小数部分。这些修改增加了算法的实现复杂性。
  6. 效率问题：即使可以通过适当的缩放和转换来处理浮点数，计数排序在处理浮点数时也可能不如专门设计的浮点数排序算法高效。
  7. 数据分布：计数排序的效率在很大程度上取决于数据的分布。对于浮点数，数据可能非常稀疏，这意味着大量的计数数组槽位将为空，导致空间利用效率低下。

示例

  1. 找出数组中的最大值和最小值，然后创建一个计数数组来存储每个整数出现的次数。
  2. 累加计数数组中的值，以便每个元素的位置可以被确定。
  3. 创建一个输出数组，根据计数数组中的信息将元素放到正确的位置上。
public class CountingSort {
    public static void countingSort(int[] arr) {
        // 找出数组中的最大值和最小值
        int max = arr[0];
        int min = arr[0];
        for (int value : arr) {
            if (value > max) {
                max = value;
            }
            if (value < min) {
                min = value;
            }
        }

        // 创建并初始化计数数组
        int range = max - min + 1;
        int[] count = new int[range];
        for (int i = 0; i < range; i++) {
            count[i] = 0;
        }

        // 统计每个元素的出现次数
        for (int value : arr) {
            count[value - min]++;
        }

        // 累加计数数组中的值
        for (int i = 1; i < range; i++) {
            count[i] += count[i - 1];
        }

        // 创建输出数组，并根据计数数组构建排序数组
        int[] output = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[arr[i] - min] - 1] = arr[i];
            count[arr[i] - min]--;
        }

        // 将排序后的数组复制回原数组
        for (int i = 0; i < arr.length; i++) {
            arr[i] = output[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        countingSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

def counting_sort(arr):
    max_val = max(arr)
    min_val = min(arr)
    range_val = max_val - min_val

    # 创建计数数组并初始化为0
    count_arr = [0] * (range_val + 1)

    # 计数每个元素的出现次数
    for num in arr:
        count_arr[num - min_val] += 1

    # 累加计数数组中的值
    for i in range(1, len(count_arr)):
        count_arr[i] += count_arr[i - 1]

    # 创建输出数组，并根据计数数组构建排序数组
    output_arr = [0] * len(arr)
    for num in reversed(arr):
        output_arr[count_arr[num - min_val] - 1] = num
        count_arr[num - min_val] -= 1

    return output_arr

# 示例
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print("Sorted array:", sorted_arr)

注意事项

  • 计数排序不适合处理有大量重复元素的数组，因为这样会导致计数数组的索引变得非常大。
  • 当数值范围 (k) 很大时，计数排序的空间复杂度会很高，可能不适用。

计数排序在处理特定类型的数据时非常有效，尤其是当数据范围较小且数据分布比较均匀时。在这种情况下，它通常比基于比较的排序算法更快。