久久国产成人av_抖音国产毛片_a片网站免费观看_A片无码播放手机在线观看,色五月在线观看,亚洲精品m在线观看,女人自慰的免费网址,悠悠在线观看精品视频,一级日本片免费的,亚洲精品久,国产精品成人久久久久久久

搜索
分享

java堆排序算法

 dongsibei 2014-04-24

java堆排序算法

2012-08-26 作者：神馬舉報

[java]代碼庫

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

    本站是提供個人知識管理的網(wǎng)絡(luò)存儲空間,，所有內(nèi)容均由用戶發(fā)布,，不代表本站觀點。請注意甄別內(nèi)容中的聯(lián)系方式,、誘導(dǎo)購買等信息,，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,，請點擊一鍵舉報,。
    轉(zhuǎn)藏 分享 獻(xiàn)花（0）

    0條評論

    發(fā)表

    請遵守用戶 評論公約

    類似文章 更多