十大排序算法-------【堆排序】詳解（Java源碼）

堆排序是指利用堆這種資料結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并且同時滿足堆積的性質：即子節點的鍵值或者索引總數小于（或者大于）它的父節點。

1. 算法描述

1. 将初始待排序的序列建構成為大頂堆，此堆為初始的無序區；
2. 将堆頂元素R[1]與最後一個元素R[n]交換，此時得到新的無序區（R1,R2，…Rn-1）和新的有序區（Rn），且滿足R[1,2,…n-1]<=R[n];
3. 由于交換後新的堆頂可能違反堆的性質，是以需要對目前無序區（R1,R2,…Rn-1）調整為新堆，然後再次将R[1]

1. 代碼實作：完全二叉樹有個特性：左邊子節點位置 = 目前父節點的兩倍 + 1，右邊子節點位置 = 目前父節點的兩倍 + 2。
2. 代碼實作：

public class DuiPaiXu2 {



       private static void daDingDui(int[] arrays, int start, int end) {



              // 父節點

              int curr = start;

              // 左右節點

              int left = curr * 2 + 1;

//           int right = curr * 2 + 2;



              // 父節點值

              int temp = arrays[curr];



              for (; left < end; curr = left, left = curr * 2 + 1) {// 将其左子節點變為父節點，将根據其變換後的父節點擷取到左子節點

                    

                     if (left < end && arrays[left] < arrays[left + 1]) {// 判斷左右子節點誰最大

                            left++;// 變為右子節點為父節點，

                     }



                     if (arrays[left] > temp) {// 判斷左右子節點的最大值與目前父節點的值誰大

                            arrays[curr] = arrays[left];

                            arrays[left] = temp;

                     }



              }

       }



       private static void jiaoHuan(int[] arrays, int index1, int index2) {

              int temp = arrays[index1];

              arrays[index1] = arrays[index2];

              arrays[index2] = temp;

       }



       private static void duiPaiXu(int[] arrays) {

              int length = arrays.length;

              int left;



              // 從（n/2-1）--->0周遊，逐漸将待排序序列生成一個大頂堆

              for (left = length / 2 - 1; left > 0; left--) {

                     daDingDui(arrays, left, length - 1);

              }



              // 從最後一個元素開始對序列進行調整，不斷的縮小調整範圍，直到縮小到隻含有第一個元素

              for (left = length - 1; left > 0; left--) {

//                  交換第一個和左子節點元素後，左子葉節點就是序列中最大的元素。

                     jiaoHuan(arrays, 0, left);



                     // 調整剩下的堆序列，保證右子節點為剩下的堆序列中的最大值

                     daDingDui(arrays, 0, left - 1);

              }



       }



       public static void main(String[] args) {

              int arrays[] = { 20, 30, 90, 40, 70, 110, 60, 10, 100, 50, 80 };



              System.out.println(Arrays.toString(arrays));

              duiPaiXu(arrays);

              System.out.println(Arrays.toString(arrays));



       }

}