堆排序

tangr206 發布于2019-08-16 12:30 / 1977人閱讀

摘要：計算機算法理論簡介建立初始堆首末元素互換即得到最大元素放入數組最末尾調整堆第二步的操作明顯會將堆破壞所以需要調整堆跳回第二步建立初始堆在建堆之前需要將數組轉成二叉樹圖方便理解如果將父左子右子當做樹的最小單元組稱為父子單元那么只需要保證每個父

@(Study)[計算機, 算法]

理論簡介

建立初始堆

首末元素互換, 即得到最大元素放入數組最末尾.

調整堆. 第二步的操作明顯會將堆破壞, 所以需要調整堆.

跳回第二步.

建立初始堆

在建堆之前需要將數組轉成二叉樹圖, 方便理解:

如果將父>左子|右子當做樹的最小單元組, 稱為父子單元, 那么只需要保證每個父子單元滿足最大堆規則, 那么整體樹就滿足了最大堆.
==>定義一個方法(unitAdjust())用來調整父子單元, 將單元中最大的值推到該單元的根部, 成為父, 原來的父降到最大值之前的位置, 作為子. 但是這樣有可能使得以這個新子為父結點的下一層的父子單元不滿足最大堆規則. ==>設置規則, 如果發生了交換, 則遞歸調用方法自身, 調整新子為父結點的父子單元. 如此反復.

上述過程可以說是自上而下的下鉆過程.

但是如果使得整個樹成為最大堆, 那么就是需要針對樹中的每個父子單元進行調整. 只需要對樹中的每個非葉子節點進行遍歷, 使用上述方法unitaAdjust()調整即可. 進一分析, 可以發現這里有個問題: 遍歷的方向是自上而下還是自下而上呢?

如果自上而下會出現什么情況呢?
如下圖, 第一趟循環中, 操作的對象是以根結點34為父結點的父子單元. 循環體內部將調用unitAdjust(), 34和50將互換, 由于發生了交換, unitAdust()方法將發生遞歸調用, 去操作以新子34為父結點的父子單元, 經過比較, 未發生交換情況, 第一趟循環結束. 圖中發生了比較或者互換的位置以綠色標出, 這時聰明的你不難發現, 當程序向下遍歷走到第三個節點時, 便發生了重復比較, 當然你或許能夠想到規避重復比較的方法, 但是我是沒有想出, 或者也可以認為重復比較無所謂.

其實, 換一種思路, 進行自下而上遍歷情況就完全不一樣了.

從最后一個非葉子節點67開始, 67?90

50節點不動

23?90, 觸發下鉆機制.

23?67

34?90, 觸發下鉆機制

34?67, 再次下鉆

未動

最終得到初始堆如下圖所示, 其中藍色表示交換過位置.

可見, 整體是自下而上遍歷, 具體單元操作時采取自上而下, 總之, 自上而下和自下而上的相結合.

建立堆的過程其實有點冒泡的味道, 數值大逐漸的冒到上面, 好像密度大的即使開始在水底部, 但隨著遍歷, 密度大的終將上浮到上部.

堆排序

初始堆建立好了后, 堆頂的元素自然就是最大值, 于是將第一個元素和最后一個元素互換, 即完成將最大值放到最末尾, 完了第一次排序.

由于交換使得堆被破壞, 所以需要對的n-1個元素進行調整, 使其成為堆. 具體做法就是調用unitAdjust()對以根節點為父結點的父子單元進行調整, 剛換來的最末位元素自然會被移到子節點位置, 這樣遞歸調用機制被觸發, 于是繼續保證所有下層調整為堆.

接著將倒數第二個元素和堆頂元素互換, ......如此反復.

代碼實現

思路:

//建立初始堆//
for (i=n/2;i>=1;i--) {
    unitAdjust()
}
//堆排序//
for (i=n; i>=1; i--) {
    首末交換
    unitAdjust()調整
}

Java代碼:

測試結果:

10億長度, 內存爆掉;

1億長度, 35693ms.

package LearningLog;

/*
 * - 10億長度, 內存爆掉
 * - 1億長度, 35693ms.
 */

public class demo25 {
    public static void main(String[] args) {
        int[] arr=MyJava.randomArr(100000000, 10000,123);
//        System.out.println(Arrays.toString(arr));
//        initHeap(arr);
        long t0 = System.currentTimeMillis();
        heapSort(arr);
        long t1 = System.currentTimeMillis();
        System.out.println((t1-t0)+"ms");
//        System.out.println(Arrays.toString(arr));
    }
    /* ====unitAdjust()===========================================
     * 父子單元調整
     * I: 父結點的索引, 數組長度: 非常非常非常關鍵, 因為后續調用的時候, 需要卡住最大的遍歷位置, 否則將會將尾部已經排好序的較大數值頂到上面去了, 那就糟糕嘔吐了
     */
    public static void unitAdjust(int array[],int fatherNode, int sub_size) {
        int lchild = 2*fatherNode+1;
        int rchild = lchild+1;

        int max = fatherNode; // 默認最大值索引就是父結點的索引
        int tmp = 0;
        if (fatherNode=0; i--) {
            unitAdjust(array, i, array.length);   //大的值不斷上浮
        }

    }
    
    /*
     * ====heapSort()=================================================
     * 堆排序
     */
    public static void heapSort(int[] array) {
        int tmp=0;
        //建立堆//
        initHeap(array);
        for(int i=array.length-1; i>=0; i--) {
            //首尾互換/
            tmp = array[i];
            array[i] = array[0];
            array[0] = tmp;
            
            //剩下的i-1個元素需要調整//
            unitAdjust(array, 0, i); //始終只用調整第一個父子單元即可
        }
    }
    
    
    
    
    
}

GPU云服務器云服務器堆排序堆排序算法堆排序排序c語言 python的堆排序

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/71219.html

JavaScript 數據結構與算法之美 - 歸并排序、快速排序、希爾排序、堆排序

摘要：之所以把歸并排序快速排序希爾排序堆排序放在一起比較，是因為它們的平均時間復雜度都為。歸并排序是一種穩定的排序方法。因此，快速排序并不穩定。希爾排序思想先將整個待排序的記錄序列分割成為若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言算法為王。想學好前端，先練好內功，只有內功深厚者，前端之路才...

haitiancoder 2019-08-26 10:20 評論0 收藏0
七大排序算法總結(java)

摘要：前面介紹了七大算法的思想與實現步驟，下面來做一個歸總。直到無序區中的數為零，結束排序。步驟以從小到大為例，排序數組大小為。比較完以后則排序結束。堆排序思想堆排序是采用樹的形式的數據結構來進行排序的，其中每一個堆都是完全二叉樹。前面介紹了七大算法的思想與實現步驟，下面來做一個歸總。排序方法平均復雜度最壞復雜度最好復雜度輔助空間穩定性直接選擇排序 O(n^2...

cartoon 2019-08-14 14:09 評論0 收藏0
堆排序就這么簡單

摘要：一堆排序介紹來源百度百科堆排序是指利用堆積樹堆這種數據結構所設計的一種排序算法，它是選擇排序的一種。一、堆排序介紹來源百度百科：堆排序(Heapsort)是指利用堆積樹（堆）這種數據結構所設計的一種排序算法，它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。前面我已經有二叉樹入門的文章了，當時講解的是二叉查找樹，那上面所說的完全二...

NickZhou 2019-08-19 10:43 評論0 收藏0
基礎算法學習之(三):堆排序

摘要：奇妙的記憶點不穩定內排序基本思想分為兩步建堆與維持堆的性質首先我們要先理解堆是什么東西堆其實就是一個完全二叉樹我們可以使用順序表存儲一個二叉樹如下圖所示來存儲其中分為最大堆最小堆而最大堆就是上頭大下頭小最小堆則反之明白了堆的定義我們就可以開奇妙的記憶點: 不穩定內排序基本思想: 分為兩步,建堆與維持堆的性質,首先我們要先理解堆是什么東西.堆其實就是一個完全二叉樹,我們可以使用...

mrli2016 2019-08-20 11:34 評論0 收藏0
常見八大排序（C語言實現）及動圖演示

摘要：當到達時等同于直接插入排序，此時序列已基本有序，所有記錄在統一組內排好成有序序列。當面對大量數據時，希爾排序將比直接插入排序更具優勢圖示講解第一趟取增量，所有間隔為的元素分在一組，在各個組中分別進行直接插入排序。 ...

不知名網友 2021-11-26 11:11 評論0 收藏0