java堆排序的算法思想的分析
一、基礎知識
我們通常所説的堆是指二叉堆,二叉堆又稱完全二叉樹或者叫近似完全二叉樹。二叉堆又分為最大堆和最小堆。
堆排序(Heapsort)是指利用堆這種數據結構所設計的一種排序算法,它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。數組可以根據索引直接獲取元素,時間複雜度為O(1),也就是常量,因此對於取值效率極高。
最大堆的特性如下:
父結點的鍵值總是大於或者等於任何一個子節點的鍵值 每個結點的左子樹和右子樹都是一個最大堆
最小堆的特性如下:
父結點的鍵值總是小於或者等於任何一個子節點的鍵值 每個結點的左子樹和右子樹都是一個最小堆
二、算法思想
1.最大堆的算法思想是:
先將初始的R[0…n-1]建立成最大堆,此時是無序堆,而堆頂是最大元素
再將堆頂R[0]和無序區的最後一個記錄R[n-1]交換,由此得到新的無序區R[0…n-2]和有序區R[n-1],且滿足R[0…n-2] ≤ R[n-1]
由於交換後,前R[0…n-2]可能不滿足最大堆的性質,因此再調整前R[0…n-2]為最大堆,直到只有R[0]最後一個元素才調整完成。
最大堆排序完成後,其實是升序序列,每次調整堆都是要得到最大的一個元素,然後與當前堆的最後一個元素交換,因此最後所得到的序列是升序序列。
2.最小堆的算法思想是:
先將初始的R[0…n-1]建立成最小堆,此時是無序堆,而堆頂元素是最小的元素
再將堆頂R[0]與無序區的最後一個R[n-1]交換,由此得到新的無序堆R[0…n-2]和有序堆R[n-1],且滿足R[0…n-2] >= R[n-1]
由於交換後,前R[0…n-2]可能不滿足最小堆的性質,因此再調整前R[0…n-2]為最小堆,直到只有R[0]最後一個元素才調整完成
最小堆排序完成後,其實是降序序列,每次調整堆都是要得到最小的一個元素,然後與當前無序堆的最後一個元素交換,所以所得到的序列是降序的。
提示:堆排序的過程,其實就是不斷地擴大有序區,然後不斷地縮小無序區,直到只有有序區的過程。
三、排序過程分析
因為算法比較抽象,這裏直接通過舉個小例子來説明堆排序的過程是如何的。下面我們用這個無序序列採用最大堆的進行堆排序,所得到的序列就是升序序列(ASC)。
無序序列:89,-7,999,-89,7,0,-888,7,-7
第一步:初始化建成最大堆:
第二步:將堆頂最大元素999與無序區的最後一個元素交換,使999成為有序區。交換後,-7成為堆頂,由於-7並不是無序區中最大的元素,因此需要調整無序區,使無序區中最大值89成為堆頂,所以-7與89交換。交換後導致89的`右子樹不滿足最大堆的性質,因此要對右子樹調整成最大堆,所以-7要與0交換,如下圖:
從圖中看到,當-7成89交換後,堆頂是最大元素了,但是-7的左孩子是0,右孩子是-888,由於-7<0,導致-7這個結點不滿足堆的性質,因此需要調整它。所以,0與-7交換。
然後不斷重複着第二步的過程,直到全部成為有序區。
最後:所得到的是升序序列
四、時間複雜度
堆排序的時間,主要由建立初始堆和反覆調整堆這兩部分的時間開銷構成.由於堆排序是不穩定的,它得扭到的時間複雜度會根據實際情況較大,因此只能取平均時間複雜度。
平均時間複雜度為:O( N * log2(N) )
堆排序耗時的操作有:初始堆 + 反覆調整堆,時間複雜度如下:
1.初始建堆:每個父節點會和左右子節點進行最多2次比較和1次交換,所以複雜度跟父節點個數有關。根據2x <= n(x為n個元素可以折半的次數,也就是父節點個數),得出x = log2n。即O ( log2n )
2.反覆調整堆:由於初始化堆過程中,會記錄數組比較結果,所以堆排序對原序列的數組順序並不敏感,最好情況和最壞情況差不多。需要抽取 n-1 次堆頂元素,每次取堆頂元素都需要重建堆(O(重建堆) < O(初始堆))。所以小於 O(n-1) * O(log2n)
使用建議:
由於初始化堆需要比較的次數較多,因此,堆排序比較適合於數據量非常大的場合(百萬數據或更多)。由於高效的快速排序是基於遞歸實現的,所以在數據量非常大時會發生堆棧溢出錯誤。
-
Java程序設計示例教程
本文以實例形式詳細講述了Java的反射機制,是Java程序設計中重要的技巧。分享給大家供大家參考。具體分析如下:首先,Reflection是Java程序開發語言的特徵之一,它允許運行中的Java程序對自身進行檢查,或者説"自審",並能直接操作程序的內部屬性。例如,使用它能獲得Java類...
-
計算機二級Java備考習題及答案
練習可以幫助我們加深對知識的記憶和理解,下面是本站小編整理的2017計算機二級Java備考練習題及答案,歡迎學習!備考練習題一1、下列敍述中,錯誤的是______。A、Applet的默認佈局管理器是FlowLayoutB、JApplet中增加構件是加到JApplet的內容面板上,不是直接加到JApp...
-
Java中如何獲取Spring中配置的bean
Spring是一個分層的JavaSE/EEfull-stack(一站式)輕量級開源框架。在Java中如何獲取Spring中配置的'bean?下面本站小編帶大家一起來看看詳細操作,希望對大家有所幫助!想了解更多相關信息請持續關注我們應屆畢業生考試網!一、什麼是Spring?Spring是一個輕量級的控...
-
java的基礎語法教學
java的基礎語法教學前言學習完了第一個java程序,之後就來系統的學習java。先從基礎語法開始,這個語法你也可以理解為英語或是漢語裏面的語法,只不過大家各有各的特點和區別。學習編程其實也是一個編程語言的學習過程。我們在學習英語的.時候都説,要想學習好英語一...