基数排序算法及优化（java）

2024-08-27 18:12
文章标签 java 算法 优化 基数排序

本文主要是介绍基数排序算法及优化（java），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

1.1 引言

1.2 基数排序的历史

1.3 基数排序的基本原理

1.3.1 基数排序的过程

1.3.2 基数排序算法流程

1.4 基数排序的Java实现

1.4.1 简单实现

1.4.2 代码解释

1.4.3 使用场景

1.4.4 实际应用案例

1.5 基数排序的时间复杂度

1.6 基数排序的空间复杂度

1.7 基数排序的稳定性

1.8 基数排序的优化方案

1.8.1 并行处理

1.8.2 减少空间占用

1.8.3 Java示例代码

1.8.4 代码解释

1.9 总结

1.1 引言

基数排序是一种非比较排序算法，适用于整数或字符串等类型的排序。它通过对整数按位进行排序来达到整个数组排序的目的。基数排序通常分为两种类型：最低有效位（Least Significant Digit, LSD）排序和最高有效位（Most Significant Digit, MSD）排序。本文将详细介绍基数排序的工作原理，并通过具体案例来阐述其应用。此外，还将探讨基数排序的不同优化方案，并给出相应的Java代码示例。

1.2 基数排序的历史

基数排序的思想可以追溯到19世纪末期，最早是由Harold H. Seward在1954年的论文中提出的。随着时间的发展，基数排序因其简单高效的特点成为了计算机科学中一个重要的排序算法之一。

基数排序之所以重要，是因为它可以在O(d(n+k)) 的时间内完成排序，其中 d 是数字的位数，n 是数组的长度，k 是基数（通常是10）。这种时间复杂度使得基数排序非常适合处理大规模数据集，尤其是在数据的位数较少的情况下。

1.3 基数排序的基本原理

1.3.1 基数排序的过程

基数排序的基本过程包括以下几个主要步骤：

  1. 确定数字的位数：找到数组中最大的数字，以此来确定位数。
  2. 按位排序：从最低位开始，依次对每一位进行排序。
  3. 稳定排序：使用一种稳定的排序算法（如计数排序）来处理每一位上的数字。

1.3.2 基数排序算法流程

  1. 确定数字的位数：找到数组中最大的数字，以此来确定位数。
  2. 按位排序：从最低位开始，依次对每一位进行排序。
  3. 稳定排序：使用计数排序来处理每一位上的数字。
  4. 重复步骤2和3：直到所有位都被排序过为止。

1.4 基数排序的Java实现

1.4.1 简单实现

下面是一个简单的基数排序Java代码示例，其中包含了详细的注释和说明：

