我正在尝试合并排序列表,但获取ArrayoutOfBoundsRor,但无法修复它。
这是用于使用比较器接口的通用列表目前我正在运行整数测试。
这是我的合并排序类:
public class ListMS<T> {
private List<T> wholeList;
private Comparator<T> comparator;
public ListMS(List<T> list, Comparator<T> C){
wholeList=new ArrayList<>();
wholeList.addAll(list);
comparator=C;
mergeSort(wholeList, comparator);
}
public static <T> void merge(List<T> L1, List<T> L2,List<T> L, Comparator<T> C){
int i=0;
int j=0;
while(i+j<L.size()){
if(j==L2.size() || (i<L.size() && C.compare(L1.get(i),L2.get(j))<0)){
L.set(i+j,L1.get(i++));
}
else{
L.set(i+j,L2.get(j++));
}
}
}
public static <T> void mergeSort(List<T> L, Comparator<T> C){
int size=L.size();
if(size<2){
return;
}
int half=size/2;
List<T> L1=L.subList(0,half);
List<T> L2=L.subList(half,size);
mergeSort(L1,C);
mergeSort(L1,C);
merge(L1,L2,L,C);
}
public List<T> getWholeList(){
return wholeList;
}
}
我用的是:
public static void main(String[] args) {
Comparator<Integer> C=new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1.compareTo(o2);
}
};
List<Integer> list1K=generateList(1000);
ListMS<Integer> list1KMerged=new ListMS<>(list1K, C);
printList(list1K);
printList(list1KMerged.getWholeList());
}
public static List<Integer> generateList(int size){
List<Integer> listNumber=new ArrayList<>();
for(int i=0;i<size;i++){
int min=0;
int max=size-1;
int num=(int)(Math.random() * ((max - min) + 1)) + min;
listNumber.add(num);
}
return listNumber;
}
public static void printList(List<Integer> L){
for(int i=0;i<L.size();i++){
System.out.print(L.get(i));
}
}
但我得到了多个边界:
线程“main”java.lang.IndexOutboundsException:索引中的异常:
1,尺寸:1 at
java.util.ArrayList$SubList.rangeCheck(ArrayList.java:1225)位于
java.util.ArrayList$SubList.get(ArrayList.java:1042)位于
ListMS.merge(ListMS.java:19)位于ListMS.mergeSort(ListMS.java:40)位于
ListMS.mergeSort(ListMS.java:37)上的ListMS.mergeSort(ListMS.java:37)
在ListMS.mergeSort(ListMS.java:37)上
ListMS.mergeSort(ListMS.java:37)上的ListMS.mergeSort(ListMS.java:37)
在listms.mergesort(listms.java:37)上
ListMS.mergeSort(ListMS.java:37)上的ListMS.mergeSort(ListMS.java:37)
在listms.(listms.java:11)在
TestListMS.main(TestListMS.java:16)
最佳答案
基本上,这一行merge()methid中的循环计数器出错:
if(j == L2.size() || (i < L.size() && C.compare(L1.get(i), L2.get(j)) < 0))
因此修改合并函数,它将工作:
public static <T> void merge(List<T> L1, List<T> L2,List<T> L, Comparator<T> C){
int i=0;
int j=0;
int k=0;
while(i < L1.size() && j < L2.size()) {
if(C.compare(L1.get(i), L2.get(j)) < 0) {
L.set(k++, L1.get(i++));
}else {
L.set(k++, L2.get(j++));
}
}
while(i < L1.size()) {
L.set(k++, L1.get(i++));
}
while(j < L2.size()) {
L.set(k++, L2.get(j++));
}
}
更新:
mergeSort函数中也有多个错误更改为:
public static <T> void mergeSort(List<T> L, Comparator<T> C){
int size=L.size();
if(size<2){
return;
}
int half=size/2;
List<T> L1=new ArrayList<T>(L.subList(0,half));
List<T> L2=new ArrayList<T>(L.subList(half,size));
mergeSort(L1,C);
mergeSort(L2,C);
merge(L1,L2,L,C);
printList(L);
}
L1和L2不是旧代码中的新数组列表它们只是指向列表l中相同内存位置的两个指针,所以在merge函数中修改l也修改了l1和l2。为了解决这个问题,您需要创建两个具有不同内存分配的新子阵列。
另外,您调用了
mergeSort(L1,C);
两次,而不是分别在L1和L2上调用它。