java - 我的堆排序只排列在数组的特定间隔

Question

堆排序有问题。好像只有每4个间隔排列一次。我得到的输出是:

167548
1092841
11047435
23672988
3901457
13705876
32329454
62936411
34097325
45417546
23189907
50261310
184562247

代码:

public static <T extends Comparable<? super T>> void reheap(T[] heap, int rootIndex, int lastIndex) {

    boolean done = false;
    T orphan = heap[rootIndex];
    int leftChildIndex = 2 * rootIndex + 1;

    while (!done && (leftChildIndex <= lastIndex)) {
        int largerChildIndex = leftChildIndex;
        int rightChildIndex = leftChildIndex + 1;
        if ((rightChildIndex <= lastIndex) && heap[rightChildIndex].compareTo(heap[largerChildIndex]) > 0) {
            largerChildIndex = rightChildIndex;
        }

        if (orphan.compareTo(heap[largerChildIndex]) < 0) {
            heap[rootIndex] = heap[largerChildIndex];
            rootIndex = largerChildIndex;
            leftChildIndex = 2 * rootIndex + 1;

        } else
            done = true;
    }
    heap[rootIndex] = orphan;
}

public static <T extends Comparable<? super T>> void heapsort(T[] array, int n) {
    for (int rootIndex = n / 2 - 1; rootIndex >= 0; rootIndex--) {

        reheap(array, rootIndex, n - 1);
        swap(array, 0, n - 1);

        for (int lastIndex = n - 2; lastIndex > 0; lastIndex--) {
            reheap(array, 0, lastIndex);
            swap(array, 0, lastIndex);

        }
    }
}

public static void swap(Object[] array, int i, int j) {
    Object temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

Answer 1

我不确定这是否是最佳解决方案，但您可以尝试将内部 for-loop 移出:

public static <T extends Comparable<? super T>> void heapsort(T[] array, int n) {
    for (int rootIndex = n / 2 - 1; rootIndex >= 0; rootIndex--) {
        reheap(array, rootIndex, n - 1);
        swap(array, 0, n - 1);
    }

    for (int lastIndex = n - 2; lastIndex > 0; lastIndex--) {
        reheap(array, 0, lastIndex);
        swap(array, 0, lastIndex);
    }
}