问题

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

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。

英文:

Is this how radix sort works? I tried it off the definition I know, works well and quick

import java.util.*;
import java.util.Arrays;
public class Radix {
static int [] Unsorted = new int [1000000];
ArrayList&lt;Integer&gt;[] Radix = new ArrayList[1000000];   
ArrayList&lt;Integer&gt;[] Radix2 = new ArrayList[1000000];   
ArrayList&lt;Integer&gt;[] Radix3 = new ArrayList[1000000];   
ArrayList&lt;Integer&gt;[] Radix4 = new ArrayList[1000000];   
ArrayList&lt;Integer&gt;[] Radix5 = new ArrayList[1000000];   
public void setLists(){
for(int i = 0; i &lt; Unsorted.length; i++){
Unsorted[i] = (int) ((Math.random() * 90000) + 10000);
Radix[i] = new ArrayList&lt;&gt;();
Radix2[i] = new ArrayList&lt;&gt;();
Radix3[i] = new ArrayList&lt;&gt;();
Radix4[i] = new ArrayList&lt;&gt;();
Radix5[i] = new ArrayList&lt;&gt;();
}
}
public void Radix(ArrayList&lt;Integer&gt;[] Radixes, int division){
for(int i = 0; i &lt; Unsorted.length; i++){
int temp = (Unsorted[i] / division) % 10;
Radixes[temp].add(Unsorted[i]);
}
this.set(Radixes);
}
public void set(ArrayList&lt;Integer&gt;[] Radixes){
int count = 0;
for (int i = 0; i &lt; Unsorted.length; i++) { 
for (int j = 0; j &lt; 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);
}

I know you're supposed to repeat it how many ever times the length of the largest number is, but I already know all the numbers will be of length 5

答案1

得分: 1

以下是翻译好的部分：

这段代码似乎能够工作，但你是否意识到你创建了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]);
    }
}

结果：

英文:

This code seems to work, but do you realize that you are creating 5 million ArrayList objects? How could that possibly be necessary? That's the biggest problem I see here. You only need 10 such lists, one for each digit 0-9. You don't even need 10 per radix position, as you can reuse the same list for each position.

I also renamed your identifiers that had uppercase first letters when they should have lowercase. Only your class name should be an uppercase word.

Here's your code with these two changes made, where an array of 10 lists is created on the fly for processing each radix position:

With these changes, I get the same sort of result, but without the gigantic amount of wasted memory of the initial version:

public class Radix {
static int[] unsorted = new int[1000000];
public void setLists() {
for (int i = 0; i &lt; unsorted.length; i++)
unsorted[i] = (int) ((Math.random() * 90000) + 10000);
}
public void radix(int division) {
ArrayList&lt;Integer&gt;[] radixLists = new ArrayList[10];
for (int i = 0 ; i &lt; radixLists.length ; i++)
radixLists[i] = new ArrayList&lt;&gt;();
for (int i = 0; i &lt; unsorted.length; i++) {
int temp = (unsorted[i] / division) % 10;
radixLists[temp].add(unsorted[i]);
}
this.set(radixLists);
}
public void set(ArrayList&lt;Integer&gt;[] radixLists) {
int count = 0;
for (int i = 0; i &lt; radixLists.length; i++) {
for (int j = 0; j &lt; 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 &lt; unsorted.length; i++)
System.out.println(unsorted[i]);
}
}

Result:

通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。

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

问题

答案1

Android：如何将单选按钮的文本设置为整数？

单向 vs 双向

权限拒绝在Android Studio中

如何在Java中使用这个C#语法示例？

What's the correct way to type hint an empty list as a literal in python?

如何在Highcharts Gantt中更改本地化的星期名称

如何在同一个流中使用多个过滤器和映射函数？

如何使用Map/Set来将代码优化到O(n)？

.NET MAUI Android在GitHub Actions上构建失败，错误代码为1。

如何在Playwright视觉比较中屏蔽多个定位器？

在C++中，可以使用可变模板参数来检索类型的内部类型。

selenium.common.exceptions.StaleElementReferenceException: Message: stale element reference: stale element not found

Creating and opening a URL to log in to Website via Basic Auth with Robot Framework/Selenium (Python)

AG Grid 在上下文菜单中以大文本形式打开

发表评论