合并排序算法不起作用。不断收到 IndexOutOFBoundsError
。我认为问题可能是因为没有哨兵。当 leftarray
和 rightarray
将自身复制到 k
时,我需要创建一个循环,其中一个数组用完数字,这会导致错误。我需要一些帮助来创建这个哨兵。
private static <T> void mergeSort(Comparable<? extends T>[] items, int begIndx, int endIndx) {
if (items.length > 1) {
int midIndx = items.length / 2;
@SuppressWarnings("unchecked")
T[] left = (T[]) new Object[midIndx];
@SuppressWarnings("unchecked")
T[] right = (T[]) new Object[items.length - midIndx];
for (int i = 0; i < midIndx; i++) {
left[i] = (T) items[i];
}
for (int i = midIndx; i < items.length; i++) {
right[i] = (T) items[i];
}
mergeSort(items, begIndx, midIndx);
mergeSort(items, midIndx + 1, endIndx);
merge(items, begIndx, midIndx, endIndx);
}
}
@SuppressWarnings("unchecked")
private static <T> void merge(Comparable<? extends T>[] array,
int begIndx, int midIndx, int endIndx) {
int sizeOfLeft = midIndx - begIndx + 1;
int sizeOfRight = endIndx - midIndx;
/// change to generic later
@SuppressWarnings("unchecked")
T[] leftArr = (T[]) new Object[sizeOfLeft + 1];
@SuppressWarnings("unchecked")
T[] rightArr = (T[]) new Object[sizeOfRight + 1];
for (int i = 0; i < sizeOfLeft; i++) {
leftArr[i] = (T) array[begIndx + i];
}
for (int j = 0; j < sizeOfRight; j++) {
rightArr[j] = (T) array[midIndx + j + 1];
}
int i = 0;
int j = 0;
// changed to less than or equal to rather than "less than"
// this is because this is a zero based index system
// and because endeIndex is not a length but an index,
// you need to populate it.
for (int k = begIndx; k <= endIndx; k++) {
// use comparable here
if (((Integer) leftArr[i]).compareTo((Integer) rightArr[j]) <= 0) {
array[k] = (Comparable<? extends T>) leftArr[i];
i = i + 1;
} else if (((Integer) leftArr[i]).compareTo((Integer) rightArr[j]) >= 0) {
/// just replaces it so don't use comparable
array[k] = (Comparable<? extends T>) rightArr[j];
j = j + 1;
} else if ((Integer) leftArr[sizeOfLeft] == null) {
array[k] = (Comparable<? extends T>) rightArr[j];
j = j + 1;
} else if ((Integer) rightArr[sizeOfRight] == null) {
array[k] = (Comparable<? extends T>) leftArr[i];
i = i + 1;
}
}
}
我创建了一个整数数组arr = new Integer[5
]。所以这 5 个数字应该被排序。
最佳答案
您的代码中存在多个问题:
尚不清楚索引
endIndx
是否包含或排除。如果排除endIndx
,代码会简单得多,并且对数组进行排序的初始调用很简单:mergesort(arr, 0, arr.length);
mergesort
中的初始测试不正确:您应该测试切片是否包含超过 1 个元素,而不是测试数组长度:if (endIndx - begIndx > 1)
left
和right
数组在mergesort
中未使用。在
merge
中不需要在数组left
和right
中分配额外的元素,比较更简单数组索引值与子数组的长度。这种哨兵方法令人困惑,不应该使用。
这是一个简化版本:
private static <T> void mergeSort(Comparable<? extends T>[] items, int begIndx, int endIndx) {
if (endIndx - begIndx > 1) {
int midIndx = items.length / 2;
mergeSort(items, begIndx, midIndx);
mergeSort(items, midIndx, endIndx);
merge(items, begIndx, midIndx, endIndx);
}
}
@SuppressWarnings("unchecked")
private static <T> void merge(Comparable<? extends T>[] array,
int begIndx, int midIndx, int endIndx) {
int sizeOfLeft = midIndx - begIndx;
int sizeOfRight = endIndx - midIndx;
/// change to generic later
@SuppressWarnings("unchecked")
T[] leftArr = (T[]) new Object[sizeOfLeft];
@SuppressWarnings("unchecked")
T[] rightArr = (T[]) new Object[sizeOfRight];
for (int i = 0; i < sizeOfLeft; i++) {
leftArr[i] = (T)array[begIndx + i];
}
for (int j = 0; j < sizeOfRight; j++) {
rightArr[j] = (T)array[midIndx + j];
}
int i = 0;
int j = 0;
int k = begIndx;
while (i < sizeOfLeft && j < sizeOfRight) {
/// use comparable to compare actual values
if ((Integer)leftArr[i]).compareTo((Integer)rightArr[j]) <= 0) {
array[k] = (Comparable<? extends T>)leftArr[i];
i++;
k++;
} else {
array[k] = (Comparable<? extends T>)rightArr[j];
j++;
k++;
}
}
while (i < sizeOfLeft) {
array[k] = (Comparable<? extends T>)leftArr[i];
i++;
k++;
}
while (j < sizeOfRight) {
array[k] = (Comparable<? extends T>)rightArr[j];
j++;
k++;
}
}
关于java - 合并排序算法的问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56308120/