【排序算法】Java实现三大非比较排序：计数排序、桶排序、基数排序

非比较排序概念

非比较排序是一种排序算法，它不通过比较元素之间的大小关系来进行排序，而是基于元素的特征或属性进行排序。这种方法在特定情况下可以比比较排序方法（如快速排序、归并排序等）更有效率，尤其是在处理大量数据时。非比较排序通常要求输入数据满足一定的条件，或者对数据的特征进行合理的利用。

常见的非比较排序算法包括：

1. 计数排序（Counting Sort）：

   • 适用于范围较小的整数排序。通过统计每个元素出现的次数，然后将元素按顺序放入结果数组。

2. 桶排序（Bucket Sort）：

   • 将数据分到若干个桶中，随后对每个桶中的数据进行排序，最后再将所有桶中的数据合并在一起。

3. 基数排序（Radix Sort）：

   • 通过将待排序的数值按位数分组，逐位进行排序，通常配合计数排序实现。

非比较排序的时间复杂度通常可以达到 O(n) ，但它们一般要求算法的输入数据具有特定的特征，且通常是稳定的排序算法。非比较排序的优势在于在适当的条件下，它可以显著提高排序的效率。

计数排序

计数排序是一种非比较型的排序算法，适用于特定条件下的排序，尤其是当待排序的元素范围较小且其重复元素较多时。它的基本原理是利用一个额外的数组来记录每个元素出现的次数，从而达到排序的目的。以下是计数排序的原理步骤：

1. 确定范围：首先确定待排序数组中元素的值的范围，找到最大值和最小值。

2. 创建计数数组：根据范围创建一个计数数组，数组的大小通常为最大值与最小值的差加一，用于存放每个元素的出现次数。

3. 计数：遍历原始数组，对每个元素在计数数组中对应的位置进行计数。即，若元素为 x，则计数数组的第 x 位置的值加一。

4. 计算位置：通过累加计数数组的值，得到每个元素在已排序数组中的最终位置。这一步实际上是将计数数组转换为位置数组。

5. 排序输出：根据计数数组生成已排序数组。遍历计数数组，按次数将对应的元素输出到结果数组中。

计数排序的时间复杂度为 O(n + k)，其中 n 是待排序元素的数量，k 是计数数组的大小。因其效率较高，通常适用于待排序数据范围较小的情况。

代码实现： 

