数据结构作业之用队列实现的基数排序（Java版）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构作业之用队列实现的基数排序（Java版），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3756字，纯文字阅读大概需要6分钟。
内容图文
题目：
利用队列实现对某一个数据序列的排序（采用基数排序），其中对数据序列的数据（第1和第2条进行说明）和队列的存储方式（第3条进行说明）有如下的要求：
1）当数据序列是整数类型的数据的时候，数据序列中每个数据的位数不要求等宽，比 如：
1、21、12、322、44、123、2312、765、56
2）当数据序列是字符串类型的数据的时候，数据序列中每个字符串都是等宽的，比 如：
"abc","bde","fad","abd","bef","fdd","abe"
3）要求重新构建队列的存储表示方法：使其能够将 n 个队列顺序映射到一个数组 listArray 中，每个队列都表示成内存中的一个循环队列【这一项是可选项】
基数排序思想：
以整数为例：先建立十个桶，编号为0-9。然后检测要排序的整数，
从各位数字开始，到数据中存在的最高的位数。根据每一位数字的值把所有要排序的整数放到对应数字的桶中。
比如，整数73 22 93 43 55 14 28 65 39 81。
第一趟：
第二趟：
如果要排序的数字中有更高的位数，必须多次排序。但是这样就比较花时间。所以对于位数相差较大的一串数字的排序，不建议采用基数排序。基数排序的时间复杂度为O（n）。空间复杂度为O（n+bucket）。bucket为桶的数目。故空间复杂度约等于O（n）。当每个桶之后的数字已知的时候，可以把储存基数排序的空间结构变成简单的一维数组。
队列：先进先出特性。push和pop分别入队出队。
具体实现代码：
1
//
Programming in Java
2
import java.util.*;
3 4publicclass radixSort {
5 6privatestaticfinal HashMap<Character, Integer> alphaToNum = new HashMap();
7 8static {
9 alphaToNum.clear();
10 initAlpha2Num(‘A‘, ‘Z‘, alphaToNum);
11 initAlpha2Num(‘a‘, ‘z‘, alphaToNum);
12 13 }
14 15privatestaticfinalvoid initAlphaToNum(char c1, char c2, HashMap<Character, Integer> map) {
16for (char c = c1; c <= c2; c++)
17 map.put(c, map.size());
18 }
19 20publicstaticvoid main(String[] args) {
21 radixSort sortInstance = new radixSort();
22int[] data = { 1, 4, 3, 3, 21, 12, 322, 44, 123, 2312, 765, 56, 8978, 10000, 14, 28, 65, 39, 81, 33, 100, 567 };
23 String[] data2 = { "abc", "Bde", "fad", "abd", "Bef", "fdd", "abe" };
24 sortInstance.sort(data);
25 sortInstance.sort(data2);
26 27 print(data);
28 print(data2);
29 }
30 31publicstaticvoid print(String[] data) {
32for (int i = 0; i < data.length; i++)
33 System.out.print(data[i] + " ");
34 System.out.println();
35 }
36 37publicstaticvoid print(int[] data) {
38for (int i = 0; i < data.length; i++)
39 System.out.print(data[i] + " ");
40 System.out.println();
41 }
42 43publicvoid sort(int[] a) {
44int N = 10;
45 ArrayList<Queue<Integer>> qArray;
46 qArray = new ArrayList();
47for (int i = 0; i < N; i++)
48 qArray.add(new<Integer> LinkedList());// 开辟空间 49int max = Integer.MIN_VALUE;
50for (int i = 0; i < a.length; i++)
51 max = Integer.max(max, a[i]);
52int[] length = newint[N];// 记录qArray的原始长度，防止对元素重复操作
53// radix sort 54for (int i = 0; i < a.length; i++)
55 qArray.get(a[i] % 10).offer(a[i]);// 1 step 56for (int j = 10; j <= max; j *= 10) {
57for (int i = 0; i < N; i++)
58 length[i] = qArray.get(i).size(); // 2 step update length 59for (int i = 0; i < N; i++) {
60 Queue<Integer> q = qArray.get(i);
61while (length[i]-- > 0) {
62int num = q.poll();
63 qArray.get((num / j) % 10).offer(num);
64 }
65 }
66 }
67for (int i = 0, AIndex = 0; i < N; i++) // finally 68while (qArray.get(i).size() > 0)
69 a[AIndex++] = qArray.get(i).poll();
70 }
71 72publicvoid sort(String[] s) {
73int N = alphaToNum.size();
74 ArrayList<Queue<String>> qArray;
75 qArray = new ArrayList();
76for (int i = 0; i < N; i++)
77 qArray.add(new<String> LinkedList());// 开辟空间 78int strLen = s[0].length();
79int[] length = newint[N];// forbid duplicate operation for (int i = 0; i < s.length; i++) 80 qArray.get(alphaIndex(s[i].charAt(s[i].length() - 1))).offer(s[i]);
81for (int j = strLen - 1; j > 0; j--) {
82for (int i = 0; i < N; i++)
83 length[i] = qArray.get(i).size();
84for (int i = 0; i < N; i++) {
85 Queue<String> q = qArray.get(i);
86while (length[i]-- > 0) {
87 String str = q.poll();
88 qArray.get(alphaIndex(str.charAt(j - 1))).offer(str);
89 }
90 }
91 }
92for (int i = 0, AIndex = 0; i < N; i++) // finally 93while (qArray.get(i).size() > 0)
94 s[AIndex++] = qArray.get(i).poll();
95 }
96 97privateint alphaIndex(char c) {
98return alphaToNum.get(c);
99 }
100 }
ps：阿爸的代码
原文：http://www.cnblogs.com/yueyiviolet/p/6035189.html
内容总结
以上是互联网集市为您收集整理的数据结构作业之用队列实现的基数排序（Java版）全部内容，希望文章能够帮你解决数据结构作业之用队列实现的基数排序（Java版）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。