java堆排序算法2012-08-26 作者： 神馬舉報[java]代碼庫 * 1. 基本思想： 堆排序是一樹形選擇排序，在排序過程中，將R[1..N]看成是一顆完全二叉樹的順序存儲結(jié)構(gòu)， |
* 利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系來選擇最小的元素。 |
* 2. 堆的定義: N個元素的序列K1,K2,K3,...,Kn.稱為堆，當且僅當該序列滿足特性： 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.排序過程： 堆排序正是利用小根堆（或大根堆）來選取當前無序區(qū)中關(guān)鍵字小（或最大）的記錄實現(xiàn)排序的。我們不妨利用大根堆來排序。每一趟排序的基本操作是： |
* 將當前無序區(qū)調(diào)整為一個大根堆 |
* ，選取關(guān)鍵字最大的堆頂記錄，將它和無序區(qū)中的最后一個記錄交換。這樣，正好和直接選擇排序相反，有序區(qū)是在原記錄區(qū)的尾部形成并逐步向前擴大到整個記錄區(qū)。 |
* 排序算法的實現(xiàn)，對數(shù)組中指定的元素進行排序 |
public void sort(Integer[] array, int from, int end) { |
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 |
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); |
* 調(diào)整節(jié)點順序，從父、左右子節(jié)點三個節(jié)點中選擇一個最大節(jié)點與父節(jié)點轉(zhuǎn)換 |
* 要調(diào)整的節(jié)點，與它的子節(jié)點一起進行調(diào)整 |
private void adjustNote(Integer[] arr, int parentNodeIndex, int len) { |
int minNodeIndex = parentNodeIndex; |
// 如果有左子樹，i * 2為左子節(jié)點索引 |
if (parentNodeIndex * 2 <= len) { |
if ((arr[parentNodeIndex - 1] |
.compareTo(arr[parentNodeIndex * 2 - 1])) < 0) { |
minNodeIndex = parentNodeIndex * 2;// 記錄最大索引為左子節(jié)點索引 |
// 只有在有或子樹的前提下才可能有右子樹，再進一步斷判是否有右子樹 |
if (parentNodeIndex * 2 + 1 <= len) { |
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); |
public void swap(Integer[] array, int i, int j) { |
if (i != j) {// 只有不是同一位置時才需交換 |
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 + " "); |
|
