非比较排序

非比较排序是一类特殊的排序算法，它们与传统的基于比较的排序算法不同。传统的排序算法，如快速排序、归并排序、堆排序等，是通过比较元素之间的大小来决定排序顺序的。而非比较排序则是通过其他的方式来实现排序，它们不依赖于元素之间的比较，因此可以达到更高的效率。

1. 非比较排序的种类

常见的非比较排序算法有三种：

计数排序（Counting Sort）
基数排序（Radix Sort）
桶排序（Bucket Sort）

这三种排序算法的特点是，它们依赖于数据的范围或结构，而非直接比较元素。

2. 计数排序（Counting Sort）

计数排序是一种基于元素范围的排序算法。它的主要思想是：通过统计每个元素在数据集中的出现次数，然后根据这些统计信息重新构造已排序的数组。计数排序适用于元素范围较小的情况。

2.1 算法步骤：

找到数据中最大和最小的元素，确定排序的范围。
创建一个计数数组，用于存储每个元素出现的次数。
根据计数数组来生成排序后的数组。

2.2 计数排序的复杂度：

时间复杂度：O(n + k)，其中n是元素数量，k是元素的范围。
空间复杂度：O(k)，计数数组的大小是k。

2.3 Java代码示例：

public class CountingSort {
    public static void countingSort(int[] arr) {
        int max = Integer.MIN_VALUE;
        // 找到数组中的最大值
        for (int num : arr) {
            max = Math.max(max, num);
        }
        
        // 创建计数数组，大小为最大值+1
        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);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

3. 基数排序（Radix Sort）

基数排序是一种通过逐位处理数字的排序算法。它将元素按位数分配到不同的桶中，每次处理一个位，直到所有位都处理完毕。基数排序适用于数字或其他类型的数据，并且它不依赖于比较操作。

3.1 算法步骤：

从最低位开始处理元素，按照该位的值将元素分配到不同的桶中。
对所有桶中的元素按位数排序，依次处理每一位，直到所有位都被处理。
最终，所有元素就被排序好了。

3.2 基数排序的复杂度：

时间复杂度：O(d * (n + b))，其中d是数字的位数，n是元素的数量，b是桶的数量（通常为10）。
空间复杂度：O(n + b)。

3.3 Java代码示例：

import java.util.*;

public class RadixSort {
    // 获取数字的最大位数
    public static int getMax(int[] arr) {
        int max = arr[0];
        for (int num : arr) {
            max = Math.max(max, num);
        }
        return max;
    }

    // 计数排序基于某一位
    public static void countSort(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10]; // 基数是10，表示十进制

        // 计算每个元素的出现次数
        for (int i = 0; i < n; i++) {
            count[(arr[i] / exp) % 10]++;
        }

        // 计算位置
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

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

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

    // 基数排序
    public static void radixSort(int[] arr) {
        int max = getMax(arr);

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

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

4. 桶排序（Bucket Sort）

桶排序是一种将数据分布到多个桶中，然后对每个桶内部的数据进行排序的算法。桶排序适用于数据服从均匀分布的情况。它的核心思想是：将元素分到若干个桶中，然后对每个桶内的元素进行排序，最后将各个桶的结果合并。

4.1 算法步骤：

根据数据的分布范围，创建多个桶。
将数据分配到对应的桶中。
对每个桶内的元素进行排序。
合并所有桶中的数据，得到最终排序结果。

4.2 桶排序的复杂度：

时间复杂度：O(n + k)，其中n是元素的数量，k是桶的数量（通常n与k相等）。
空间复杂度：O(n + k)。

4.3 Java代码示例：

import java.util.*;

public class BucketSort {
    public static void bucketSort(int[] arr) {
        if (arr.length <= 1) return;
        
        int max = Arrays.stream(arr).max().getAsInt();
        int min = Arrays.stream(arr).min().getAsInt();
        int bucketCount = (max - min) / arr.length + 1;
        
        // 创建桶
        List<Integer>[] buckets = new List[bucketCount];
        for (int i = 0; i < bucketCount; i++) {
            buckets[i] = new ArrayList<>();
        }
        
        // 将元素放入桶中
        for (int num : arr) {
            int index = (num - min) / arr.length;
            buckets[index].add(num);
        }

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

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

    public static void main(String[] args) {
        int[] arr = {4, 2, 3, 7, 6, 9, 1, 8, 5};
        bucketSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}