java - 我的就地堆排序代码有什么问题

Question

我正在做一项学校作业，作业是编写一个堆排序(就地)程序。现在该程序对于少于 +- 20 个元素的数组工作得很好，超过它偶尔会搞砸，但我似乎找不到问题所在。

/**
 * swaps two elements in an array
 *
 * @param a array
 * @param i position of element to swap in a
 * @param j position of element to swap in a
 */
public static void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

/**
 * restores the heap property in a heap represented as an array
 * 4 5 0
 * <p>
 * restoreHeap([4, 5, 0], 0, 3)
 * biggest = 1
 *
 * @param heap  array representation of a heap,
 *              which might be invalidated
 * @param root  index of the root of the heap,
 *              which might be a subtree of the overall heap
 * @param range index of the last element in the heap,
 *              array elements with an index > range are not part of the heap
 *              <p>
 *              when the heap property is invalid at root,
 *              the method fixes the heap first locally before fixing the affected subtree
 */
public static void restoreHeap(int[] heap, int root, int range) {
    final int left = root * 2 + 1;
    final int right = root * 2 + 2;
    final int size = root + range;
    int biggest = root;
    if (left < size && heap[left] > heap[biggest]) {
        biggest = left;
    }
    if (right < size && heap[right] > heap[biggest]) {
            biggest = right;
    }

    if (biggest != root) {
        swap(heap, biggest, root);
        restoreHeap(heap, biggest, range - (biggest - root));
    }
}


/**
 * turns an array of integers into a heap
 * <p>
 * this is an in-place algorithm, the heap is built in the array itself
 * 1 2 4 5 9 3
 *
 * @param array of integer numbers,
 *              on return, this array represents a valid heap
 */
public static void buildHeap(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int temp = i;
        while (array[temp / 2] < array[temp]) {
            swap(array, temp / 2, temp);
            temp /= 2;
        }
    }
}

/**
 * sorts an array of integer numbers
 * <p>
 * this is an in-place algorithm, the heap is built in the array itself
 *
 * @param array of elements, on return, this array represents a valid heap
 */
public static void inPlaceHeapSort(int[] array) {
    buildHeap(array);
    int arrSize = array.length;
    while (arrSize > 1) {
        swap(array, arrSize - 1, 0);
        arrSize--;
        restoreHeap(array, 0, arrSize);
    }
}

方法的框架已经存在，所以如果您问为什么某些参数还在那里，那是因为它是强制性的。

Answer 1

问题似乎是索引，左右的索引似乎是错误的

final int left = root * 2 + 1;
final int right = root * 2 + 2;

这里你应该把代码改成

final int left = root * 2;
final int right = root * 2 + 1;

还要记住，您必须从 1 而不是 0 开始对数组进行索引。