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

简介

简要说明

  • 基数排序是一种非比较型整数排序算法。
  • 将整数按位数切割成不同的数字，然后按每个位数进行比较排序。排序过程是通过分配和收集来完成的，其中分配是将数字按照某位的大小放入桶中，收集是将桶中的数字再放回原数组。

主要功能

  • 对一组非负整数进行排序。
  • 可以按照个位、十位、百位等顺序进行排序，直到最高位。

注意事项

  • 基数排序适用于整数或者字符串排序。
  • 如果要排序的数据包含负数，则需要特殊处理，例如可以添加一个偏移量使得所有数都成为非负数。
  • 基数排序的性能很大程度上取决于桶的实现和数据的分布。

适用场景

  • 数据范围不大，但数据量很大时，基数排序非常有效。
  • 适用于整数排序，特别是当数字的位数较少时。

时间复杂度

  • 平均情况：O(nk)，其中n是待排序元素的数量，k是数字的最大位数。

空间复杂度

  • O(n + k)，其中n是待排序元素的数量，k是数字的最大位数。

Java 8

import java.util.Arrays;

public class RadixSort {

    // 主方法调用基数排序
    public static void main(String[] args) {
        int[] array = {170, 45, 75, 90, 802, 24, 2, 66};
        System.out.println("Original array: " + Arrays.toString(array));

        radixSort(array);

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

    // 基数排序方法
    public static void radixSort(int[] array) {
        // 找到最大值以确定位数
        int max = Arrays.stream(array).max().getAsInt();

        // 对每一位进行排序，从个位开始
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(array, exp);
        }
    }

    // 根据当前位进行计数排序
    private static void countingSortByDigit(int[] array, int exp) {
        int n = array.length;
        int[] output = new int[n]; // 输出数组
        int[] count = new int[10]; // 计数数组，范围0-9

        // 初始化计数数组
        Arrays.fill(count, 0);

        // 计算每个桶的元素个数
        for (int value : array) {
            count[(value / exp) % 10]++;
        }

        // 更改count[i]，使count[i]包含位置信息
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 构建输出数组
        for (int i = n - 1; i >= 0; i--) {
            output[count[(array[i] / exp) % 10] - 1] = array[i];
            count[(array[i] / exp) % 10]--;
        }

        // 将排序好的数组复制回原数组
        System.arraycopy(output, 0, array, 0, n);
    }
}

注释

在这个Java案例中，radixSort 方法实现了基数排序算法。它首先找到数组中的最大值以确定位数，然后对每一位进行计数排序。countingSortByDigit 方法是一个辅助方法，用于根据当前位进行计数排序。

更新时间: