今天我們不刷力扣了，我們來復習（手撕）一下數據結構中的八大排序算法之一，堆排序

基本概念：

? ? ?堆是一種特殊的樹形數據結構，即完全二叉樹。

堆分為大頂堆和小頂堆：

大頂堆：每個節點的值都大于或等于其兩個子節點的值，在堆排序算法中用于升序排序。

小頂堆：每個節點的值都小于或等于其兩個子節點的值，在堆排序算法中用于降序排序。

映射為數組：

代碼實現：

    //堆排序public static void heapSort(int[] arr) {//構造大根堆heapInsert(arr);int size = arr.length;while (size > 1) {//固定最大值swap(arr, 0, size - 1);size--;//構造大根堆heapify(arr, 0, size);}}//構造大根堆（通過新插入的數上升）public static void heapInsert(int[] arr) {for (int i = 0; i < arr.length; i++) {//當前插入的索引int currentIndex = i;//父結點索引int fatherIndex = (currentIndex - 1) / 2;//如果當前插入的值大于其父結點的值,則交換值，并且將索引指向父結點//然后繼續和上面的父結點值比較，直到不大于父結點，則退出循環while (arr[currentIndex] > arr[fatherIndex]) {//交換當前結點與父結點的值swap(arr, currentIndex, fatherIndex);//將當前索引指向父索引currentIndex = fatherIndex;//重新計算當前索引的父索引fatherIndex = (currentIndex - 1) / 2;}}}//將剩余的數構造成大根堆（通過頂端的數下降）public static void heapify(int[] arr, int index, int size) {int left = 2 * index + 1;int right = 2 * index + 2;while (left < size) {int largestIndex;//判斷孩子中較大的值的索引（要確保右孩子在size范圍之內）if (arr[left] < arr[right] && right < size) {largestIndex = right;} else {largestIndex = left;}//比較父結點的值與孩子中較大的值，并確定最大值的索引if (arr[index] > arr[largestIndex]) {largestIndex = index;}//如果父結點索引是最大值的索引，那已經是大根堆了，則退出循環if (index == largestIndex) {break;}//父結點不是最大值，與孩子中較大的值交換swap(arr, largestIndex, index);//將索引指向孩子中較大的值的索引index = largestIndex;//重新計算交換之后的孩子的索引left = 2 * index + 1;right = 2 * index + 2;}}//交換數組中兩個元素的值public static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}

算法思路：

排序步驟：?

? ? ? 1.構造一個大頂堆（或小頂堆），取堆頂數字（也就是最大值或最小值）

? ? ? ? 2.再將剩下的數字構建一個大頂堆（或小頂堆），取堆頂數字（也就是剩下值當中的最大值（或最小值））

? ? ? ? 3.重復以上操作，直到取完堆中的數字，最后得到一個從大到小（或從小到大）排序的序列

基本思路：

將所有元素構成一個堆的形式，然后比較每一個二叉樹，將最大的或最小的與根節點元素互換位置，最后將最頂根節點取出，再從左到右、從下到上的方式將尾節點放到最頂根節點上，再重復上述操作進行排序取出最大或最小元素，以此類推，直到所有元素取出。

?

平均時間復雜度：O（）

學習參考：?

堆排序算法（圖解詳細流程）-CSDN博客