java中带有数组列表的arraylist合并排序
因此,作为家庭作业,我必须编写一个程序,将常规数组代码中的排序与数组列表合并,我只是想知道是否有人能帮我找出哪里出了问题,因为我的代码抛出了大量空指针异常,我试着修复它们,但当我修复一个时,它会转到另一个。。。等等
谢谢! 我的代码:
private static ArrayList<Integer> numbers= new ArrayList<Integer>();
private static ArrayList<Integer> helper;
private static int number;
public static void sort(ArrayList<Integer> myNumbers){
for(int i=0; i<myNumbers.size();i++){
numbers.add(myNumbers.get(i));
}
//numbers=myNumbers;
number = myNumbers.size()-1;
mergesort(0, number -1);
}
private static void mergesort(int low, int high){
//check if low is smaller than high, if not then the array is sorted
if(low<high){
//get the index of the element which is in the middle
int middle=low+(high-low)/2;
//sort the left side of the array
mergesort(low, middle);
//sort the right side of the array
mergesort(middle +1, high);
//combine them both
merge(low, middle, high);
}
}
private static void merge(int low, int middle, int high){
//copy both parts into the helper array
for(int i=high;i>low;i++){
helper.add((numbers.get(i)));
}
int i=low;
int j=middle+1;
int k=low;
//copy the smallest myNumbers from either the left or right side back to the original array
while(i<middle && j<high){
if(helper.get(i)< helper.get(j)){
numbers.set(k,(helper.get(i)));
i++;
}
else{
numbers.set(k,(helper.get(j)));
j++;
}
k++;
}
//copy the rest of the left side of the array into target array
while(i<middle){
numbers.set(k,helper.get(i));
k++;
i++;
}
}
返回:
Exception in thread "main" java.lang.NullPointerException
at BinarySearch.merge(BinarySearch.java:61)
at BinarySearch.mergesort(BinarySearch.java:55)
at BinarySearch.mergesort(BinarySearch.java:51)
at BinarySearch.mergesort(BinarySearch.java:51)
at BinarySearch.mergesort(BinarySearch.java:51)
at BinarySearch.mergesort(BinarySearch.java:51)
at BinarySearch.mergesort(BinarySearch.java:51)
at BinarySearch.mergesort(BinarySearch.java:51)
at BinarySearch.sort(BinarySearch.java:43)
at BinarySearch.main(BinarySearch.java:25)
# 1 楼答案
blackuprise指出了你的两个问题
合并实现还有另一个问题,可能会导致合并结果出错。在合并方法结束时,您有:
你怎么能这么确定每次数组的右边都会被合并,只有左边的部分还有元素?(奇怪的句子^ ^左半部分有剩余。)
你也应该检查一下右边。或者使用
SENTINEL
来避免“rest”检查# 2 楼答案
如果你试图用你的算法实现一个合并排序,用于学术用途,而给出的答案是一个好的答案,或者如果你对Guava已有的实现感兴趣,那么它就是:guava Iterators
# 3 楼答案
它试图访问未创建的合并函数中的帮助器字段
此外,我认为应该从所有函数/字段中删除static关键字
私有静态ArrayList助手
到
private static ArrayList helper=new ArrayList()
# 4 楼答案
罪魁祸首是:
改用
for(int i=high; i>=low; i--) {
# 5 楼答案
公共课合并