[数据结构与算法]2021.10.19 Java数据结构基数排序作业

• 问题描述

在虚拟货币投机炒作时，不同概念版块会出现轮动，根据相关板块的市值排行变动可以一定程度上反映出当时的热点，所以进行排序后观察，可以更好的当韭菜。为了简便，将数字四舍五入化成整型。

• 数据结构

使用循环队列储存数据，使用基数排序。

• 算法思想

基数排序，获得一系列数字的最大位数m和进制d，用LSD从右至左依次检索每一位，获得该放入的桶的序号。（该序号在十进制下等于该数位的数值，其余进制可能不同）。

进行与数位相同次数的排序后得到正确结果。

• 代码实现

interface myQueue{
    public void append(Object obj)throws Exception;
    public Object delete() throws Exception;
    public Object getFront() throws Exception;
    public boolean notEmpty();
}

public class test {
    public static void main(String[] args)throws Exception{
        int[] targetNumbers={1111,10,1,1110};
        RadixSort aTest=new RadixSort();
        aTest.sort(targetNumbers,11,2);
    }
    }


class SeqQueue implements myQueue{
    static final int defaultSize=100;
    int front;
    int rear;
    int count;
    int maxSize;
    Object[] data;

    public SeqQueue(){
        initiate(defaultSize);
    }

    public SeqQueue(int size){
        initiate(size);
    }

    private void initiate(int size){
        maxSize=size;
        front=rear=0;
        count=0;
        data=new Object[size];
    }

    @Override
    public void append(Object obj) throws Exception {
        if(count>0&&rear==front){
            throw new Exception("队列已满");
        }

        data[rear]=obj;
        if (rear+1<maxSize) rear++;
        else  rear=(rear++)%maxSize;
        this.count++;
    }

    @Override
    public Object delete() throws Exception {
        if(count==0){
            throw new Exception("队列已空");
        }

        Object temp=data[front];
        if(front+1<maxSize) front++;
        else front=(front++)%maxSize;
        this.count--;
        return temp;
    }

    @Override
    public Object getFront() throws Exception{
        if(count==0){
            throw new Exception("队列已空");
        }
        return data[front];
    }

    @Override
    public boolean notEmpty(){
        return count!=0;
    }
}

class RadixSort{
    int numbersAmount;

    public void sort(int[] targetNumbers,int m,int d)throws Exception{
        final int DIGITNUMBER=m; //数字最高位数为m
        final  int BUCKETAMOUNT=d;//基数为d
        int power=1;
        numbersAmount=targetNumbers.length;
        SeqQueue[] bucket=new SeqQueue[BUCKETAMOUNT];
        int[] resultNumbers=new int[numbersAmount];
        for(int everyDigit=0;everyDigit<DIGITNUMBER;everyDigit++){  //一次控制对一位的操作
            if(everyDigit==0) power=1;
            else power*=BUCKETAMOUNT;
            for(int i=0;i<BUCKETAMOUNT;i++){  //创建基数个桶，存放数字
                bucket[i]=new SeqQueue();
            }
            int targetOrder=0;
            for(int i=0;i<numbersAmount;i++){
                int iDigitValue=targetNumbers[i]/power-(targetNumbers[i]/(power*BUCKETAMOUNT))*BUCKETAMOUNT;//获取每一位的值
                bucket[iDigitValue].append(targetNumbers[i]);
            }
            for(int j=0;j<BUCKETAMOUNT;j++){

                while (bucket[j].notEmpty()){
                    resultNumbers[targetOrder]=(int)bucket[j].getFront();
                    bucket[j].delete();
                    if(targetOrder+1<numbersAmount) targetOrder++;
                }
            }
            for(int i=0;i<numbersAmount;i++){   //将一次排序后的结果赋给targetNumbers数组，作为下一次排序的初始顺序
                targetNumbers[i]=resultNumbers[i];
            }
        }
        for(int i=0;i<numbersAmount;i++){  //输出排序后的结果
            System.out.println(targetNumbers[i]);
        }
    }
}

由于初学不久，技术水平有限，基数排序内容主体绝大部分都是自己完成，所以代码并不算很好，希望以后可以更加成熟。

注意：在输入测试样例的时候，如果输入的数字不是十进制，千万要注意转换成目标进制时位数可能与十进制不同，位数应按对应进制的，比如数字1111B，应该是十一位而非四位。