合并排序算法问题

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 (endIndx - begIndx > 1)

• 数组left和right未在mergesort.

• left不需要在数组和rightin中分配额外的元素，merge将数组索引值与子数组的长度进行比较要简单得多。这种哨兵方法令人困惑，不应使用。

这是一个简化版本：

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++;

    }

}