日韩黑丝制服一区视频播放|日韩欧美人妻丝袜视频在线观看|九九影院一级蜜桃|亚洲中文在线导航|青草草视频在线观看|婷婷五月色伊人网站|日本一区二区在线|国产AV一二三四区毛片|正在播放久草视频|亚洲色图精品一区

搜索
分享

java堆排序算法

 dongsibei 2014-04-24

java堆排序算法

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

[java]代碼庫

/**
 * 選擇排序之堆排序：
 *
 * 1. 基本思想： 堆排序是一樹形選擇排序，在排序過程中，將R[1..N]看成是一顆完全二叉樹的順序存儲結構，
 * 利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。
 *
 * 2. 堆的定義: N個元素的序列K1,K2,K3,...,Kn.稱為堆，當且僅當該序列滿足特性： Ki≤K2i Ki ≤K2i+1(1≤ I≤[N/2])
 * 堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉子結點的關鍵字均大于等于其孩子結點的關鍵字。例如序列10,15,56,25,30,70就是一個堆，
 * 它對應的完全二叉樹如上圖所示。這種堆中根結點（稱為堆頂）的關鍵字最小，我們把它稱為小根堆。
 * 反之，若完全二叉樹中任一非葉子結點的關鍵字均大于等于其孩子的關鍵字，則稱之為大根堆。
 *
 * 3.排序過程： 堆排序正是利用小根堆（或大根堆）來選取當前無序區(qū)中關鍵字小（或最大）的記錄實現(xiàn)排序的。我們不妨利用大根堆來排序。每一趟排序的基本操作是：
 * 將當前無序區(qū)調整為一個大根堆
 * ，選取關鍵字最大的堆頂記錄，將它和無序區(qū)中的最后一個記錄交換。這樣，正好和直接選擇排序相反，有序區(qū)是在原記錄區(qū)的尾部形成并逐步向前擴大到整個記錄區(qū)。
 */
public class HeapSort {
 
    /**
     * 排序算法的實現(xiàn)，對數(shù)組中指定的元素進行排序
     *
     * @param array
     *            待排序的數(shù)組
     * @param from
     *            從哪里開始排序
     * @param end
     *            排到哪里
     * @param c
     *            比較器
     */
    public void sort(Integer[] array, int from, int end) {
        // 創(chuàng)建初始堆
        initialHeap(array, from, end);
 
        /*
         * 對初始堆進行循環(huán)，且從最后一個節(jié)點開始，直接樹只有兩個節(jié)點止 每輪循環(huán)后丟棄最后一個葉子節(jié)點，再看作一個新的樹
         */
        for (int i = end - from + 1; i >= 2; i--) {
            // 根節(jié)點與最后一個葉子節(jié)點交換位置，即數(shù)組中的第一個元素與最后一個元素互換
            swap(array, from, i - 1);
            // 交換后需要重新調整堆
            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é)點進行循環(huán) ，且從最一個非葉子節(jié)點開始
        for (int i = lastBranchIndex; i >= 1; i--) {
            adjustNote(arr, i, end - from + 1);
        }
    }
 
    /**
     * 調整節(jié)點順序，從父、左右子節(jié)點三個節(jié)點中選擇一個最大節(jié)點與父節(jié)點轉換
     *
     * @param arr
     *            待排序數(shù)組
     * @param parentNodeIndex
     *            要調整的節(jié)點，與它的子節(jié)點一起進行調整
     * @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é)點索引
            }
 
            // 只有在有或子樹的前提下才可能有右子樹，再進一步斷判是否有右子樹
            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)絡存儲空間，所有內容均由用戶發(fā)布，不代表本站觀點。請注意甄別內容中的聯(lián)系方式、誘導購買等信息，謹防詐騙。如發(fā)現(xiàn)有害或侵權內容，請點擊一鍵舉報。
    轉藏 分享 獻花（0）

    0條評論

    發(fā)表

    請遵守用戶 評論公約

    類似文章 更多