基数排序

基数排序(Radix Sort)是在桶排序的基础上发展而来的，两种排序都是分配排序的高级实现。

分配排序(Distributive Sort)的基本思想：排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶：O(n)。

基数排序代码：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    //static  int[] array = {7, 8, 9, 6, 1, 4, 3, 2, 5, 0, -1, -2,-3};
    static  int[] array = {7, 8, 9, 6, 1, 4, 3, 2, 5, 0,32,7,159,2,83,123,321,36};
    public static void main(String[] args) throws InterruptedException {
        System.out.println(Arrays.toString(array));
        radixSort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void radixSort(int[] array){

        int max = array[0];
        for(int i=0;i<array.length;i++){  //找到数组中的最大值
            if(array[i]>max){
                max = array[i];
            }
        }

        int keysNum = 0;  //关键字的个数，我们使用个位、十位、百位...当做关键字，所以关键字的个数就是最大值的位数
        while(max>0){
            max /= 10;
            keysNum++;
        }

        List<ArrayList<Integer>> buckets = new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<10;i++){  //每位可能的数字为0~9，所以设置10个桶
            buckets.add(new ArrayList<Integer>());  //桶由ArrayList<Integer>构成
        }

        for(int i=0;i<keysNum;i++){  //由最次关键字开始，依次按照关键字进行分配

            for(int j=0;j<array.length;j++){  //扫描所有数组元素，将元素分配到对应的桶中
                //取出该元素对应第i+1位上的数字，比如258，现在要取出十位上的数字，258%100=58,58/10=5
                int key =array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);
                buckets.get(key).add(array[j]);  //将该元素放入关键字为key的桶中
            }
            //buckets内有10子bucket,根据第i+1位上的数字分别存储在不同的bucket内
            //分配完之后，将桶中的元素依次复制回数组
            int counter = 0;  //元素计数器
            for(int j=0;j<10;j++){
                ArrayList<Integer> bucket =buckets.get(j);  //关键字为j的桶
                while(bucket.size()>0){
                    array[counter++] = bucket.remove(0);  //将桶中的第一个元素复制到数组，并移除
                }
            }
            System.out.print("第"+(i+1)+"轮排序：");
            display(array);
        }
    }

    public static void display(int[] array){
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]+"\t");
        }
        System.out.println();
    }
}      

[7, 8, 9, 6, 1, 4, 3, 2, 5, 0, 32, 7, 159, 2, 83, 123, 321, 36]
第1轮排序：0    1    321    2    32    2    3    83    123    4    5    6    36    7    7    8    9    159    
第2轮排序：0    1    2    2    3    4    5    6    7    7    8    9    321    123    32    36    159    83    
第3轮排序：0    1    2    2    3    4    5    6    7    7    8    9    32    36    83    123    159    321    
[0, 1, 2, 2, 3, 4, 5, 6, 7, 7, 8, 9, 32, 36, 83, 123, 159, 321]      

View Code

数组中不可以有负数。

第一步判断关键字的个数，这里的关键字就是个，十，百，获取最大值，就可以知道关键字的个数

第二步创建List数组buckets，有10个元素，每一个都是一个ArrayList类型的bucket

第三步根据关键字进行遍历，先根据数组array中元素的个位数的值，分别存储到buckets中对应的bucket

第四步将buckets中的值全部赋值给array,清空buckets中的每一个bucket，并根据关键字中的百进行下一步

第三步，第四步不停循环，直到关键字全部循环结束

最后即可发现数组array已经排好序。

复制的次数和数据项的个数与关键字长度成正比，关键字的长度越长，效率越低。