Java数据结构和算法-基数排序-白红宇

Java数据结构和算法-基数排序

阅读量：2443 次

发布时间：2019-05-10

本文共 1071 字，大约阅读时间需要 3 分钟。

基数排序：

基数排序(Radix Sort)是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。

具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

步骤：首先求出该序列最高位数，例如本例最高位百位，计数count=3

1. 按照个位数进行排序。

2. 按照十位数进行排序。

3. 按照百位数进行排序。

排序后，数列就变成了一个有序序列。

基数排序Java实现：

package com.algorithm.sort;import java.util.ArrayList;public class BasicSort {    public static void main(String[] args) {        int[] a={34,2,4,5,7,45,44,12,145,347,47,556,78,67,55,89,10,23};        basicSort(a);        for(int num:a){            System.out.print(" "+num);        }    }    private static void basicSort(int[] a) {        int max=0;        int count=0;        //求该数组最大数，以便求出最大位数        for(int i=0;i
   
     listOut=new ArrayList
    
     ();        for(int i=0;i<10;i++){            ArrayList listInner=new ArrayList();            listOut.add(listInner);        }        for(int i=0;i
     
      0){//注意循环                    a[c++]=(int)listOut.get(m).remove(0);                }            }        }    }}输出： 2 4 5 7 10 12 23 34 44 45 47 55 67 78 89 145 347 556

各种排序时间复杂度总结：

你可能感兴趣的文章