算法与数据体系课笔记之- 9.桶排序、排序总结相关题目
2022/1/31 14:35:39
本文主要是介绍算法与数据体系课笔记之- 9.桶排序、排序总结相关题目,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
TOC
9.桶排序、排序总结相关题目分析 总览
笔记思维导图链接
算法与数据结构思维导图
参考左程云体系算法课程笔记
参考慕课网算法体系课程笔记
常见题目汇总:
题1:计数排序
题意
- 假设有n个样本数,数的范围是0-200,对这n个数进行排序
题解
- 范围小,故可以用计数排序,只需要准备200个桶,0-199,每个桶放一种样本数据,从小到大顺序
- 遍历一遍,将数据放到这200个桶类,再将200个桶依次倒出,就是最终排序的结果
代码实现
package class08; public class Code03_CountSort { // only for 0~200 value public static void countSort(int[] arr) { if (arr == null || arr.length < 2) { return; } // 1. 找出样本的最大值,确定需要多少个桶 int max = Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++) { max = Math.max(max, arr[i]); } // 2. 每个样本对应创建一个桶,统计每个样本的次数 int[] bucket = new int[max + 1]; for (int i = 0; i < arr.length; i++) { bucket[arr[i]]++; } // 3. 将桶按照顺序,依次导出样本,即最终排序结果 int i = 0; for (int j = 0; j < bucket.length; j++) { while (bucket[j]-- > 0) { arr[i++] = j; } } } }
复杂度分析
- 入桶,是O(n), 出桶也是O(n),故总的时间复杂度为O(n)
题2:基数排序
题意
- 数据非负,且为10进制。
- 例如最大数是321三位,将这些数进行排序
题解
- 先确定最大数是几位数,确定要处理几轮的入桶出桶操作
- 比如最大位是321,先处理个位数,按照个数数先排序,再处理十位、按照十位数值排序,最后处理第三位百位,最终排序的结果就是有序的
- 对于每次的入桶出桶可以优化,无需每次都要准备10个桶,装0-9种数,可以只准备两个辅助count,help
- count,统计每个数出现的次数,类似计数排序,count[2]表示2出现的次数
- count’,统计前几个数一共出现的次数,count’[2]表示0,1,2一共出现的次数
- help数组处理最后从右往左遍历要处理的数,count’[2]出现5次,表明最后一个数应该出现在4位置,放置后,减一次,用来处理下个该位是2的数
- 每轮将help的结果交给原数组arr,每轮arr就排好序了
代码实现
package class08; public class Code04_RadixSort { // only for no-negative value public static void radixSort(int[] arr) { if (arr == null || arr.length < 2) { return; } radixSort(arr, 0, arr.length - 1, maxbits(arr)); } // 1. 获取最大数的位数 public static int maxbits(int[] arr) { // 获取最大数 int max = Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++) { max = Math.max(max, arr[i]); } // 获取位数 int res = 0; while (max != 0) { res++; max /= 10; } return res; } // arr[L..R]排序 , 最大值的十进制位的位数digit public static void radixSort(int[] arr, int L, int R, int digit) { final int radix = 10; // 每次都准备10个桶处理每一位的数 int i = 0, j = 0; // 有多少个数准备多少个辅助空间 int[] help = new int[R - L + 1]; for (int d = 1; d <= digit; d++) { // 有多少位就进出几次 // 代码优化,省去10个桶,用两个数组count,count'来处理每次的进出操作 // 用count统计当前位的数,出现的次数,类似计数排序 int[] count = new int[radix]; // count[0..9] for (i = L; i <= R; i++) { // 遍历要处理的每个数 // 103 1 3 // 209 1 9 j = getDigit(arr[i], d); // 找出当前位的数 count[j]++; } // 处理count'数组,统计每个数应该占多少位,即count'[2]表示0,1,2一共出现的次数 for (i = 1; i < radix; i++) { count[i] = count[i] + count[i - 1]; } // 从右往左遍历,例如103,3一共出现了5次,则,103应该放在4位置 for (i = R; i >= L; i--) { j = getDigit(arr[i], d); help[count[j] - 1] = arr[i]; // count[j]出现的次数,表明要占j个位置,最后一个位置是j- 1 count[j]--; } // 对数组按照当前位进行排序,就是help数组最终放置的数的顺序 for (i = L, j = 0; i <= R; i++, j++) { arr[i] = help[j]; } } } // 获取第d位数的值 public static int getDigit(int x, int d) { return ((x / ((int) Math.pow(10, d - 1))) % 10); } }
复杂度分析
![在这里插入图片描述](/images/baidian.png)
这篇关于算法与数据体系课笔记之- 9.桶排序、排序总结相关题目的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-08如何在敏捷项目中实现高效测试?
- 2024-07-08用户故事一定要有 “So that...” 吗?
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt