好程序员Java学习路线分享5分钟了解基数排序,前言:基数排序无需进行比较和交换,而是利用分配和收集两种基本操作实现排序。基数排序分为两种:第一种是LSD ,从最低位开始排序;第二种是 MSD, 从最高位开始排序。

基数排序思想介绍

  1. 分配:对于数字,每位的取值范围是0-9,因此需要10个容器(我们可以将其称为桶),这10个桶标号为0-9。每趟排序时,我们取每一个元素在该位的数值依次放入桶中。

2. 收集:在一趟排序完成后,我们按顺序从0-9的桶中依次取元素。

3. 继续进行分配和收集,直到最大位数排序完成。

算法说明:

待排序数据:12, 34, 2, 123, 25, 59, 37

采用LSD,从低位开始排序

第一轮:取个位数,放入对应的桶,比如12的个位数是2,放到2号桶;34的个位数是4,放到4号桶

第一轮后,得到数据:12, 2, 123, 34, 25, 37, 59

第二轮:取十位数,放入桶中。比如2,十位数是0,放到0号桶

好程序员Java学习路线分享5分钟了解基数排序-LMLPHP

第二轮后,得到数据:2, 12, 123, 25, 34, 37, 59

第三轮:取百位数,放入桶

好程序员Java学习路线分享5分钟了解基数排序-LMLPHP

最后,得到有序数据 2, 12, 25, 34, 37, 59, 123

基数排序的代码实现

  1. private static void radixSort(int[] arr) {  
  2. //存储最大值,暂时记录为第一个元素  
  3. int max = arr[0];  
  4. //获取待排序数组中的最大值  
  5. for (int v : arr) {  
  6. if (v > max) {  
  7. max = v;  
  8. }  
  9. }  
  10. // 用列表表示桶,一共10个桶,每个桶对应的元素也是列表  
  11. List<List<Integer>> list = new ArrayList<List<Integer>>();  
  12. for(int i  = 0; i < 10; i ++) {  
  13. list.add(new ArrayList<Integer>());  
  14. }  
  15. // 确定循环轮数  
  16. for(int i = 0, factor = 1; i < max; factor *= 10, i ++) {  
  17. for(int j = 0; j < arr.length; j ++) {  
  18. // 根据相应的位(个位/十位...)取通号,然后将数据放入桶中  
  19. list.get((arr[j] / factor) % 10).add(arr[j]);  
  20. }  
  21. // 遍历桶,将其中数据放入arr数组中  
  22. for(int j = 0, k = 0; j < list.size(); j ++) {  
  23. while(!list.get(j).isEmpty()) {  
  24. arr[k] = list.get(j).get(0);  
  25. list.get(j).remove(0);  
  26. k++;  
  27. }  
  28. }  
  29. }  
  30. }   

总结

基数排序是一种按记录关键字的各位值逐步进行排序的方法。一般适用于记录的关键字为整数类型的情况,对于字符串和文字排序不适合。

08-07 18:26