1import java.util.Arrays;
2
3/**
4 * 基数排序类，用于实现基数排序算法。
5 */
6public class RadixSort {
7
8    /**
9     * 打印数组中的元素。
10     *
11     * @param array 需要打印的数组
12     */
13    private static void printArray(int[] array) {
14        for (int value : array) {
15            System.out.print(value + " ");
16        }
17        System.out.println();
18    }
19
20    /**
21     * 基数排序方法。
22     *
23     * @param array 需要排序的数组
24     */
25    public static void radixSort(int[] array) {
26        // 确定最大值
27        int max = findMax(array);
28        // 按位进行排序
29        for (int exp = 1; max / exp > 0; exp *= 10) {
30            countingSortByDigit(array, exp);
31        }
32    }
33
34    /**
35     * 按照特定位数进行计数排序。
36     *
37     * @param array 需要排序的数组
38     * @param exp   当前位数的基数
39     */
40    private static void countingSortByDigit(int[] array, int exp) {
41        int n = array.length;
42        int[] output = new int[n]; // 输出数组
43        int[] count = new int[10]; // 计数数组
44
45        // 计数
46        for (int i = 0; i < n; i++) {
47            int index = (array[i] / exp) % 10;
48            count[index]++;
49        }
50
51        // 累计入数
52        for (int i = 1; i < 10; i++) {
53            count[i] += count[i - 1];
54        }
55
56        // 输出排序后的数组
57        for (int i = n - 1; i >= 0; i--) {
58            int index = (array[i] / exp) % 10;
59            output[count[index] - 1] = array[i];
60            count[index]--;
61        }
62
63        // 复制排序后的数组回原数组
64        System.arraycopy(output, 0, array, 0, n);
65    }
66
67    /**
68     * 查找数组中的最大值。
69     *
70     * @param array 数组
71     * @return 最大值
72     */
73    private static int findMax(int[] array) {
74        int max = array[0];
75        for (int value : array) {
76            if (value > max) {
77                max = value;
78            }
79        }
80        return max;
81    }
82
83    /**
84     * 主方法，用于测试基数排序算法。
85     */
86    public static void main(String[] args) {
87        int[] array = {170, 45, 75, 90, 802, 24, 2, 66};
88        System.out.println("原始数组:");
89        printArray(array);
90
91        radixSort(array);
92
93        System.out.println("排序后的数组:");
94        printArray(array);
95    }
96}import java.util.Arrays;/*** 基数排序类，用于实现基数排序算法。*/
public class RadixSort {/*** 打印数组中的元素。** @param array 需要打印的数组*/private static void printArray(int[] array) {for (int value : array) {System.out.print(value + " ");}System.out.println();}/*** 基数排序方法。** @param array 需要排序的数组*/public static void radixSort(int[] array) {// 确定最大值int max = findMax(array);// 按位进行排序for (int exp = 1; max / exp > 0; exp *= 10) {countingSortByDigit(array, exp);}}/*** 按照特定位数进行计数排序。** @param array 需要排序的数组* @param exp   当前位数的基数*/private static void countingSortByDigit(int[] array, int exp) {int n = array.length;int[] output = new int[n]; // 输出数组int[] count = new int[10]; // 计数数组// 计数for (int i = 0; i < n; i++) {int index = (array[i] / exp) % 10;count[index]++;}// 累计入数for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}// 输出排序后的数组for (int i = n - 1; i >= 0; i--) {int index = (array[i] / exp) % 10;output[count[index] - 1] = array[i];count[index]--;}// 复制排序后的数组回原数组System.arraycopy(output, 0, array, 0, n);}/*** 查找数组中的最大值。** @param array 数组* @return 最大值*/private static int findMax(int[] array) {int max = array[0];for (int value : array) {if (value > max) {max = value;}}return max;}/*** 主方法，用于测试基数排序算法。*/public static void main(String[] args) {int[] array = {170, 45, 75, 90, 802, 24, 2, 66};System.out.println("原始数组:");printArray(array);radixSort(array);System.out.println("排序后的数组:");printArray(array);}
}

1.4.2 代码解释

  • 确定数字的位数：找到数组中最大的数字，以此来确定位数。
  • 按位排序：从最低位开始，依次对每一位进行排序。
  • 稳定排序：使用计数排序来处理每一位上的数字。

1.4.3 使用场景

基数排序适用于以下情况：

  • 数据范围有限：如果数组中的元素取值范围很小，基数排序可以非常高效。
  • 数据量大：对于大规模数据集，尤其是当数据的位数相对较小的时候，基数排序可以提供非常快的排序速度。
  • 需要稳定排序：基数排序是一种稳定的排序算法，适用于需要保持相同元素相对顺序的情况。

1.4.4 实际应用案例

案例描述：假设我们有一个包含100000个整数的数组，这些整数的范围在1到10000之间。我们需要快速地对这些整数进行排序。

解决方案：使用基数排序可以有效地解决这个问题。

  1. 确定数字的位数：找到数组中最大的数字，以此来确定位数。
  2. 按位排序：从最低位开始，依次对每一位进行排序。
  3. 稳定排序：使用计数排序来处理每一位上的数字。

具体步骤：

  1. 确定数字的位数：找到数组中最大的数字，以此来确定位数。
  2. 按位排序：从最低位开始，依次对每一位进行排序。
  3. 稳定排序：使用计数排序来处理每一位上的数字。

效果：由于基数排序的时间复杂度为O(d(n+k))，并且在这种情况下 k 和 d 相对较小，因此它可以快速完成排序任务。

1.5 基数排序的时间复杂度

基数排序的时间复杂度主要由按位排序和稳定排序两部分组成。

