/**
 * 選擇排序之堆排序：
 *
 * 1. 基本思想： 堆排序是一樹形選擇排序，在排序過程中，將R[1..N]看成是一顆完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，
 * 利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來選擇最小的元素。
 *
 * 2. 堆的定義: N個(gè)元素的序列K1,K2,K3,...,Kn.稱為堆，當(dāng)且僅當(dāng)該序列滿足特性： Ki≤K2i Ki ≤K2i+1(1≤ I≤[N/2])
 * 堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉子結(jié)點(diǎn)的關(guān)鍵字均大于等于其孩子結(jié)點(diǎn)的關(guān)鍵字。例如序列10,15,56,25,30,70就是一個(gè)堆，
 * 它對應(yīng)的完全二叉樹如上圖所示。這種堆中根結(jié)點(diǎn)（稱為堆頂）的關(guān)鍵字最小，我們把它稱為小根堆。
 * 反之，若完全二叉樹中任一非葉子結(jié)點(diǎn)的關(guān)鍵字均大于等于其孩子的關(guān)鍵字，則稱之為大根堆。
 *
 * 3.排序過程： 堆排序正是利用小根堆（或大根堆）來選取當(dāng)前無序區(qū)中關(guān)鍵字小（或最大）的記錄實(shí)現(xiàn)排序的。我們不妨利用大根堆來排序。每一趟排序的基本操作是：
 * 將當(dāng)前無序區(qū)調(diào)整為一個(gè)大根堆
 * ，選取關(guān)鍵字最大的堆頂記錄，將它和無序區(qū)中的最后一個(gè)記錄交換。這樣，正好和直接選擇排序相反，有序區(qū)是在原記錄區(qū)的尾部形成并逐步向前擴(kuò)大到整個(gè)記錄區(qū)。
 */
public class HeapSort {
 
    /**
     * 排序算法的實(shí)現(xiàn)，對數(shù)組中指定的元素進(jìn)行排序
     *
     * @param array
     *            待排序的數(shù)組
     * @param from
     *            從哪里開始排序
     * @param end
     *            排到哪里
     * @param c
     *            比較器
     */
    public void sort(Integer[] array, int from, int end) {
        // 創(chuàng)建初始堆
        initialHeap(array, from, end);
 
        /*
         * 對初始堆進(jìn)行循環(huán)，且從最后一個(gè)節(jié)點(diǎn)開始，直接樹只有兩個(gè)節(jié)點(diǎn)止 每輪循環(huán)后丟棄最后一個(gè)葉子節(jié)點(diǎn)，再看作一個(gè)新的樹
         */
        for (int i = end - from + 1; i >= 2; i--) {
            // 根節(jié)點(diǎn)與最后一個(gè)葉子節(jié)點(diǎn)交換位置，即數(shù)組中的第一個(gè)元素與最后一個(gè)元素互換
            swap(array, from, i - 1);
            // 交換后需要重新調(diào)整堆
            adjustNote(array, 1, i - 1);
        }
 
    }
 
    /**
     * 初始化堆 比如原序列為：7,2,4,3,12,1,9,6,8,5,10,11 則初始堆為：1,2,4,3,5,7,9,6,8,12,10,11
     *
     * @param arr
     *            排序數(shù)組
     * @param from
     *            從哪
     * @param end
     *            到哪
     * @param c
     *            比較器
     */
    private void initialHeap(Integer[] arr, int from, int end) {
        int lastBranchIndex = (end - from + 1) / 2;// 最后一個(gè)非葉子節(jié)點(diǎn)
        // 對所有的非葉子節(jié)點(diǎn)進(jìn)行循環(huán) ，且從最一個(gè)非葉子節(jié)點(diǎn)開始
        for (int i = lastBranchIndex; i >= 1; i--) {
            adjustNote(arr, i, end - from + 1);
        }
    }
 
    /**
     * 調(diào)整節(jié)點(diǎn)順序，從父、左右子節(jié)點(diǎn)三個(gè)節(jié)點(diǎn)中選擇一個(gè)最大節(jié)點(diǎn)與父節(jié)點(diǎn)轉(zhuǎn)換
     *
     * @param arr
     *            待排序數(shù)組
     * @param parentNodeIndex
     *            要調(diào)整的節(jié)點(diǎn)，與它的子節(jié)點(diǎn)一起進(jìn)行調(diào)整
     * @param len
     *            樹的節(jié)點(diǎn)數(shù)
     * @param c
     *            比較器
     */
    private void adjustNote(Integer[] arr, int parentNodeIndex, int len) {
        int minNodeIndex = parentNodeIndex;
        // 如果有左子樹，i * 2為左子節(jié)點(diǎn)索引
        if (parentNodeIndex * 2 <= len) {
            // 如果父節(jié)點(diǎn)小于左子樹時(shí)
            if ((arr[parentNodeIndex - 1]
                    .compareTo(arr[parentNodeIndex * 2 - 1])) < 0) {
                minNodeIndex = parentNodeIndex * 2;// 記錄最大索引為左子節(jié)點(diǎn)索引
            }
 
            // 只有在有或子樹的前提下才可能有右子樹，再進(jìn)一步斷判是否有右子樹
            if (parentNodeIndex * 2 + 1 <= len) {
                // 如果右子樹比最大節(jié)點(diǎn)更大
                if ((arr[minNodeIndex - 1]
                        .compareTo(arr[(parentNodeIndex * 2 + 1) - 1])) < 0) {
                    minNodeIndex = parentNodeIndex * 2 + 1;// 記錄最大索引為右子節(jié)點(diǎn)索引
                }
            }
        }
 
        // 如果在父節(jié)點(diǎn)、左、右子節(jié)點(diǎn)三都中，最大節(jié)點(diǎn)不是父節(jié)點(diǎn)時(shí)需交換，把最大的與父節(jié)點(diǎn)交換，創(chuàng)建大頂堆
        if (minNodeIndex != parentNodeIndex) {
            swap(arr, parentNodeIndex - 1, minNodeIndex - 1);
            // 交換后可能需要重建堆，原父節(jié)點(diǎn)可能需要繼續(xù)下沉
            if (minNodeIndex * 2 <= len) {// 是否有子節(jié)點(diǎn)，注，只需判斷是否有左子樹即可知道
                adjustNote(arr, minNodeIndex, len);
            }
        }
    }
 
    /**
     * 交換數(shù)組中的兩個(gè)元素的位置
     *
     * @param array
     *            待交換的數(shù)組
     * @param i
     *            第一個(gè)元素
     * @param j
     *            第二個(gè)元素
     */
    public void swap(Integer[] array, int i, int j) {
        if (i != j) {// 只有不是同一位置時(shí)才需交換
            Integer tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }
    }
 
    /**
     * 測試
     *
     * @param args
     */
    public static void main(String[] args) {
        Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7, 0, -7, -1, 34 };
        HeapSort heapsort = new HeapSort();
        heapsort.sort(intgArr, 0, intgArr.length - 1);
        for (Integer intObj : intgArr) {
            System.out.print(intObj + " ");
        }
    }
 
}

標(biāo)簽： swap

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。