java堆排序算法代碼

/**


選擇排序之堆排序：
*

基本思想： 堆排序是一樹形選擇排序，在排序過程中，將R[1..N]看成是一顆完全二叉樹的順序存儲結構，


利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。
*

堆的定義: N個元素的序列K1,K2,K3,...,Kn.稱為堆，當且僅當該序列滿足特性： Ki≤K2i Ki ≤K2i+1(1≤ I≤[N/2])


堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉子結點的關鍵字均大于等于其孩子結點的關鍵字。例如序列10,15,56,25,30,70就是一個堆，
它對應的完全二叉樹如上圖所示。這種堆中根結點（稱為堆頂）的關鍵字最小，我們把它稱為小根堆。
反之，若完全二叉樹中任一非葉子結點的關鍵字均大于等于其孩子的關鍵字，則稱之為大根堆。
*
3.排序過程： 堆排序正是利用小根堆（或大根堆）來選取當前無序區中關鍵字小（或最大）的記錄實現排序的。我們不妨利用大根堆來排序。每一趟排序的基本操作是：
將當前無序區調整為一個大根堆
，選取關鍵字最大的堆頂記錄，將它和無序區中的最后一個記錄交換。這樣，正好和直接選擇排序相反，有序區是在原記錄區的尾部形成并逐步向前擴大到整個記錄區。
*/
public class HeapSort {
/**

排序算法的實現，對數組中指定的元素進行排序
*
@param array
待排序的數組
@param from
從哪里開始排序
@param end
排到哪里
@param c
比較器
*/
public void sort(Integer[] array, int from, int end) {
// 創建初始堆
initialHeap(array, from, end);
/*

對初始堆進行循環，且從最后一個節點開始，直接樹只有兩個節點止 每輪循環后丟棄最后一個葉子節點，再看作一個新的樹
*/
for (int i = end - from + 1; i >= 2; i--) {
// 根節點與最后一個葉子節點交換位置，即數組中的第一個元素與最后一個元素互換
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
排序數組
@param from
從哪
@param end
到哪
@param c
比較器
*/
private void initialHeap(Integer[] arr, int from, int end) {
int lastBranchIndex = (end - from + 1) / 2;// 最后一個非葉子節點
// 對所有的非葉子節點進行循環 ，且從最一個非葉子節點開始
for (int i = lastBranchIndex; i >= 1; i--) {
adjustNote(arr, i, end - from + 1);
}
}
/**

調整節點順序，從父、左右子節點三個節點中選擇一個最大節點與父節點轉換
*
@param arr
待排序數組
@param parentNodeIndex
要調整的節點，與它的子節點一起進行調整
@param len
樹的節點數
@param c
比較器
/
private void adjustNote(Integer[] arr, int parentNodeIndex, int len) {
int minNodeIndex = parentNodeIndex;
// 如果有左子樹，i  2為左子節點索引
if (parentNodeIndex  2 <= len) {
// 如果父節點小于左子樹時
if ((arr[parentNodeIndex - 1]
  .compareTo(arr[parentNodeIndex  2 - 1])) < 0) {
minNodeIndex = parentNodeIndex * 2;// 記錄最大索引為左子節點索引
}
// 只有在有或子樹的前提下才可能有右子樹，再進一步斷判是否有右子樹
if (parentNodeIndex * 2 + 1 <= len) {
// 如果右子樹比最大節點更大
if ((arr[minNodeIndex - 1]

  .compareTo(arr[(parentNodeIndex * 2 + 1) - 1])) < 0) {

minNodeIndex = parentNodeIndex * 2 + 1;// 記錄最大索引為右子節點索引
}
}
}
// 如果在父節點、左、右子節點三都中，最大節點不是父節點時需交換，把最大的與父節點交換，創建大頂堆
if (minNodeIndex != parentNodeIndex) {
swap(arr, parentNodeIndex - 1, minNodeIndex - 1);
// 交換后可能需要重建堆，原父節點可能需要繼續下沉
if (minNodeIndex * 2 <= len) {// 是否有子節點，注，只需判斷是否有左子樹即可知道
adjustNote(arr, minNodeIndex, len);
}
}
}
/**

交換數組中的兩個元素的位置
*
@param array
待交換的數組
@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 + " ");

 }
}



}</pre>