非比较排序概念

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

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

计数排序（Counting Sort）：

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

桶排序（Bucket Sort）：

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

基数排序（Radix Sort）：

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

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

计数排序

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

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

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

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

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

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

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

代码实现： 

<code>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]--;

}

}

}

}

桶排序

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

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

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

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

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

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

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

<code>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 + " ");

}

}

}

代码说明：

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

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

基数排序

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

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

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

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

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

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

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

<code>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));

}

}

代码说明：

找到最大值：findMax 方法用来找到数组中的最大值，以确定需要进行多少次排序。按位排序：radixSort 方法从最低位开始，每次调用 countingSortByDigit 方法进行计数排序。计数排序实现：countingSortByDigit 方法中的步骤：

初始化一个计数数组 count，用于记录每个数字在当前位上的出现次数。统计每个数字对当前位的贡献并存储到计数数组中。根据计数数组生成输出数组，确保排序的稳定性。将输出数组中的元素复制回原数组中。测试代码：在 main 方法中定义一组整数，调用 radixSort 方法进行排序，并输出排序前后的结果。

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