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

huangapple go评论62阅读模式
英文:

Radix Sort method works, but not sure if it's correct

问题

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

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]);
    }
}

结果:

10000
10000
10000
10000
10000
10000
10000
10000
10001
10001
10001
10001
10002
10002
...
99997
99997
99998
99998
99998
99998
99998
99998
99998
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
英文:

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:

10000
10000
10000
10000
10000
10000
10000
10000
10001
10001
10001
10001
10002
10002
...
99997
99997
99998
99998
99998
99998
99998
99998
99998
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999

huangapple
  • 本文由 发表于 2020年10月12日 00:23:29
  • 转载请务必保留本文链接:https://go.coder-hub.com/64306362.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定