链式基数排序 对整数序列进行排序


题:
低关键字优先的基数排序算法很有创新。
请对整数序列进行排序。
随机产生1000个整数,其中整数的范围0~9999
可以用十进制的每个位为关键字。排序时使用十个动态数组为临时空间,进行分配和收集。
采用低关键字优先的基数排序完成对整数序列的排序任务。
注意体会仅仅依靠分配、收集的手段即可完成排序。

源码LSDSorting.java


import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class LSDSorting {
    @SuppressWarnings({ "rawtypes", "unchecked" })
    public static void main(String[] args) {
        Random rd = new Random();
        List<Integer> ls = new ArrayList<Integer>();
        for (int i=0; i<1000; i++) {
            ls.add(rd.nextInt(10000));
        }
    //  System.out.println(ls);
        
        ArrayList<ArrayList> x = new ArrayList<ArrayList>();
        
        for (int k=1; k<10000; k*=10) {
            x.clear();
            for (int i=0; i<10; i++) {
                x.add(new ArrayList<Integer>());
            }
            for (int i=0; i<1000; i++) {
                int t = ls.get(i);
                int n = t/k%10;
                x.get(n).add(t);
            }
            ls.clear();
            for (int i=0; i<10; i++) {
                ls.addAll(x.get(i));
            }
        }
        
    //  System.out.println(ls.size());
        for (int i=0; i<10; i++) {
            System.out.println(x.get(i));
        }
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注