数据结构-排序之基数排序(使用java代码实现)
2021/5/30 20:53:30
本文主要是介绍数据结构-排序之基数排序(使用java代码实现),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前言
最近在学习数据结构的排序算法时,学到了基数排序。对于基数排序的算法的具体实现过程有了一定了解,但在具体实现的时候出现了一些小问题。在和同学讨论和查阅资料过后打算使用java代码将其实现出来。
基数排序
基数排序是桶排序(或箱排序)的优化算法,解决了桶排序对于差值过大的列表排序时造成的大量空间冗余。
基数排序是根据数位进行排序的,它从每个数的个位开始,将对应的数存入相应的桶中,然后从桶中顺序取出数进行排序,排序完成之后,进一位,从十位开始,重复上述步骤,直至将最大位数的数的最高位进行排序完毕,最后获得的数就会是顺序的了。
具体代码
排序部分
因为每一位的排序都是重复的,在不确定最大位数为多少时,我们无法确定需要进行几次存放数据的重复操作,所以嵌套了一个循环,循环进行最大位数的排序次数。
public static void radixSort(int[] arr) { //先求出数组中最大的数 int max = arr[0]; for (int i = 1; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } } //得到最大数是几位数 int maxLength = (max + "").length(); //定义一个二维数组,表示10个桶,每个桶就是一个数组 //为了在放入数时放置数据溢出,我们每个桶的大小为arr.length,即每个桶最多放进数组里的所有元素 int[][] bucket = new int[10][arr.length]; //定义一个一维数组来记录各个桶的每次放入的数据个数 int[] bucketElementCount = new int[10]; //根据最大的数有多少位进行遍历多少遍 for (int count = 0; count < maxLength; count++) { //第count+1轮:针对每个元素的个、十、百、千。。。位进行排序处理 for (int j = 0; j < arr.length; j++) { int digit = (int) Math.pow(10, count); //取出每个元素的个、十、百、千。。。位进行排序处理 int digitOfElement = arr[j] / (1 * digit) % 10; //放入到个位数对应的桶中 bucket[digitOfElement][bucketElementCount[digitOfElement]] = arr[j]; bucketElementCount[digitOfElement]++; } //按照一维数组的下标(即桶的顺序)依次取出数据,放入到原来数组 int index = 0; //遍历每一个桶,并将桶中数据放入到原数组 for (int k = 0; k < bucketElementCount.length; k++) { //如果桶中有数据,才放入原来数组 if (bucketElementCount[k] != 0) { for (int m = 0; m < bucketElementCount[k]; m++) { arr[index++] = bucket[k][m]; } } //第一轮处理后,需将bucketElementCount[k]=0 bucketElementCount[k] = 0; } System.out.println("第" + (count+1) + "轮, arr=" + Arrays.toString(arr)); } }
输入数组
java中不能直接通过手动输入整个数组,所以我写了一个方法,实现调用方法输入数组,并且可以控制输入的数组长度。
public static int[] scanArray() { Scanner scanner = new Scanner(System.in); System.out.println("\r请输入需要排序的数组的长度:"); int length = scanner.nextInt(); System.out.println("\r请输入每一位需要排序的数值:"); // 定义一个数组用于保存输入的数据 int[] arr = new int[length]; int digit = 1; int maxDigit = digit; for (int i = 0; i < arr.length; i++) { // 把数据按照从0开始的下标存入arr 数组 arr[i] = scanner.nextInt(); } return arr; }
实现排序
方法都封装完成后,我们就可以直接调用方法进行基数排序了
public static void main(String[] args) { int[] arr = scanArray(); radixSort(arr); }
运行结果:
总结
基数排序的时间复杂度一定是线性级别的,但是虽然是线性级别的,但是有一个系数的,这个系数就是最大元素的位数K,所以时间复杂度应该是O(n*k),空间复杂度主要就是取决于链表的数量以及序列元素的数量,所以空间复杂度为O(n+k)。
这篇关于数据结构-排序之基数排序(使用java代码实现)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求