- 相關(guān)推薦
java堆排序的算法思想的分析
一、基礎(chǔ)知識
我們通常所說的堆是指二叉堆，二叉堆又稱完全二叉樹或者叫近似完全二叉樹。二叉堆又分為最大堆和最小堆。
堆排序(Heapsort)是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種�？梢岳脭�(shù)組的特點(diǎn)快速定位指定索引的元素。數(shù)組可以根據(jù)索引直接獲取元素，時間復(fù)雜度為O（1），也就是常量，因此對于取值效率極高。
最大堆的特性如下：
父結(jié)點(diǎn)的鍵值總是大于或者等于任何一個子節(jié)點(diǎn)的鍵值 每個結(jié)點(diǎn)的左子樹和右子樹都是一個最大堆
最小堆的特性如下：
父結(jié)點(diǎn)的鍵值總是小于或者等于任何一個子節(jié)點(diǎn)的鍵值 每個結(jié)點(diǎn)的左子樹和右子樹都是一個最小堆
二、算法思想
1.最大堆的算法思想是：
先將初始的R[0…n-1]建立成最大堆，此時是無序堆，而堆頂是最大元素
再將堆頂R[0]和無序區(qū)的最后一個記錄R[n-1]交換，由此得到新的無序區(qū)R[0…n-2]和有序區(qū)R[n-1]，且滿足R[0…n-2].keys ≤ R[n-1].key
由于交換后，前R[0…n-2]可能不滿足最大堆的性質(zhì)，因此再調(diào)整前R[0…n-2]為最大堆，直到只有R[0]最后一個元素才調(diào)整完成。
最大堆排序完成后，其實(shí)是升序序列，每次調(diào)整堆都是要得到最大的一個元素，然后與當(dāng)前堆的最后一個元素交換，因此最后所得到的序列是升序序列。
2.最小堆的算法思想是：
先將初始的R[0…n-1]建立成最小堆，此時是無序堆，而堆頂元素是最小的元素
再將堆頂R[0]與無序區(qū)的最后一個R[n-1]交換，由此得到新的無序堆R[0…n-2]和有序堆R[n-1]，且滿足R[0…n-2].keys >= R[n-1].key
由于交換后，前R[0…n-2]可能不滿足最小堆的性質(zhì)，因此再調(diào)整前R[0…n-2]為最小堆，直到只有R[0]最后一個元素才調(diào)整完成
最小堆排序完成后，其實(shí)是降序序列，每次調(diào)整堆都是要得到最小的一個元素，然后與當(dāng)前無序堆的最后一個元素交換，所以所得到的序列是降序的。
提示：堆排序的過程，其實(shí)就是不斷地?cái)U(kuò)大有序區(qū)，然后不斷地縮小無序區(qū)，直到只有有序區(qū)的過程。
三、排序過程分析
因?yàn)樗惴ū容^抽象，這里直接通過舉個小例子來說明堆排序的過程是如何的。下面我們用這個無序序列采用最大堆的進(jìn)行堆排序，所得到的序列就是升序序列（ASC）。
無序序列：89,-7,999,-89,7,0,-888,7,-7
第一步：初始化建成最大堆：
第二步：將堆頂最大元素999與無序區(qū)的最后一個元素交換，使999成為有序區(qū)。交換后，-7成為堆頂，由于-7并不是無序區(qū)中最大的元素，因此需要調(diào)整無序區(qū)，使無序區(qū)中最大值89成為堆頂，所以-7與89交換。交換后導(dǎo)致89的右子樹不滿足最大堆的性質(zhì)，因此要對右子樹調(diào)整成最大堆，所以-7要與0交換，如下圖：
從圖中看到，當(dāng)-7成89交換后，堆頂是最大元素了，但是-7的左孩子是0，右孩子是-888，由于-7<0，導(dǎo)致-7這個結(jié)點(diǎn)不滿足堆的性質(zhì)，因此需要調(diào)整它。所以，0與-7交換。
然后不斷重復(fù)著第二步的過程，直到全部成為有序區(qū)。
最后：所得到的是升序序列
四、時間復(fù)雜度
堆排序的時間，主要由建立初始堆和反復(fù)調(diào)整堆這兩部分的時間開銷構(gòu)成.由于堆排序是不穩(wěn)定的，它得扭到的時間復(fù)雜度會根據(jù)實(shí)際情況較大，因此只能取平均時間復(fù)雜度。
平均時間復(fù)雜度為：O( N * log2(N) )
堆排序耗時的操作有：初始堆 + 反復(fù)調(diào)整堆，時間復(fù)雜度如下：
1.初始建堆：每個父節(jié)點(diǎn)會和左右子節(jié)點(diǎn)進(jìn)行最多2次比較和1次交換，所以復(fù)雜度跟父節(jié)點(diǎn)個數(shù)有關(guān)。根據(jù)2x <= n（x為n個元素可以折半的次數(shù)，也就是父節(jié)點(diǎn)個數(shù)），得出x = log2n。即O ( log2n )
2.反復(fù)調(diào)整堆：由于初始化堆過程中，會記錄數(shù)組比較結(jié)果，所以堆排序?qū)υ蛄械臄?shù)組順序并不敏感，最好情況和最壞情況差不多。需要抽取 n-1 次堆頂元素，每次取堆頂元素都需要重建堆（O(重建堆) < O(初始堆)）。所以小于 O(n-1) * O(log2n)
使用建議：
由于初始化堆需要比較的次數(shù)較多，因此，堆排序比較適合于數(shù)據(jù)量非常大的場合（百萬數(shù)據(jù)或更多）。由于高效的快速排序是基于遞歸實(shí)現(xiàn)的，所以在數(shù)據(jù)量非常大時會發(fā)生堆棧溢出錯誤。
【java堆排序的算法思想的分析】相關(guān)文章：
C#排序算法之堆排序07-21
Java排序算法06-17
堆排序算法及用C++實(shí)現(xiàn)基于最大堆的堆09-19
Java中shuffle算法的使用09-22
java常見的排序算法的代碼09-20
常用Java排序算法詳解09-17
JAVA語言的常見排序算法07-16
java垃圾回收算法講解08-27