public class CountSort {public static void sort(int[] array) {int minVal = array[0];int maxVal = array[0];//遍历数组找到最小值和最大值for (int i = 1; i < array.length; i++) {if(array[i] < minVal) {minVal = array[i];}if(array[i] > maxVal) {maxVal = array[i];}}//构建计数数组int[] count = new int[maxVal-minVal+1];for (int i = 0; i < array.length; i++) {count[array[i]-minVal]++;}int index = 0;//将计数数组中的元素还原到原数组中for (int i = 0; i < count.length; i++) {while (count[i] > 0) {array[index] = i + minVal;index++;count[i]--;}}}
}

桶排序

桶排序是一种基于分桶思想的排序算法，适用于数据分布比较均匀的情况。它的基本原理是将待排序的元素分散到一定数量的“桶”里，每个桶内部再进行排序，最后将所有桶中的元素合并在一起。以下是桶排序的具体步骤：

1. 创建桶：根据待排序数据的范围和数量，创建一定数量的桶。每个桶的范围可以根据数据的分布情况进行划分。

2. 分配元素：将待排序的元素逐一放入相应的桶中。每个元素根据其值决定放入哪个桶。例如，如果某个桶的范围是 [a, b)，那么落在这个范围内的元素就会放入该桶。

3. 排序桶内元素：对每个非空的桶内部进行排序。可以使用其他排序算法（如插入排序、快速排序等）对每个桶内的元素进行排序。

4. 合并桶：将排序好的每个桶中的元素按顺序合并成一个新的有序数组，完成整个排序过程。

桶排序的时间复杂度通常为 O(n)，最佳情况发生在数据均匀分布时，但在最坏情况下，时间复杂度可以退化为 O(n^2)，当所有元素都落在同一个桶中时。桶排序的空间复杂度为 O(n + k)，其中 n 是待排序元素的数量，k 是桶的数量。

总的来说，桶排序在适合的场景下能提供非常优秀的性能，尤其是在处理大量数据时具有明显优势。

import java.util.ArrayList;
import java.util.Collections;public class BucketSort {// 主排序方法public static void bucketSort(float[] arr) {// 如果数组为空或只有一个元素，直接返回if (arr == null || arr.length <= 1) {return;}// 1. 找出数组中的最大值和最小值float maxValue = arr[0];float minValue = arr[0];for (float num : arr) {if (num > maxValue) {maxValue = num;}if (num < minValue) {minValue = num;}}// 2. 计算桶的数量int bucketCount = (int) Math.floor(maxValue - minValue) + 1; // 桶的数量ArrayList<ArrayList<Float>> buckets = new ArrayList<>(bucketCount);// 3. 初始化每个桶for (int i = 0; i < bucketCount; i++) {buckets.add(new ArrayList<>()); // 创建一个空的桶}// 4. 将元素分配到桶中for (float num : arr) {int bucketIndex = (int) (num - minValue); // 计算索引buckets.get(bucketIndex).add(num); // 将元素放入对应的桶中}// 5. 对每个桶内部进行排序并合并int index = 0; // 记录排序后的数组的索引for (ArrayList<Float> bucket : buckets) {Collections.sort(bucket); // 使用 Collections.sort() 对桶内部元素进行排序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.51f, 0.32f};System.out.println("原始数组:");for (float num : arr) {System.out.print(num + " ");}// 调用桶排序bucketSort(arr);System.out.println("\n排序后的数组:");for (float num : arr) {System.out.print(num + " ");}}
}

代码说明：

1. 桶的创建：首先确定待排序数组的最大值和最小值，然后根据这个范围创建相应数量的桶。
2. 元素分配：遍历原始数组，将每个元素放入对应的桶中，桶的索引由元素的值与最小值的差决定。
3. 桶内排序：对每个桶内部进行排序，这里使用了 Java 提供的 Collections.sort() 方法。
4. 合并结果：将每个桶中排序后的元素放回原数组。

运行上述代码，可以验证桶排序的功能，并输出原始数组与排序后的数组。

基数排序

基数排序是一种非比较型的排序算法，主要用于整数排序，但也可以扩展到字符串等数据类型。它的基本原理是将待排序的数值分解成不同的位数，然后按位进行排序，通常使用稳定的排序算法（如计数排序）对每一位进行排序。以下是基数排序的基本步骤：

1. 确定最大位数：首先找出待排序数据中最大数的位数，以确定需要进行多少轮排序。

2. 从低到高位排序：从最低位开始，对所有数字进行排序。在每一轮中，将所有数字按照当前位的值分配到对应的桶中，然后再依次收集在一起。这个过程使用稳定的排序算法来保证相同数字的相对顺序不变。

3. 重复进行：对每一位重复排序，直到最高位。

4. 得到最终排序结果：经过多次按位排序后，所有元素会按照升序排列。

基数排序的时间复杂度为 O(n * k)，其中 n 是待排序的元素数量，k 是最大数字的位数。基数排序的空间复杂度为 O(n + k)，主要用于存放桶和临时数组。

基数排序特别适合处理大量数据且范围不是特别大的整数，能够在特定条件下达到很高的效率。

import java.util.Arrays;public class RadixSort {// 基数排序主方法public static void radixSort(int[] arr) {// 1. 找到最大值，以确定排序的位数int max = findMax(arr);// 2. 对每一位进行排序for (int exp = 1; max / exp > 0; exp *= 10) {countingSortByDigit(arr, exp);}}// 找到数组中的最大值private static int findMax(int[] arr) {int max = arr[0];for (int num : arr) {if (num > max) {max = num;}}return max;}// 根据当前位进行计数排序private static void countingSortByDigit(int[] arr, int exp) {int n = arr.length;int[] output = new int[n]; // 输出数组int[] count = new int[10]; // 计数数组，范围是 0-9// 1. 初始化计数数组Arrays.fill(count, 0);// 2. 统计每个数字在当前位（exp）上的出现次数for (int i = 0; i < n; i++) {int digit = (arr[i] / exp) % 10; // 取出当前位的数字count[digit]++;}// 3. 计算每个元素的最终位置for (int i = 1; i < 10; i++) {count[i] += count[i - 1]; // 计算累计频率}// 4. 从后往前填充输出数组，保证稳定性for (int i = n - 1; i >= 0; i--) {int digit = (arr[i] / exp) % 10; // 取出当前位的数字output[count[digit] - 1] = arr[i]; // 放置到输出数组count[digit]--; // 减少计数}// 5. 将排序好的数据复制回原数组System.arraycopy(output, 0, arr, 0, n);}// 测试代码public static void main(String[] args) {int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};System.out.println("原始数组:");System.out.println(Arrays.toString(arr));// 调用基数排序radixSort(arr);System.out.println("排序后的数组:");System.out.println(Arrays.toString(arr));}
}

代码说明：

1. 找到最大值：findMax 方法用来找到数组中的最大值，以确定需要进行多少次排序。
2. 按位排序：radixSort 方法从最低位开始，每次调用 countingSortByDigit 方法进行计数排序。
3. 计数排序实现：countingSortByDigit 方法中的步骤：
   • 初始化一个计数数组 count，用于记录每个数字在当前位上的出现次数。
   • 统计每个数字对当前位的贡献并存储到计数数组中。
   • 根据计数数组生成输出数组，确保排序的稳定性。
   • 将输出数组中的元素复制回原数组中。
4. 测试代码：在 main 方法中定义一组整数，调用 radixSort 方法进行排序，并输出排序前后的结果。

运行上述代码可以验证基数排序的功能，并观察原始数组与排序后的数组。