堆積排序

堆積排序是利用堆這種資料結構而設計的一種排序演算法，堆排序是一種選擇排序，它的最壞、最好、平均時間複雜度均為 O(nlogn)，它也是不穩定排序。

• "堆"是具有以下性質的完全二元樹：

1. 大頂推：每個節點的值都大於或等於其左右孩子結點的值
2. 小頂推：每個節點的值都小於或等於其左右孩子節點的值，
3. 沒有要求節點的左孩子的值和右孩子的值的大小關係。

程式範例試做:

import java.util.Arrays;

public class Alex1014_1 {
    public static void main(String[] args){
        int arr[] = {2, 7901, 41, 89, 23};
        Alex1014_1(arr);
    }

    public static void Alex1014_1(int arr[]) {
        System.out.println("堆積排序");
        // 第一次調整
        adjustHeap(arr, 1, arr.length);
        System.out.println(Arrays.toString(arr));
        // 第二次調整
        adjustHeap(arr, 0, arr.length);
        System.out.println(Arrays.toString(arr));
    }
    // 將一個陣列(二元樹), 調整成一個大頂堆
    public static void adjustHeap(int arr[], int i, int length) {
        int temp = arr[i]; // 先取出當前元素的值, 保存在臨時變數
        // 開始調整
        // int k = i * 2 + 1 => i 的左子節點
        // k = k * 2 + 1 => 下次再調的話就是下面的左子節點
        for(int k = i * 2 + 1; k < length ; k = k * 2 + 1) {
            if(k+1 < length && arr[k] < arr[k+1]) { // 左子節點小於右子節點
                k++; // k 指向右子節點(因為要找到最大值)
            }
            if(arr[k] > temp) { // 如果子節點大於父節點
                arr[i] = arr[k]; // 把較大的值賦給當前值
                i = k; // i 指向 k 繼續循環比較
            } else {
                break;
            }
        }
        arr[i] = temp; // 將 temp 值放到調整後的位置
    }
}

程式執行結果:

[2, 7901, 41, 89, 23]
[7901, 89, 41, 2, 23]

不過由執行結果可以發現，這樣得堆積排序並沒有真正行程有序數列，因此透過修改部分程式碼調整會變成下列範例。

程式範例試做:

import java.util.Arrays;

public class Alex1014_2 {
    public static void main(String[] args){
        int arr[] = {2, 7901, 41, 89, 23};
        Alex1014_2(arr);
    }

    public static void Alex1014_2(int arr[]) {
        int temp = 0;
        System.out.println("堆積排序");

        // 將無序序列構建成一個堆, 根據升序降序需求選擇大頂堆或小頂堆
        // arr.length / 2 - 1 => 從下至上 由左至右 找出非葉子節點
        for(int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }

        for(int j = arr.length - 1; j > 0; j--) {
            // 交換
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }

        System.out.println(Arrays.toString(arr));
    }
    public static void adjustHeap(int arr[], int i, int length) {
        int temp = arr[i];
        for(int k = i * 2 + 1; k < length ; k = k * 2 + 1) {
            if(k+1 < length && arr[k] < arr[k+1]) {
                k++;
            }
            if(arr[k] > temp) {
                arr[i] = arr[k];
                i = k;
            } else {
                break;
            }
        }
        arr[i] = temp;
    }
}

程式執行結果:

堆積排序
[2, 23, 41, 89, 7901]