【校招VIP】Java实现基数排序算法详解及优化

01月09日 收藏 0 评论 0 java开发

【校招VIP】Java实现基数排序算法详解及优化

转载声明:文章来源https://blog.csdn.net/qq_40254606/article/details/140535438


引言

基数排序(Radix Sort)是一种非比较型整数排序算法,通过将整数按位进行排序来实现。它具有稳定、高效的特点,特别适用于大规模数据的排序。本文将详细讲解如何使用Java实现基数排序算法,并结合图解和实例代码,帮助您全面理解这一高级排序算法。同时,我们还将进行时间复杂度分析,并探讨基数排序的优化方法,以进一步提高其性能。

基数排序算法的原理

基数排序通过按位排序,从最低位到最高位(或从最高位到最低位)逐步进行,最终得到有序数组。它通常使用计数排序作为子过程来实现按位排序。

算法步骤

1.确定最大数的位数:找到数组中最大数的位数。

2.按位排序:从最低位开始,对数组进行多次排序,每次按当前位进行排序。

图解基数排序

为了更清晰地展示基数排序的过程,以下使用一个简单示例并分步骤图解:

Java实现基数排序

import java.util.Arrays;

public class RadixSort {
/**
* 获取数组中的最大值
* @param arr 待排序的数组
* @return 最大值
*/
private static int getMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}

/**
* 计数排序,用于对每个位进行排序
* @param arr 待排序的数组
* @param exp 当前位的指数
*/
private static void countSort(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n]; // 输出数组
int[] count = new int[10]; // 计数数组,表示0-9的频率

// 初始化计数数组
Arrays.fill(count, 0);

// 计数每个位出现的次数
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);
}

/**
* 基数排序
* @param arr 待排序的数组
*/
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);
// 输出排序后的数组
System.out.println("排序后的数组:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}


时间复杂度分析

原始基数排序

基数排序的时间复杂度主要取决于以下两个因素:

1.数组中的元素个数 (n)。

2.数组中最大元素的位数 (d)。

在每一位上的排序我们通常使用计数排序,它的时间复杂度为 (O(n + k)),其中 (k) 是计数排序的范围。在基数排序中,我们需要对 (d) 位进行排序,因此总的时间复杂度为 O(d⋅(n+k))。对于常见的情况,计数排序的范围 (k) 是一个常数(通常是10),所以时间复杂度可以简化为 O(d⋅n)。

优化后的基数排序

优化后的基数排序可以通过以下几种方式提高性能:

1.减少无效操作:避免对零元素进行多余的操作。

2.并行化处理:利用多线程或并行计算的方式,提高排序速度。

尽管有这些优化措施,基数排序的时间复杂度在最优情况下仍然是 O(d⋅n)。优化的目标主要是降低常数因子,提高实际运行速度。

图解优化后的基数排序

Java实现优化后的基数排序

import java.util.Arrays;
import java.util.concurrent.RecursiveAction;
import java.util.concurrent.ForkJoinPool;

public class OptimizedRadixSort {
/**
* 获取数组中的最大值
* @param arr 待排序的数组
* @return 最大值
*/
private static int getMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}

/**
* 计数排序,用于对每个位进行排序
* @param arr 待排序的数组
* @param exp 当前位的指数
*/
private static void countSort(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n]; // 输出数组
int[] count = new int[10]; // 计数数组,表示0-9的频率

// 初始化计数数组
Arrays.fill(count, 0);

// 计数每个位出现的次数
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);
}

/**
* 基数排序
* @param arr 待排序的数组
*/
public static void radixSort(int[] arr) {
// 找到数组中的最大数,确定位数
int max = getMax(arr);

// 使用ForkJoinPool进行并行处理
ForkJoinPool pool = new ForkJoinPool();


pool.invoke(new ParallelRadixSort(arr, 1, max));
}

/**
* 并行处理的基数排序任务
*/
private static class ParallelRadixSort extends RecursiveAction {
private final int[] arr;
private final int exp;
private final int max;

public ParallelRadixSort(int[] arr, int exp, int max) {
this.arr = arr;
this.exp = exp;
this.max = max;
}

@Override
protected void compute() {
if (max / exp > 0) {
countSort(arr, exp);
// 继续处理下一位
ParallelRadixSort nextTask = new ParallelRadixSort(arr, exp * 10, max);
nextTask.fork();
nextTask.join();
}
}
}

public static void main(String[] args) {
// 初始化数组
int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
// 调用优化后的基数排序方法
radixSort(arr);
// 输出排序后的数组
System.out.println("排序后的数组:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}


结论

通过上述讲解和实例代码,我们详细展示了如何在Java中实现基数排序算法,并结合图解说明了其工作原理。同时,我们对基数排序的时间复杂度进行了分析,并提供了优化后的代码和图解,展示了如何通过并行化处理提高基数排序的性能。

C 0条回复 评论

帖子还没人回复快来抢沙发