如何使用java實作堆排序演算法

如何使用Java實作堆排序演算法

堆排序是一種基於堆疊資料結構的排序演算法，它利用了堆的性質來進行排序。堆排序分為兩個主要步驟：建堆和排序。

建堆：
首先，我們需要根據待排序的陣列來建構一個大根堆或小根堆。對於升序排序，我們需要建構一個大根堆；對於降序排序，我們需要建造一個小根堆。

大根堆的性質是：節點的值大於或等於其子節點的值。
小根堆的性質是：節點的值小於或等於其子節點的值。

建構大根堆的過程如下：

public static void buildHeap(int[] array, int length) {
    for (int i = length / 2 - 1; i >= 0; i--) {
        heapify(array, length, i);
    }
}

public static void heapify(int[] array, int length, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < length && array[left] > array[largest]) {
        largest = left;
    }

    if (right < length && array[right] > array[largest]) {
        largest = right;
    }

    if (largest != i) {
        int temp = array[i];
        array[i] = array[largest];
        array[largest] = temp;
        heapify(array, length, largest);
    }
}

排序：
建構好大根堆之後，我們需要將堆頂元素與數組的最後一個元素進行交換，並且縮小堆的範圍，然後再對堆進行堆化操作，重複此過程直到堆為空。最後得到的數組就是有序的。

public static void heapSort(int[] array) {
    int length = array.length;

    buildHeap(array, length);

    for (int i = length - 1; i >= 0; i--) {
        int temp = array[i];
        array[i] = array[0];
        array[0] = temp;

        heapify(array, i, 0);
    }
}

使用範例：

public static void main(String[] args) {
    int[] array = {4, 10, 3, 5, 1};
    heapSort(array);

    System.out.println(Arrays.toString(array));
}

輸出結果為：[1, 3, 4, 5, 10]，即為升序排序的結果。

堆排序的時間複雜度為O(nlogn)，其中n為待排序元素的數量。堆排序是一種穩定的排序演算法，適用於大規模資料的排序。

以上是如何使用java實作堆排序演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！