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

基数排序就是这样工作的吗？我尝试了一下我知道的定义，效果很好，而且很快

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

这段代码似乎有效，但您是否意识到您正在创建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]);
}
}

结果：

相关内容

最新更新

热门标签：