Go 數據結構之堆排序示例詳解
堆排序
堆排序是一種樹形選擇排序算法。
簡單選擇排序算法每次選擇一個關鍵字最小的記錄需要 O(n) 的時間,而堆排序選擇一個關鍵字最小的記錄需要 O(nlogn)的時間。
堆可以看作一棵完全二叉樹的順序存儲結構。
在這棵完全二叉樹中,如果每個節點的值都大於等於左邊孩子的值,稱為大根堆(最大堆、又叫大頂堆)。如果每個節點的值都小於等於左邊孩子的值,稱為小根堆(最小堆,小頂堆)。
可以,用數學符號表示如下:
堆排序過程
- 構建初始堆
- 在輸出堆的頂層元素後,從上到下進行調整,將頂層元素與其左右子樹的根節點進行比較,並將最小的元素交換到堆的頂部;然後不斷調整直到葉子節點得到新的堆。
假如,{1, 7, 9, 2, 4, 6, 3, 5, 8}
建堆,然後進行堆排序輸出。
動畫顯示
- 初始化堆,建堆操作圖畫演示:
首先根據無序序列 {1, 7, 9, 2, 4, 6, 3, 5, 8}
按照完全二叉樹的順序構建一棵完全二叉樹,如圖:
然後從最後一個分支節點 n/2開始調整堆,這裡 9 / 2 = 4:
然後從 n/2−1 開始調整,即序號 3 開始調整,接著從 n/2-2 執行調整操作,如圖所示:
一直重復到序號為 1 的節點:
最終通過此次調整堆,得到新的堆為 [9, 8, 6, 7, 4, 1, 3, 5, 2]
,得到新的堆後開始堆排序過程
開始堆排序
構建完初始堆後,此時,我們可以進入堆排序,從上面的方法中,
我們可以已知我們構建的最大堆的堆頂是最大的記錄,可以可以將堆頂交換到最後一個元素的位置,然後執行堆頂下沉操作,然後再執行堆調整操作(新的堆頂也是最大值),直到剩餘一個節點,得到一個有序序列。
此時,我們又可以進行堆調整操作,如下圖:
堆調整完畢,開始把新的堆頂 8 和最後一個記錄 2 進行交換,然後將堆頂下沉,調整為堆,如下圖所示:
從此我們得到新的堆頂 7 ,然後把 7 跟最後一個元素 3 進行交換,7 下沉,然後堆調整,慢慢得到堆頂 6 和 堆頂5,如圖所示:
然後是 3 下沉:
最後,堆頂 2 與最後一個記錄 1 進行交換,隻剩一個節點,堆排序結束,如下圖所示:
我們得到的新的序列按序號讀取數據,就是一個有序序列。
代碼實現
最後,我們用代碼來檢驗一下我們的動畫過程是否正確,如下:
package main import "fmt" // 調整堆 func adjustHeap(array []int, currentIndex int, maxLength int) { var noLeafValue = array[currentIndex] // 當前非葉子節點 // j 指向左孩子 // 當前非葉子節點的左節點為:2 * currentIndex + 1 for j := 2*currentIndex + 1; j <= maxLength; j = currentIndex*2 + 1 { if j < maxLength && array[j] < array[j+1] { // 如果有右孩子,且左孩子比右孩子小 j++ // j 指向右孩子 } if noLeafValue >= array[j] { break // 非葉子節點大於孩子節點,跳過不交換 } array[currentIndex] = array[j] // 移動到當前節點的父節點 currentIndex = j // j 指向交換後的新位置,繼續向下比較 } array[currentIndex] = noLeafValue // 放在合適的位置 } // 初始化堆 func createHeap(array []int, length int) { // 建堆 for i := length / 2; i >= 0; i-- { adjustHeap(array, i, length-1) } } func heapSort(array []int, length int) { for i := length - 1; i > 0; i-- { array[0], array[i] = array[i], array[0] adjustHeap(array, 0, i-1) } } func main() { var unsorted = []int{1, 7, 9, 2, 4, 6, 3, 5, 8} var length = len(unsorted) fmt.Println("建堆之前:") for i := 0; i < length; i++ { fmt.Printf("%d,", unsorted[i]) } fmt.Println() fmt.Println("建堆之後:") createHeap(unsorted, length) for i := 0; i < length; i++ { fmt.Printf("%d,", unsorted[i]) } fmt.Printf("\n堆排序之後: \n") heapSort(unsorted, length) for i := 0; i < length; i++ { fmt.Printf("%d,", unsorted[i]) } }
運行結果:
[Running] go run "e:\Coding Workspaces\LearningGoTheEasiestWay\Go 數據結構\堆排序\main.go"
建堆之前:
1,7,9,2,4,6,3,5,8,
建堆之後:
9,8,6,7,4,1,3,5,2,
堆排序之後:
1,2,3,4,5,6,7,8,9,
可以看到,創建堆的結果 9,8,6,7,4,1,3,5,2
和排序結果 1,2,3,4,5,6,7,8,9
都是和我們圖中的堆一樣,所以說圖看懂瞭代碼也就變得有意思瞭。
總結
總結一下堆排序的復雜度:
時間復雜度:堆排序主要耗費時間在初始堆和反復調整堆上,所以時間復雜度為 O(nlogn)O(nlogn)O(nlogn)
空間復雜度:交換記錄需要一個輔助空間,所以空間復雜度為 O(1)O(1)O(1)
穩定性:堆排序多次交換關鍵字,可能會發生相等關鍵字排序前後位置不一樣的情況,所以不穩定
推薦大傢都自己畫圖體驗一下堆排序的過程,這中間設計除瞭涉及到算法的精妙,也能體會到二叉樹的遍歷過程。
以上就是Go 數據結構之堆排序示例詳解的詳細內容,更多關於Go 數據結構堆排序的資料請關註WalkonNet其它相關文章!