计数排序算法及其实现步骤与适用场景

由 Java Q&A Hub 使用 GPT-4o-mini 回答

问题：

计数排序

回答：

计数排序（Counting Sort）是一种非比较排序算法，适用于范围较小的整数排序。它的基本思想是通过统计每个元素出现的次数，然后根据这些计数来确定每个元素在排序后数组中的位置。计数排序的时间复杂度为 O(n + k)，其中 n 是待排序元素的数量，k 是元素值的范围。

计数排序的步骤

  1. 确定范围：找出待排序数组中的最大值和最小值，以确定计数数组的大小。
  2. 创建计数数组：创建一个计数数组，大小为最大值与最小值之差加一，用于存储每个元素出现的次数。
  3. 统计元素出现次数：遍历待排序数组，统计每个元素的出现次数，并将其存储在计数数组中。
  4. 累加计数数组：对计数数组进行累加，使得每个元素的值表示小于或等于该元素的元素个数。
  5. 构建输出数组：根据计数数组的值，将元素放入输出数组中，最后将输出数组复制回原数组。

计数排序的代码示例

以下是 Java 中实现计数排序的示例代码：

import java.util.Arrays;

public class CountingSort {
    public static void countingSort(int[] arr) {
        if (arr.length == 0) {
            return; // 如果数组为空，直接返回
        }

        // 找到最大值和最小值
        int max = Arrays.stream(arr).max().getAsInt();
        int min = Arrays.stream(arr).min().getAsInt();

        // 创建计数数组
        int range = max - min + 1; // 计算范围
        int[] count = new int[range];
        int[] output = new int[arr.length];

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

        // 累加计数数组
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        // 构建输出数组
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[arr[i] - min] - 1] = arr[i];
            count[arr[i] - min]--;
        }

        // 将输出数组复制回原数组
        System.arraycopy(output, 0, arr, 0, arr.length);
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("原数组: " + Arrays.toString(arr));
        countingSort(arr);
        System.out.println("排序后数组: " + Arrays.toString(arr));
    }
}

代码分析

  1. 输入检查：首先检查输入数组是否为空。
  2. 最大值和最小值：使用 Java 8 的流 API 找到数组中的最大值和最小值。
  3. 计数数组：创建一个计数数组，其大小为 max - min + 1，以便能够存储所有可能的元素。
  4. 统计次数：遍历输入数组，更新计数数组中对应元素的计数。
  5. 累加计数：对计数数组进行累加，使得每个位置的值表示小于或等于该元素的数量。
  6. 构建输出：从后向前遍历输入数组，使用计数数组确定每个元素在输出数组中的位置，并减少计数。
  7. 复制回原数组：使用 System.arraycopy 方法将排序后的结果复制回原数组。

适用场景

计数排序适用于以下情况：

  • 数组中的元素范围较小（例如 0 到 1000）。
  • 需要稳定排序（相同元素的相对顺序保持不变）。

注意事项

  • 计数排序不适合处理大范围的整数，因为它需要额外的空间来存储计数数组。
  • 计数排序是稳定的排序算法，适合用于需要保持相同元素相对顺序的场景。

Related