Java 中的线性排序算法详解

简介

在 Java 编程中，排序算法是非常基础且重要的一部分。线性排序（Linear Sort）是一类时间复杂度能达到线性级别的排序算法，相较于常见的比较排序算法（如快速排序、归并排序，它们的平均时间复杂度为 $O(n log n)$），线性排序在特定条件下能提供更高效的排序性能。本文将详细介绍 Java 中线性排序的基础概念、使用方法、常见实践以及最佳实践。

目录

1. 线性排序的基础概念
2. Java 中常见的线性排序算法
   • 计数排序
   • 桶排序
   • 基数排序
3. 线性排序的使用方法
4. 常见实践
5. 最佳实践
6. 小结
7. 参考资料

线性排序的基础概念

线性排序是指时间复杂度为 $O(n)$ 的排序算法。这类算法不基于元素之间的比较来确定顺序，而是利用元素的某些特性（如元素的值范围、元素的位数等）来实现排序。由于不需要进行大量的比较操作，线性排序在特定场景下可以显著提高排序效率。但线性排序通常对数据有一定的要求，例如数据的取值范围不能过大，数据需要是整数等。

Java 中常见的线性排序算法

计数排序

计数排序的核心思想是统计每个元素出现的次数，然后根据统计结果将元素按顺序输出。

import java.util.Arrays;

public class CountingSort {
    public static void countingSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 找出数组中的最大值
        int max = arr[0];
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
        }
        // 创建计数数组
        int[] count = new int[max + 1];
        // 统计每个元素出现的次数
        for (int num : arr) {
            count[num]++;
        }
        // 根据计数数组将元素放回原数组
        int index = 0;
        for (int i = 0; i <= max; i++) {
            while (count[i] > 0) {
                arr[index++] = i;
                count[i]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        countingSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

桶排序

桶排序的基本思想是将数组中的元素分配到有限个桶中，然后对每个桶中的元素分别进行排序，最后将所有桶中的元素按顺序合并。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BucketSort {
    public static void bucketSort(double[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 确定桶的数量
        int bucketNum = 5;
        // 创建桶
        List<List<Double>> buckets = new ArrayList<>();
        for (int i = 0; i < bucketNum; i++) {
            buckets.add(new ArrayList<>());
        }
        // 将元素分配到桶中
        double max = arr[0];
        double min = arr[0];
        for (double num : arr) {
            if (num > max) {
                max = num;
            }
            if (num < min) {
                min = num;
            }
        }
        double range = (max - min) / bucketNum;
        for (double num : arr) {
            int bucketIndex = (int) ((num - min) / range);
            if (bucketIndex == bucketNum) {
                bucketIndex--;
            }
            buckets.get(bucketIndex).add(num);
        }
        // 对每个桶中的元素进行排序
        int index = 0;
        for (List<Double> bucket : buckets) {
            Collections.sort(bucket);
            for (double num : bucket) {
                arr[index++] = num;
            }
        }
    }

    public static void main(String[] args) {
        double[] arr = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51};
        bucketSort(arr);
        for (double num : arr) {
            System.out.print(num + " ");
        }
    }
}

基数排序

基数排序是一种多关键字排序算法，它从最低位开始，依次对每一位进行排序，直到最高位。

import java.util.Arrays;

public class RadixSort {
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 找出数组中的最大值
        int max = arr[0];
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
        }
        // 从最低位开始进行排序
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortForRadix(arr, exp);
        }
    }

    private static void countingSortForRadix(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};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

线性排序的使用方法

1. 计数排序：适用于数据范围较小且为整数的情况。首先找出数组中的最大值，创建一个计数数组，统计每个元素出现的次数，最后根据计数数组将元素放回原数组。
2. 桶排序：适用于数据均匀分布的情况。确定桶的数量，将元素分配到不同的桶中，对每个桶中的元素进行排序，最后将所有桶中的元素合并。
3. 基数排序：适用于整数排序，尤其是位数较多的整数。从最低位开始，依次对每一位进行计数排序。

常见实践

• 在处理成绩排序时，如果成绩的范围是 0 - 100，可以使用计数排序，因为数据范围较小且为整数。
• 在对大规模的浮点数进行排序时，如果数据分布比较均匀，可以使用桶排序。
• 在对身份证号码进行排序时，可以使用基数排序，因为身份证号码是固定长度的整数。

最佳实践

• 数据范围判断：在选择线性排序算法时，首先要判断数据的范围和特性。如果数据范围过大，计数排序和基数排序可能会消耗大量的内存。
• 空间复杂度考虑：线性排序算法通常需要额外的空间，如计数数组、桶等。在内存有限的情况下，需要谨慎使用。
• 稳定性要求：如果需要排序算法具有稳定性（即相等元素的相对顺序不变），可以选择计数排序和基数排序。

小结

线性排序是一类时间复杂度为 $O(n)$ 的排序算法，包括计数排序、桶排序和基数排序。这些算法在特定条件下能提供高效的排序性能，但对数据有一定的要求。在实际应用中，需要根据数据的范围、分布和特性选择合适的线性排序算法。

参考资料

• 《算法导论》
• Java 官方文档
• GeeksforGeeks 网站