合并排序算法问题

Question

MergeSorting 算法不工作。继续得到一个IndexOutOFBoundsError。我相信问题可能是因为没有哨兵。leftarray当andrightarray将自身复制到时，我需要创建一个循环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;

        } 

        }

    }

}

我创建了一个整数数组arr = new Integer[5]。所以应该对这 5 个数字进行排序。

Answer 1

您的代码中存在多个问题：目前尚不清楚该指数endIndx是被包括还是被排除在外。如果排除了 ，代码会简单得多endIndx，对数组进行排序的初始调用很简单：mergesort(arr, 0, arr.length);中的初始测试mergesort不正确：您应该测试切片是否有超过 1 个元素，而不是测试数组长度：if&nbsp;(endIndx&nbsp;-&nbsp;begIndx&nbsp;>&nbsp;1)数组left和right未在mergesort.left不需要在数组和rightin中分配额外的元素，merge将数组索引值与子数组的长度进行比较要简单得多。这种哨兵方法令人困惑，不应使用。这是一个简化版本：private static <T> void mergeSort(Comparable<? extends T>[] items, int begIndx, int endIndx) {&nbsp; &nbsp; if (endIndx - begIndx > 1) {&nbsp; &nbsp; &nbsp; &nbsp; int midIndx = items.length / 2;&nbsp; &nbsp; &nbsp; &nbsp; mergeSort(items, begIndx, midIndx);&nbsp; &nbsp; &nbsp; &nbsp; mergeSort(items, midIndx, endIndx);&nbsp; &nbsp; &nbsp; &nbsp; merge(items, begIndx, midIndx, endIndx);&nbsp; &nbsp; }}@SuppressWarnings("unchecked")private static <T> void merge(Comparable<? extends T>[] array,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int begIndx, int midIndx, int endIndx) {&nbsp; &nbsp; int sizeOfLeft = midIndx - begIndx;&nbsp; &nbsp; int sizeOfRight = endIndx - midIndx;&nbsp; &nbsp; /// change to generic later&nbsp; &nbsp; @SuppressWarnings("unchecked")&nbsp; &nbsp; T[] leftArr = (T[]) new Object[sizeOfLeft];&nbsp; &nbsp; @SuppressWarnings("unchecked")&nbsp; &nbsp; T[] rightArr = (T[]) new Object[sizeOfRight];&nbsp; &nbsp; for (int i = 0; i < sizeOfLeft; i++) {&nbsp; &nbsp; &nbsp; &nbsp; leftArr[i] = (T)array[begIndx + i];&nbsp; &nbsp; }&nbsp; &nbsp; for (int j = 0; j < sizeOfRight; j++) {&nbsp; &nbsp; &nbsp; &nbsp; rightArr[j] = (T)array[midIndx + j];&nbsp; &nbsp; }&nbsp; &nbsp; int i = 0;&nbsp; &nbsp; int j = 0;&nbsp; &nbsp; int k = begIndx;&nbsp; &nbsp; while (i < sizeOfLeft && j < sizeOfRight) {&nbsp; &nbsp; &nbsp; &nbsp; /// use comparable to compare actual values&nbsp; &nbsp; &nbsp; &nbsp; if ((Integer)leftArr[i]).compareTo((Integer)rightArr[j]) <= 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; array[k] = (Comparable<? extends T>)leftArr[i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; k++;&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; array[k] = (Comparable<? extends T>)rightArr[j];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; k++;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; while (i < sizeOfLeft) {&nbsp; &nbsp; &nbsp; &nbsp; array[k] = (Comparable<? extends T>)leftArr[i];&nbsp; &nbsp; &nbsp; &nbsp; i++;&nbsp; &nbsp; &nbsp; &nbsp; k++;&nbsp; &nbsp; }&nbsp; &nbsp; while (j < sizeOfRight) {&nbsp; &nbsp; &nbsp; &nbsp; array[k] = (Comparable<? extends T>)rightArr[j];&nbsp; &nbsp; &nbsp; &nbsp; j++;&nbsp; &nbsp; &nbsp; &nbsp; k++;&nbsp; &nbsp; }}