  • 按位排序：每一轮排序的时间复杂度为 O(n+k)。
  • 稳定排序：使用计数排序作为稳定排序算法的时间复杂度为O(n+k)。

因此，基数排序的整体时间复杂度为O(d(n+k))，其中 d 是数字的位数，n 是数组的长度，k 是基数（通常是10）。

基数排序的时间复杂度可以通过分析按位排序和稳定排序的过程得出。按位排序的时间复杂度基于输入数组的长度和基数，而稳定排序的时间复杂度同样基于输入数组的长度和基数。

1.6 基数排序的空间复杂度

基数排序的空间复杂度为O(n+k)，其中 n 是数组的长度，k 是基数。

1.7 基数排序的稳定性

基数排序是一种稳定的排序算法。这意味着相同元素的相对顺序在排序过程中不会发生改变。

1.8 基数排序的优化方案

1.8.1 并行处理

通过多线程或分布式计算可以提高基数排序的速度。

1.8.2 减少空间占用

如果元素的取值范围很大，可以考虑使用更紧凑的数据结构来减少空间占用。

1.8.3 Java示例代码

下面是一个考虑了更多优化因素的基数排序Java代码示例，其中包含了详细的注释和说明：

import java.util.Arrays;/*** 基数排序类，用于实现基数排序算法。*/
public class RadixSortOptimized {/*** 打印数组中的元素。** @param array 需要打印的数组*/private static void printArray(int[] array) {for (int value : array) {System.out.print(value + " ");}System.out.println();}/*** 基数排序方法。** @param array 需要排序的数组*/public static void radixSort(int[] array) {// 确定最大值int max = findMax(array);// 按位进行排序for (int exp = 1; max / exp > 0; exp *= 10) {countingSortByDigit(array, exp);}}/*** 按照特定位数进行计数排序。** @param array 需要排序的数组* @param exp   当前位数的基数*/private static void countingSortByDigit(int[] array, int exp) {int n = array.length;int[] output = new int[n]; // 输出数组int[] count = new int[10]; // 计数数组// 计数for (int i = 0; i < n; i++) {int index = (array[i] / exp) % 10;count[index]++;}// 累计入数for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}// 输出排序后的数组for (int i = n - 1; i >= 0; i--) {int index = (array[i] / exp) % 10;output[count[index] - 1] = array[i];count[index]--;}// 复制排序后的数组回原数组System.arraycopy(output, 0, array, 0, n);}/*** 查找数组中的最大值。** @param array 数组* @return 最大值*/private static int findMax(int[] array) {int max = array[0];for (int value : array) {if (value > max) {max = value;}}return max;}/*** 主方法，用于测试基数排序算法。*/public static void main(String[] args) {int[] array = {170, 45, 75, 90, 802, 24, 2, 66};System.out.println("原始数组:");printArray(array);radixSort(array);System.out.println("排序后的数组:");printArray(array);}
}

1.8.4 代码解释

  • 确定数字的位数：找到数组中最大的数字，以此来确定位数。
  • 按位排序：从最低位开始，依次对每一位进行排序。
  • 稳定排序：使用计数排序来处理每一位上的数字。
  • 优化：在这个版本中，我们减少了不必要的循环，并使用了数组复制方法来简化代码。

1.9 总结

基数排序是一种非比较排序算法，适用于整数或字符串等类型的排序。通过合理选择按位排序和稳定排序的方法，可以大大提高基数排序的效率。无论是在理论研究还是实际工程中，基数排序都是一个值得深入了解的重要算法。

这篇关于基数排序算法及优化（java）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1112399。

相关文章

Vue3 的 shallowRef 和 shallowReactive：优化性能

Vue3 的 shallowRef 和 shallowReactive：优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉，那么对 shallowRef 和 shallowReactive 是否了解呢？ 在编程和数据结构中，“shallow”（浅层）通常指对数据结构的最外层进行操作，而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素，而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层（Shallow） 定义
阅读更多...
JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
HDFS—存储优化（纠删码）

HDFS—存储优化（纠删码）

纠删码原理 HDFS 默认情况下，一个文件有3个副本，这样提高了数据的可靠性，但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码，采用计算的方式，可以节省约50％左右的存储空间。 此种方式节约了空间，但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件，都会执行此策略。 默认只开启对 RS-6-3-1024k
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2