java - 基数排序方法有效，但不确定它是否正确

问题描述

这是基数排序的工作原理吗？我根据我知道的定义尝试了它，效果很好而且很快

import java.util.*;
import java.util.Arrays;
public class Radix {
static int [] Unsorted = new int [1000000];
ArrayList<Integer>[] Radix = new ArrayList[1000000];   
ArrayList<Integer>[] Radix2 = new ArrayList[1000000];   
ArrayList<Integer>[] Radix3 = new ArrayList[1000000];   
ArrayList<Integer>[] Radix4 = new ArrayList[1000000];   
ArrayList<Integer>[] Radix5 = new ArrayList[1000000];   
public void setLists(){
    for(int i = 0; i < Unsorted.length; i++){
        Unsorted[i] = (int) ((Math.random() * 90000) + 10000);
        Radix[i] = new ArrayList<>();
        Radix2[i] = new ArrayList<>();
        Radix3[i] = new ArrayList<>();
        Radix4[i] = new ArrayList<>();
        Radix5[i] = new ArrayList<>();
    }
}
public void Radix(ArrayList<Integer>[] Radixes, int division){
    for(int i = 0; i < Unsorted.length; i++){
        int temp = (Unsorted[i] / division) % 10;
        Radixes[temp].add(Unsorted[i]);
    }
    this.set(Radixes);
}
public void set(ArrayList<Integer>[] Radixes){
    int count = 0;
    for (int i = 0; i < Unsorted.length; i++) { 
        for (int j = 0; j < Radixes[i].size(); j++) {
            Unsorted[count] = Radixes[i].get(j);
            count++;
        }
    }
}
public void RadixSort(){
    Radix(Radix, 1);
    Radix(Radix2, 10);
    Radix(Radix3, 100);
    Radix(Radix4, 1000);
    Radix(Radix5, 10000);
}

我知道你应该重复它多少次最大数字的长度，但我已经知道所有数字的长度都是 5

标签： java

这段代码似乎有效，但您是否意识到您正在创建 500 万个 ArrayList 对象？这怎么可能是必要的？这是我在这里看到的最大问题。您只需要 10 个这样的列表，每个数字 0-9 一个。您甚至不需要每个基数位置 10 个，因为您可以为每个位置重复使用相同的列表。

我还重命名了你的标识符，当它们应该有小写时，它们的首字母大写。只有您的班级名称应该是大写单词。

这是您进行这两项更改的代码，其中动态创建了一个包含 10 个列表的数组，用于处理每个基数位置：

通过这些更改，我得到了相同的结果，但没有初始版本浪费的大量内存：

public class Radix {
    static int[] unsorted = new int[1000000];

    public void setLists() {
        for (int i = 0; i < unsorted.length; i++)
            unsorted[i] = (int) ((Math.random() * 90000) + 10000);
    }

    public void radix(int division) {
        ArrayList<Integer>[] radixLists = new ArrayList[10];
        for (int i = 0 ; i < radixLists.length ; i++)
            radixLists[i] = new ArrayList<>();
        for (int i = 0; i < unsorted.length; i++) {
            int temp = (unsorted[i] / division) % 10;
            radixLists[temp].add(unsorted[i]);
        }
        this.set(radixLists);
    }

    public void set(ArrayList<Integer>[] radixLists) {
        int count = 0;
        for (int i = 0; i < radixLists.length; i++) {
            for (int j = 0; j < radixLists[i].size(); j++) {
                unsorted[count] = radixLists[i].get(j);
                count++;
            }
        }
    }

    public void radixSort() {
        radix(1);
        radix(10);
        radix(100);
        radix(1000);
        radix(10000);
    }

    public static void main(String[] args) {
        Radix test = new Radix();
        test.setLists();
        test.radixSort();
        for (int i = 0; i < unsorted.length; i++)
            System.out.println(unsorted[i]);
    }
}

结果：

java - 基数排序方法有效，但不确定它是否正确

问题描述

解决方案

推荐阅读