当前位置：首页 > article >正文

【唐叔学算法】第21天：超越比较-计数排序、桶排序与基数排序的Java实践及性能剖析

article 2024/12/25 6:52:52

非比较排序：计数排序、桶排序与基数排序的深度解析与Java实现

引言

当我们谈论排序算法时，大多数人的第一反应可能是基于元素比较的排序方法，如快速排序或归并排序。然而，存在一类特殊的排序算法——非比较排序，它们不依赖于元素之间的直接比较来决定顺序，而是利用数据本身的特性进行排序。这类算法在特定场景下具有显著的优势，可以提供比 O(n log n) 更好的时间复杂度，尤其是在处理整数或有限范围的数据时。本文将深入探讨三种典型的非比较排序算法：计数排序、桶排序和基数排序，分析它们的原理、实现细节、时间复杂度和空间复杂度，并通过Java代码进行具体实现。

计数排序：基于计数的线性排序算法

算法原理

计数排序（Counting Sort）是一种线性时间复杂度的排序算法，适用于待排序元素的范围已知且较小的场景。其核心思想是通过统计每个元素出现的次数，然后根据统计结果将元素直接放置到正确的位置。

算法步骤

找出待排序序列中的最大值和最小值。
创建一个计数数组，长度为最大值与最小值之差加1，用于统计每个元素出现的次数。
遍历待排序序列，填充计数数组。
根据计数数组，将元素按顺序放回原序列。

时间复杂度与空间复杂度

时间复杂度：O(n + k)，其中n是序列的长度，k是元素的范围（最大值与最小值之差）。
空间复杂度：O(k)，需要额外的计数数组来存储统计结果。

Java实现

public class CountingSort {
    public static void countingSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        // 找出最大值和最小值
        int max = arr[0], min = arr[0];
        for (int num : arr) {
            if (num > max) max = num;
            if (num < min) min = num;
        }

        // 创建计数数组
        int[] count = new int[max - min + 1];

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

        // 根据计数数组重构排序后的数组
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                arr[index++] = i + min;
                count[i]--;
            }
        }
    }

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

桶排序：基于分桶的分布式排序算法

算法原理

桶排序（Bucket Sort）是一种分布式排序算法，适用于数据分布均匀的场景。其核心思想是将待排序的元素分到多个“桶”中，每个桶内部再使用其他排序算法（如插入排序）进行排序，最后将所有桶中的元素按顺序合并。

算法步骤

确定桶的数量，并将元素分配到对应的桶中。
对每个桶中的元素进行排序（通常使用插入排序）。
将所有桶中的元素按顺序合并。

时间复杂度与空间复杂度

时间复杂度：
- 最坏情况：O(n²)，当所有元素都被分配到同一个桶时。
- 最好情况：O(n + k)，当每个桶中只有一个元素时。
- 平均情况：O(n + k)，其中n是序列的长度，k是桶的数量。
空间复杂度：O(n + k)，需要额外的桶空间。

Java实现

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

public class BucketSort {
    public static void bucketSort(float[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        // 创建桶
        int n = arr.length;
        List<List<Float>> buckets = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            buckets.add(new ArrayList<>());
        }

        // 将元素分配到桶中
        for (float num : arr) {
            int bucketIndex = (int) (n * num);
            buckets.get(bucketIndex).add(num);
        }

        // 对每个桶中的元素进行排序
        for (List<Float> bucket : buckets) {
            Collections.sort(bucket);
        }

        // 合并所有桶中的元素
        int index = 0;
        for (List<Float> bucket : buckets) {
            for (float num : bucket) {
                arr[index++] = num;
            }
        }
    }

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

基数排序：基于位数的稳定排序算法

算法原理

基数排序（Radix Sort）是一种稳定的排序算法，适用于整数或字符串的排序。其核心思想是按照元素的位数（从最低位到最高位）进行排序，每次排序都基于当前位数的值，最终得到有序序列。

算法步骤

确定待排序序列中最大数的位数。
从最低位开始，依次对每一位进行排序（通常使用计数排序）。
重复上述步骤，直到最高位。

时间复杂度与空间复杂度

时间复杂度：O(d * (n + k))，其中n是序列的长度，d是最大数的位数，k是基数（如10进制为10）。
空间复杂度：O(n + k)，需要额外的计数数组和临时数组。

Java实现

public class RadixSort {
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        // 找出最大值
        int max = arr[0];
        for (int num : arr) {
            if (num > max) max = num;
        }

        // 对每一位进行排序
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
        }
    }

    private static void countingSortByDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];

        // 统计每个数字出现的次数
        for (int num : arr) {
            int digit = (num / exp) % 10;
            count[digit]++;
        }

        // 计算累加次数
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 根据计数数组重构排序后的数组
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }

        // 将排序结果复制回原数组
        System.arraycopy(output, 0, arr, 0, n);
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        radixSort(arr);
        System.out.println("Sorted array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

对比与总结

计数排序 vs 桶排序 vs 基数排序

特性	计数排序	桶排序	基数排序
时间复杂度	O(n + k)	O(n + k)	O(d * (n + k))
空间复杂度	O(k)	O(n + k)	O(n + k)
稳定性	稳定	稳定	稳定
适用场景	整数范围较小	数据分布均匀	整数或字符串