Java 樹結構實際應用 一（堆排序2秒排完800w數據）
堆排序
1 堆排序基本介紹
1) 堆排序是利用堆這種數據結構而設計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復
雜度均為 O(nlogn)，它也是不穩定排序。
2) 堆是具有以下性質的完全二叉樹：每個結點的值都大於或等於其左右孩子結點的值，稱為大頂堆, 注意 : 沒有
要求結點的左孩子的值和右孩子的值的大小關係。
3) 每個結點的值都小於或等於其左右孩子結點的值，稱為小頂堆
4) 大頂堆舉例說明
5) 小頂堆舉例說明
6) 一般升序採用大頂堆，降序採用小頂堆
2 堆排序基本思想
堆排序的基本思想是：
1) 將待排序序列構造成一個大頂堆
2) 此時，整個序列的最大值就是堆頂的根節點。
3) 將其與末尾元素進行交換，此時末尾就為最大值。
4) 然後將剩餘 n-1 個元素重新構造成一個堆，這樣會得到 n 個元素的次小值。如此反覆執行，便能得到一個有序
序列了。
可以看到在構建大頂堆的過程中，元素的個數逐漸減少，最後就得到一個有序序列了
3 堆排序步驟圖解說明
要求：給你一個數組 {4,6,8,5,9} , 要求使用堆排序法，將數組升序排序。
步驟一 構造初始堆。將給定無序序列構造成一個大頂堆（一般升序採用大頂堆，降序採用小頂堆)。
原始的數組 [4, 6, 8, 5, 9]
1) .假設給定無序序列結構如下
2) .此時我們從最後一個非葉子結點開始（葉結點自然不用調整，第一個非葉子結點arr.length/2-1=5/2-1=1，也就是下面的 6 結點），從左至右，從下至上進行調整
3) .找到第二個非葉節點 4，由於[4,9,8]中 9 元素最大，4 和 9 交換。
4) 這時，交換導致了子根[4,5,6]結構混亂，繼續調整，[4,5,6]中 6 最大，交換 4 和 6。
此時，我們就將一個無序序列構造成了一個大頂堆。
步驟二 將堆頂元素與末尾元素進行交換，使末尾元素最大。然後繼續調整堆，再將堆頂元素與末尾元素交換，得到第二大元素。如此反覆進行交換、重建、交換.
1) .將堆頂元素 9 和末尾元素 4 進行交換
2) .重新調整結構，使其繼續滿足堆定義
3) .再將堆頂元素 8 與末尾元素 5 進行交換，得到第二大元素 8
4) 後續過程，繼續進行調整，交換，如此反覆進行，最終使得整個序列有序
再簡單總結下堆排序的基本思路：
1).將無序序列構建成一個堆，根據升序降序需求選擇大頂堆或小頂堆;
2).將堆頂元素與末尾元素交換，將最大元素”沉”到數組末端;
3).重新調整結構，使其滿足堆定義，然後繼續交換堆頂元素與當前末尾元素，反覆執行調整+交換步驟，
直到整個序列有序。
4 堆排序代碼實現
要求：給你一個數組 {4,6,8,5,9} , 要求使用堆排序法，將數組升序排序。
說明：
1) 堆排序的速度非常快，在我的機器上 8 百萬數據 2 秒左右。O(nlogn)
2) 代碼實現
package com.lin.tree_0308; import java.text.SimpleDateFormat; import java.util.Arrays; import java.util.Date; public class HeapSort { public static void main(String[] args) { // int[] arr = {4, 6, 8, 5, 9}; // 隨機生成 int[] arr = new int[80000000]; for(int i = 0; i < 80000000; i++) { arr[i] =(int)(Math.random()*8000000); } Date date1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String format1 = simpleDateFormat.format(date1); System.out.println("排序前時間為：" + format1); heapSort(arr); Date date2 = new Date(); String format2= simpleDateFormat.format(date2); System.out.println("排序後時間為：" + format2); } // heapSort public static void heapSort(int[] arr) { int temp = 0; // adjustHeap(arr, 1, arr.length); // System.out.println("第一次：" + Arrays.toString(arr)); // // adjustHeap(arr, 0, arr.length); // System.out.println("第二次：" + Arrays.toString(arr)); // 將無序序列建成一個堆，根據升序需求選擇大頂堆或小頂堆 for(int j = arr.length/2 -1; j >= 0; j--) { adjustHeap(arr, j, arr.length); } // 將堆頂元素與尾元素交換，將最大元素沉到數組尾端 // 重新調整至堆，繼續交換，反覆操作直至整個序列有序 for(int j = arr.length-1; j > 0; j--) { temp = arr[j]; arr[j] = arr[0]; arr[0] = temp; adjustHeap(arr, 0, j); } } // heap /** * * @Description: * @author LinZM * @date 2021-3-11 10:14:16 * @version V1.8 * @param arr 待調整數組 * @param i 表示非葉子節點在數組中的索引 * @param lenght 表示對多少個元素繼續調整，逐漸變小 */ public static void adjustHeap(int[] arr, int i, int length) { // 先取出當前元素的值 int temp = arr[i]; // j = 2 * i + 1 j是i節點的左節點 for(int j = i * 2 + 1; j < length; j = j * 2 + 1) { if(j+1 < length && arr[j] < arr[j+1]) {//右子節點大於左子節點 j++;// j指向有子節點 } if(arr[j] > temp) {// 子節點大於父節點 arr[i] = arr[j]; i = j; } else { break; } } arr[i] = temp; } }
僅供參考，有錯誤還請指出！
有什麼想法，評論區留言，互相指教指教。
覺得不錯的可以點一下右邊的推薦喲
