Java 十大排序算法之堆排序刨析
二叉堆是完全二叉樹或者是近似完全二叉樹。
二叉堆滿足二個特性︰
1.父結點的鍵值總是大於或等於(小於或等於)任何一個子節點的鍵值。
2.每個結點的左子樹和右子樹都是一個二叉堆(都是最大堆或最小堆)。
任意節點的值都大於其子節點的值——大頂堆(最後輸出從小到大排)
任意節點的值都小於其子節點的值———小頂堆(最後輸出從大到小排)
堆排序步驟
1.堆化,反向調整使得每個子樹都是大頂或者小頂堆(建堆)
2.按序輸出元素∶把堆頂和最末元素對調,然後調整堆頂元素(排序)
堆排序代碼實現(大頂堆)
public class HeapSort { private static void heapSort(int[] arr) { // 構造初始堆(大頂堆),從第一個非葉子節點開始調整,左右孩子節點中較大的交換到父節點中 for (int i = arr.length / 2 - 1; i >= 0; i--) { heapAdjust(arr, i, arr.length); } // 調整堆結構,交換堆頂元素與末尾元素 for (int j = arr.length - 1; j > 0; j--) { swap(arr, 0, j);// 將堆頂元素與末尾元素進行交換 heapAdjust(arr, 0, j);// 重新對堆進行調整 } } private static void swap(int[] arr, int a, int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } // 調整大頂堆 private static void heapAdjust(int[] arr, int i, int len) { int temp = arr[i], index = 2 * i + 1; while (index < len) { if (index + 1 < len && arr[index] < arr[index + 1]) {// 如果左子結點小於右子結點,index指向右子結點 index += 1; } if (arr[index] > temp) {// 如果子節點大於父節點,將子節點值賦給父節點 arr[i] = arr[index]; i = index; index = 2 * i + 1; } else { break; } } arr[i] = temp; } public static void main(String[] args) { int[] arr = {1,28,3,21,11,7,6,18}; heapSort(arr); System.out.println(Arrays.toString(arr)); } }
時間復雜度:O(nlogN)
到此這篇關於Java 十大排序算法之堆排序刨析的文章就介紹到這瞭,更多相關Java 堆排序內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- 圖解排序算法之希爾排序Java實現
- 堆排序原理及算法代碼詳解
- Java中數組的使用與註意事項詳解(推薦)
- Java實現全排列的三種算法詳解
- java數組算法例題代碼詳解(冒泡排序,選擇排序,找最大值、最小值,添加、刪除元素等)