java 基数排序

刺骨的言语ヽ痛彻心扉 2022-11-21 06:50 115阅读 0赞

--------------------

### java 基数排序 ###

### \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* ###

**基数排序**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzMTYyNQ_size_16_color_FFFFFF_t_70][]

**算法描述：基数排序为多关键字排序，**如**有关键字：k1、k2、k3，优先级：k1 >  k2 > k3**，**按关键字优先级从低到高排序，排序时先按k3排序、再按k2排序、最后按k1排序，所得的排序结果即为最终排序结果**

**空间复杂度：**o(n)

**时间复杂度：**o(n)

**算法稳定性：**基数排序是稳定排序算法

### \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* ###

**示例**

public class MyTest8 {
    
        public static int[] generate(int length){
            int[] a=new int[length];
    
            for (int i=0;i<=length-1;i++){
                a[i]=new Random().nextInt(1000);
            }
    
            return a;
        }
    
        public static void radixSort(int[] a){
            int length=a.length;
            int n=1;
    
            int len=0;
            for (int value : a) {
                if (len < (value + "").length()) {
                    len = (value + "").length();
                }
            }
    
            int[][] temp=new int[10][length-1];
            int[] index=new int[10];
    
            for (int i=0;i<len;i++){
                for (int value : a) {
                    int num = (value / n) % 10;
                    temp[num][index[num]++] = value;
                }
    
                int index2=0;
                for (int j=0;j<10;j++){
                    for (int k=0;k<index[j];k++){
                        a[index2++]=temp[j][k];
                    }
    
                    index[j]=0;
                }
    
                n*=10;
            }
        }
    
        public static void main(String[] args){
            int[] a=generate(10);
            System.out.println("数组排序前为：");
            Arrays.stream(a).forEach(i -> System.out.print(i+" "));
    
            radixSort(a);
            System.out.println("\n\n数组排序后：");
            Arrays.stream(a).forEach(i -> System.out.print(i+" "));
        }
    }

**控制台输出**

823 816 798 480 984 640 129 730 691 87 
    
    数组排序后：
    87 129 480 640 691 730 798 816 823 984

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzMTYyNQ_size_16_color_FFFFFF_t_70]: /images/20221120/d99e7419512d4afa8c22c23671770ea8.png