通用可比较合并排序算法的 Stackoverflow 错误

Question

我在排序方法中的合并排序调用中不断收到 Whosebug 错误。它可能是一个快速修复，但我现在想不出任何东西。请查看我的代码。

public class MergeSorter {

    public static <T> void sort(Comparable<? extends T>[] items) {
        if (items == null) {
            throw new IllegalArgumentException("Item is null.");
        }
        mergeSort(items, 0, items.length - 1);
    }

    @SuppressWarnings("unchecked")
    private static <T> void mergeSort(Comparable<? extends T>[] items, int begIndx, int endIndx) {
        if(begIndx == endIndx) {
            return;
        }
        if(items.length > 1) {
            int midIndx = items.length / 2;
            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;
        for (int k = begIndx; k <= endIndx; k++) {
            if (i == sizeOfLeft) {
                array[k] = (Comparable<? extends T>) rightArr[j++];
            } else if(j == sizeOfRight) {
                array[k] = (Comparable<? extends T>) leftArr[i++];
            } else if(((Integer) leftArr[i]).compareTo((Integer)rightArr[j]) <= 0) {
                array[k] = (Comparable<? extends T>) leftArr[i++];
            } else {
                array[k]=(Comparable<? extends T>) rightArr[j++];
            }
        }
    }

}

如果我给它一个包含 5 个元素的整数数组
5、24、79、8、3；

那我应该拿回3,5,8,24,79

Answer 1

你的问题是你的 mid-index 总是基于 items.length，每次调用都是一样的。

对于该调用，中间索引应该在 begIndx 和 endIndx 之间的中间位置，这很重要。

通用可比较合并排序算法的 Stackoverflow 错误

Stackoverflow error on generic comparable merge sort algorithm

java

stack-overflow

sorting

algorithm

mergesort