怎么用Java編程堆排序技術

本篇內容介紹了“怎么用Java編程堆排序技術”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

 堆排序基本介紹

1. 堆排序是利用堆這種數據結構而設計的一種排序算法，堆排序是一種選擇排序，它的最好、最壞、平均時間復雜度均為O(nlogn)，它是不穩定排序。

2. 堆是具有以下性質的完全二叉樹：每個節點的值都大于等于其左右子節點的值，稱為大頂堆，注意：沒有要求最有子節點值得大小關系。

3. 每個節點的值都小于等于左右子節點的值，稱為小頂堆。

4. 大頂堆的特點：arr[i ] >= arr[2i+1] && arr[i] >= arr[2i+2], i 對應第幾個節點，i  從編號0開始。

5. 小頂堆的特點: arr[i ] <= arr[2i+1] && arr[i] <= arr[2i+2], i  對應第幾個節點，i 從編號0開始。

6. 一般升序采用大頂堆，降序采用小頂堆。

堆排序基本思想

1. 將待排序序列構造成一個大頂堆

2. 此時，整個序列的最大值就是堆頂的根節點。

3. 將其與數組末尾元素進行交換，此時末尾就為最大值。

4. 然后將剩余 n-1 個元素重新構建成一個堆，這樣會得到n個元素的次小值。如此反復執行，便能得到一個有序序列。

可以看到在構建大頂堆的過程中，元素的個數逐漸減少，最后得到一個有序序列了

一個數組中非葉子節點的個數 = arr.length / 2 - 1

代碼案例

package com.xie.tree;  public class HeapSort {     public static void main(String[] args) {         int[] arr = new int[8000000];         for (int i = 0; i < 8000000; i++) {             arr[i] = (int) (Math.random() * 800000000);         }         long start = System.currentTimeMillis();         heapSort(arr);         long end = System.currentTimeMillis();         System.out.println("耗時：" + (end - start) + "ms");         /**          * 800萬數據          * 堆排序!!          * 耗時：2482ms          */     }      public static void heapSort(int[] arr) {         int temp = 0;         System.out.println("堆排序!!");          //1.將無序序列構成一個堆，根據升序降序需求選擇大頂堆或小頂堆         for (int i = arr.length / 2 - 1; i >= 0; i--) {             adjustHeap(arr, i, arr.length);         }         //2.將堆頂元素與數組末尾元素交換，將最大元素"沉"到數組末端         //3.重新調整結構，使其滿足堆定義，然后繼續交換堆頂元素與當前末尾元素，反復執行調整+交換步驟，直到整個序列有序。         for (int j = arr.length - 1; j > 0; j--) {             //交換             temp = arr[j];             arr[j] = arr[0];             arr[0] = temp;             adjustHeap(arr, 0, j);         }     }      /**      * 將一個數組（二叉樹），調整成一個大頂堆      * 功能：完成將以 i 對應的非葉子節點的樹調整成大頂堆      *      * @param arr    待調整的數組      * @param i      表示非葉子節點在數組的索引      * @param length 表示對多少個元素進行調整,length在逐漸減少      */     public static void adjustHeap(int[] arr, int i, int length) {         //先取出當前元素的值，保存在臨時變量         int temp = arr[i];         //k = 2 * i + 1  是i節點的左子節點         for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {             //當左子節點值小于右子節點值             if (k + 1 < length && arr[k] < arr[k + 1]) {                 k++;//k指向右子節點             }              //如果子節點值大于父節點值             if (arr[k] > temp) {                 //把較大的值賦給當前節點                 arr[i] = arr[k];                 //!!! i指向k 繼續循環比較                 i = k;             } else {                 break;             }         }          //當for循環結束后，我們已經將以 i 為父節點的樹的最大值，放在了最頂。          //將temp值放到調整后的位置         arr[i] = temp;     } }

“怎么用Java編程堆排序技術”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！