堆排序

堆排序過程：（用到遞歸演算法）

主函數中:

public void main(String[] args)
1. 定義初始化數組：int[] a = new int[]{.............}
2. 迴圈建堆 調用建堆函數：
　　for (int i = 0; i < a.length - 1; i++) {
　　　　buildMaxHeap(a, a.length - 1 - i); //建堆函數
　　　　swap(a, 0, a.length - i - 1); // 置換數據函數
　　}
3. 輸出排序好的數組：System.out.println(Arrays.toString(a));

建堆函數中:

public static void buildMaxHeap(int[]data, int lastIndex){}//data: 數組 lastIndex 最後的節點
1. 從最後的一個節點的父節點開始進行迴圈：for(int i = (lastIndex - 1)/2; i >= 0; i--){
2. k保存正在判斷的節點： int k = i：
3. 判斷當前k節點的子節點存在，若存在進入迴圈：while(2 * k + 1 <= lastIndex>)
4. 當k節點的子節點存在時，biggerIndex儲存k節點左節點索引 int biggerIndex = 2 * k + 1
5. 判斷k節點的右節點是否存在， if(biggerIndex < lastIndex){
6. 若存在則比較k節點的左右節點的大小 if(data[biggerIndex]<data[biggerIndex +１])；
7. 若右節點的值比左節點的值大，則將biggerIndex的值+1（指向右節點） ： biggerIndex++
8. 將k節點的值和biggerIndex節點的值進行比較，若 k 節點的值比biggerIndex節點的值小，則交換k節點和biggerIndex節點的值,反之，break：
　　if (data[k] < data[biggerIndex]) {
　　　　// 交換他們
　　　　swap(data, k, biggerIndex);
　　　　// 將biggerIndex賦予k，開始while迴圈的下一次迴圈，重新保證k節點的值大於其左右子節點的值
　　　　k = biggerIndex;
　　} else {
　　　　break;
　　}

交換函數中:

public static void swap(int[] a , int i ,int j){}對值進行交換：
　　int temp = a[i];
　　a[i] = a[j];
　　a[j] = temp;

 1 import java.util.Arrays;
 2 
 3 public class HeapSort {
 4     public static void main(String[] args) {
 5         int a[] = { 1, 23, 5, 4, 8, 6, 3, 2, 1, 5, 8, 4, 4, 5, 2, 1 };
 6         // 迴圈建堆
 7         for (int i = 0; i < a.length - 1; i++) {
 8             buildMaxHeap(a, a.length - 1 - i); // 建堆函數
 9             swap(a, 0, a.length - i - 1); // 交換函數
10         }
11         System.out.println(Arrays.toString(a));
12     }
13 
14     private static void buildMaxHeap(int[] data, int lastIndex) {
15         // TODO Auto-generated method stub
16         for (int i = (lastIndex - 1) / 2; i >= 0; i--) { // 從最後一個節點的父節點開始
17             int k = i;
18             // 2k+1 <= lastIndex 判斷是否存在子節點
19             while (k * 2 + 1 <= lastIndex) {
20                 int biggerIndex = 2 * k + 1;// 用biggerIndex保存k節點的左孩子的節點
21                 if (biggerIndex < lastIndex) {// 判斷k節點的右孩子（節點）是否存在
22                     if (data[biggerIndex] < data[biggerIndex + 1]) {// 若右孩子存在，判斷左右孩子的值得大小
23                         biggerIndex++;// 若右孩子比左孩子大，biggerIndex記錄右孩子的節點值biggerIndex++
24                     }
25                 }
26                 // 判斷K節點的值是否小於其較大子節點（孩子）的值
27                 if (data[k] < data[biggerIndex]) {
28                     swap(data, k, biggerIndex);// 若k節點的值小於其較大子孩子的值，交換k節點和biggerIndex節點的值
29                     k = biggerIndex;// 將biggerIndex（較大子節點的索引）賦給 k
30                 } else {
31                     // 若k節點的值不小於其較大子節點的值則break;（跳出迴圈）
32                     break;
33                 }
34             }
35         }
36     }
37 
38     private static void swap(int[] data, int i, int j) {
39         // TODO Auto-generated method stub
40         int temp = data[i];
41         data[i] = data[j];
42         data[j] = temp;
43     }
44 }