文章摘要： 计数排序是一种非比较型整数排序算法。

简介

简要说明

  • 计数排序是一种非比较型整数排序算法。
  • 使用一个额外的数组来计算每个元素的出现次数，然后根据计数数组来将元素放到正确的位置。计数排序适用于小范围整数的排序。

主要功能

  • 对整数进行排序，特别是当整数范围不大时。
  • 通过计数每个元素的出现次数，确定每个元素在排序后数组中的位置。

注意事项

  • 计数排序只适用于非负整数排序。
  • 如果要排序的数据范围很大，计数排序的空间复杂度会非常高。
  • 计数排序不是比较排序，因此其时间复杂度不受输入数据分布的影响。

适用场景

  • 数据范围较小，即最大值和最小值的差值不是很大。
  • 数据量较大，但可以接受额外的空间开销。

时间复杂度

  • 平均情况：O(n + k)，其中n是待排序元素的数量，k是最大元素值与最小元素值的差。

空间复杂度

  • O(n + k)，其中n是待排序元素的数量，k是最大元素值与最小元素值的差。

Java 8

public class CountingSort {

    // 主方法调用计数排序
    public static void main(String[] args) {
        int[] array = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("Original array: " + Arrays.toString(array));

        countingSort(array);

        System.out.println("Sorted array: " + Arrays.toString(array));
    }

    // 计数排序方法
    public static void countingSort(int[] array) {
        // 找到数组中的最大值
        int max = Arrays.stream(array).max().getAsInt();
        
        // 创建计数数组，大小为max+1
        int[] count = new int[max + 1];
        
        // 计算每个元素的出现次数
        for (int number : array) {
            count[number]++;
        }
        
        // 修改计数数组，每个位置存储小于等于该值的元素个数
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }
        
        // 构建输出数组
        int[] output = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            output[count[array[i]] - 1] = array[i]; // 放置元素
            count[array[i]]--; // 减少计数
        }
        
        // 将排序好的数组复制回原数组
        System.arraycopy(output, 0, array, 0, array.length);
    }
}

注释

在这个Java案例中，countingSort 方法实现了计数排序算法。首先，它找到数组中的最大值以确定计数数组的大小。然后，它计算每个元素的出现次数，并修改计数数组以存储小于等于每个值的元素个数。最后，它构建输出数组，并将排序好的数组复制回原数组。

更新时间: