我正在使用动态数组 List
和ArrayList
类。我认为错误是 merge
方法,但我不知道哪里出了问题。我在 JS 和 Python 中使用了“相同”的代码,一切都按照预期进行。
import java.util.ArrayList;
import java.util.List;
public class mergeS {
private static List<Integer> numbers = new ArrayList<Integer>();
private static int lon = 8;
public static void main(String[] args) {
long start, end;
float time;
for(int i = 0; i < lon; i++) {
if(Math.random() < 0.5) {
numbers.add((int)(Math.random()*(100)));
}else {
numbers.add((int)(-1*Math.random()*(100)));
}
}
System.out.println("Unsorted list:\n"+numbers+"\n");
start = System.nanoTime();
mergeSort(numbers);
end = System.nanoTime();
time = (float) ((end-start)/Math.pow(10, 9));
System.out.println("Sorted list:\n"+numbers);
System.out.println("The time used was: "+time);
}
private static void mergeSort(List<Integer> numbers) {
if (numbers.size() < 2) {
return;
}
int mid = numbers.size() / 2;
List<Integer> left = numbers.subList(0, mid);
List<Integer> right = numbers.subList(mid, numbers.size());
mergeSort(left);
mergeSort(right);
merge(left, right, numbers);
}
private static void merge(List<Integer> left,
List<Integer> right,
List<Integer> numbers) {
int i = 0, j = 0, k = 0;
while(i < left.size() && j < right.size()) {
if(left.get(i) <= right.get(j)) {
numbers.set(k, left.get(i));
i++;
}else {
numbers.set(k, right.get(j));
j++;
}
k++;
}
while(i < left.size()) {
numbers.set(k, left.get(i));
i++;
k++;
}
while(j < right.size()) {
numbers.set(k, right.get(j));
j++;
k++;
}
}
}
最佳答案
您的代码很好,您只是错过了 List.subList
不会为您创建新对象。它仅返回对同一 numbers
数组的引用。一旦你更换了
List<Integer> left = numbers.subList(0, mid);
List<Integer> right = numbers.subList(mid, numbers.size());
与
List<Integer> left = new ArrayList<Integer>( numbers.subList( 0, mid ) );
List<Integer> right = new ArrayList<Integer>( numbers.subList( mid, numbers.size() ) );
一切都像魅力一样。
关于java - Java 中存在错误的合并排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59617614/