黑马程序员技术交流社区

标题: 基数排序 [打印本页]

---

作者: 916040950    时间: 2015-3-16 08:47
标题: 基数排序

除了毕老师讲的选择，冒泡，插入三种排序，再给大家普及一个排序，希望大家能受益

基数排序

　　1、基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列

　　2、java实现

[url=][/url]
1 package com.sort; 2 3 import java.util.ArrayList; 4 import java.util.List; 5 //稳定 6 public class 基数排序 { 7     public static void main(String[] args) { 8         int[] a={49,38,65,97,176,213,227,49,78,34,12,164,11,18,1}; 9         System.out.println("排序之前：");10         for (int i = 0; i < a.length; i++) {11             System.out.print(a+" ");12         }13         //基数排序14         sort(a);15         System.out.println();16         System.out.println("排序之后：");17         for (int i = 0; i < a.length; i++) {18             System.out.print(a+" ");19         }20     }21 22     private static void sort(int[] array) {23         //找到最大数，确定要排序几趟24         int max = 0;25         for (int i = 0; i < array.length; i++) {26             if(max<array){27                 max = array;28             }29         }30         //判断位数31         int times = 0;32         while(max>0){33             max = max/10;34             times++;35         }36         //建立十个队列37         List<ArrayList> queue = new ArrayList<ArrayList>();38         for (int i = 0; i < 10; i++) {39             ArrayList queue1 = new ArrayList();40             queue.add(queue1);41         }42         //进行times次分配和收集43         for (int i = 0; i < times; i++) {44             //分配45             for (int j = 0; j < array.length; j++) {46                 int x = array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);47                 ArrayList queue2 = queue.get(x);48                 queue2.add(array[j]);49                 queue.set(x,queue2);50             }51             //收集52             int count = 0;53             for (int j = 0; j < 10; j++) {54                 while(queue.get(j).size()>0){55                     ArrayList<Integer> queue3 = queue.get(j);56                     array[count] = queue3.get(0);57                     queue3.remove(0);58                     count++;59                 }60             }61         }62     }63 }

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2