桶式排序与基数排序举例及JAVA代码实现(附:基数排序的方法给英文字符串排序)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了桶式排序与基数排序举例及JAVA代码实现(附:基数排序的方法给英文字符串排序),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含5326字,纯文字阅读大概需要8分钟。
内容图文
![桶式排序与基数排序举例及JAVA代码实现(附:基数排序的方法给英文字符串排序)](/upload/InfoBanner/zyjiaocheng/1332/9e20e996d1df47fd96ea7f979ece1756.jpg)
桶号 | 1 | 2 | 3 | 4 | 5 |
计数 | 1 | 1 | 2 | 0 | 1 |
桶的倒出顺序 | 数字队列 |
5号桶倒出1个5 | 5 |
4号桶倒出0个4 | 5 |
3号桶倒出2个3 | 5,3,3 |
2号桶倒出1个2 | 5,3,3,2 |
1号桶倒出1个1 | 5,3,3,2,1 |
// 桶式排序 public class BucketSort{ public static void main(String[] args){ int[] a = {2,4,15,11,6,3,7,19,8,5,4}; sort(a,19); } //桶式排序函数 //a是要排序的数组 //max是最大数字(这里我们默认数字最小为0)publicstaticvoid sort(int[] a,int max){ //声明一个数组,这就是桶,编号从0到max的桶,一共max+1个int[] count = newint[max + 1]; //遍历数组,用桶计数for(int i = 0;i < a.length;i++){ count[a[i]]++; } //将桶里面的数字倒出for(int i = max;i > 0;i--){ while(count[i] > 0){ System.out.print(i + " "); count[i]--; } } } }
桶号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
存放数字 | 11 | 23,73,3 | 314,1234 | 35,5 | 9 |
桶的倒出顺序 | 数字队列 |
9 | 9 |
8 | 9 |
7 | 9 |
6 | 9 |
5 | 9,35,5 |
4 | 9,35,5,314,1234 |
3 | 9,35,5,314,1234,23,73,3 |
2 | 9,35,5,314,1234,23,73,3 |
1 | 9,35,5,314,1234,23,73,3,11 |
0 | 9,35,5,314,1234,23,73,3,11 |
桶号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
存放数字 | 9,5,3 | 314,11 | 23 | 35,1234 | 73 |
桶的倒出顺序 | 数字队列 |
9 | |
8 | |
7 | 73 |
6 | 73 |
5 | 73 |
4 | 73 |
3 | 73,35,1234 |
2 | 73,35,1234,23 |
1 | 73,35,1234,23,314,11 |
0 | 73,35,1234,23,314,11,9,5,3 |
桶号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
存放数字 | 73,35,23,11,9,5,3 | 1234 | 314 |
桶的倒出顺序 | 数字队列 |
9 | |
8 | |
7 | |
6 | |
5 | |
4 | |
3 | 314 |
2 | 314,1234 |
1 | 314,1234 |
0 | 314,1234,73,35,23,11,9,5,3 |
桶号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
存放数字 | 314,73,35,23,11,9,5,3 | 1234 |
桶的倒出顺序 | 数字队列 |
9 | |
8 | |
7 | |
6 | |
5 | |
4 | |
3 | |
2 | |
1 | 1234 |
0 | 1234,314,73,35,23,11,9,5,3 |
public class RadixSort{ public static void main(String[] args){ // 声明要排序的数组 int[] data = {73,22,93,867494,43,55,123,8978,10000,14,28,65,39,81,33,100,567}; //调用基数排序函数 sort(data,10); //输出排序后的数组for(int i = 0;i < data.length;i++){ System.out.print(data[i] + " "); } } ///基数排序函数 //a表示要排序的数组 //d表示每一位数字的范围(这里是10进制数,有0~9一共10种情况)publicstaticvoid sort(int[] a,int d){ //n用来表示当前排序的是第几位int n = 1; //hasNum用来表示数组中是否有至少一个数字存在第n位boolean hasNum = false; //二维数组temp用来保存当前排序的数字 //第一维d表示一共有d个桶 //第二维a.length表示每个桶最多可能存放a.length个数字int[][] temp = newint[d][a.length]; int[] order = newint[d]; while(true){ //判断是否所有元素均无比更高位,因为第一遍一定要先排序一次,所以有n!=1的判断if(n != 1 && !hasNum){ break; } hasNum = false; //遍历要排序的数组,将其存入temp数组中(按照第n位上的数字将数字放入桶中)for(int i = 0;i < a.length;i++){ int x = a[i]/(n*10); if(x != 0){ hasNum = true; } int lsd = (x%10); temp[lsd][order[lsd]] = a[i]; order[lsd]++; } //k用来将排序好的temp数组存入data数组(将桶中的数字倒出)int k = 0; for(int i = 0;i < d;i++){ if(order[i] != 0){ for(int j = 0;j < order[i];j++){ a[k] = temp[i][j]; k++; } } order[i] = 0; } n++; } } }
public class RadixSort_Letter{ public static void main(String[] args){ // 声明要排序的数组 String[] a = {"ac","ee","ef","b","z","f","ep","gaaa","azh","az","r"}; //调用基数排序函数 sort(a,4); //输出排序后的数组for(int i = a.length - 1;i >= 0;i--){ System.out.print(a[i] + " "); } } ///基数排序函数 //a是要排序的数组 //m表示数组元素最高位数,如我们排序的数组中位数最高的元素为gaaa,有4位publicstaticvoid sort(String[] a,int m){ int n = 0; //27表示每一位字符分成27类,其中1~26对应‘a‘~‘z‘ //第0位专门用来存放没有高位字符的数组元素,如在比较第二位字符时,b,z,f等没有第二位字符的元素就存在temp[0]中 //相对应的,ac存在temp[1]中,ef存在temp[5]中 String[][] temp = new String[27][a.length]; int[] order = newint[27]; while(n < m){ //这里声明String类型的数组b,将数组a中的每个元素倒序,然后放入数组b //如a[0]="abc",则b[0]="cba" //之所以这样做,是为了解决下面调用charAt方法时索引的问题,脑子太笨,没想到更好的方法 String[] b = new String[a.length]; for(int i = 0;i < a.length;i++){ if(a[i].length() > 1){ StringBuffer sb = new StringBuffer(a[i]); sb.reverse(); b[i] = new String(sb); }else{ b[i] = a[i]; } } for(int i = 0;i < a.length;i++){ if(a[i].length() > n){ int lsd = b[i].charAt(n) - ‘a‘ + 1; temp[lsd][order[lsd]] = a[i]; order[lsd]++; }else{ temp[0][order[0]] = a[i]; order[0]++; } } int k = 0; for(int i = 0;i < 27;i++){ for(int j = 0;j < order[i];j++){ a[k] = temp[i][j]; k++; } order[i] = 0; } n++; } } }
原文:http://www.cnblogs.com/bigfatxixi/p/3597004.html
内容总结
以上是互联网集市为您收集整理的桶式排序与基数排序举例及JAVA代码实现(附:基数排序的方法给英文字符串排序)全部内容,希望文章能够帮你解决桶式排序与基数排序举例及JAVA代码实现(附:基数排序的方法给英文字符串排序)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。