黑马程序员技术交流社区
标题: 基数排列 [打印本页]
作者: 916040950 时间: 2015-3-16 08:32
标题: 基数排列
除了毕老师讲的选择,冒泡,插入三种排序,再给大家普及一个排序,希望大家能受益
基数排序
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 }
作者: 温暖的小白 时间: 2015-3-16 08:48
赞一个!
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |