Go數(shù)據(jù)結(jié)構(gòu)之堆排序示例詳解

第Go數(shù)據(jù)結(jié)構(gòu)之堆排序示例詳解目錄堆排序堆排序過(guò)程動(dòng)畫顯示開(kāi)始堆排序代碼實(shí)現(xiàn)總結(jié)

堆排序

堆排序是一種樹(shù)形選擇排序算法。

簡(jiǎn)單選擇排序算法每次選擇一個(gè)關(guān)鍵字最小的記錄需要O(n)的時(shí)間，而堆排序選擇一個(gè)關(guān)鍵字最小的記錄需要O(nlogn)的時(shí)間。

堆可以看作一棵完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)。

在這棵完全二叉樹(shù)中，如果每個(gè)節(jié)點(diǎn)的值都大于等于左邊孩子的值，稱為大根堆（最大堆、又叫大頂堆）。如果每個(gè)節(jié)點(diǎn)的值都小于等于左邊孩子的值，稱為小根堆（最小堆，小頂堆）。

可以，用數(shù)學(xué)符號(hào)表示如下：

堆排序過(guò)程

構(gòu)建初始堆在輸出堆的頂層元素后，從上到下進(jìn)行調(diào)整，將頂層元素與其左右子樹(shù)的根節(jié)點(diǎn)進(jìn)行比較，并將最小的元素交換到堆的頂部；然后不斷調(diào)整直到葉子節(jié)點(diǎn)得到新的堆。

假如，{1,7,9,2,4,6,3,5,8}建堆，然后進(jìn)行堆排序輸出。

動(dòng)畫顯示

初始化堆，建堆操作圖畫演示：

首先根據(jù)無(wú)序序列{1,7,9,2,4,6,3,5,8}按照完全二叉樹(shù)的順序構(gòu)建一棵完全二叉樹(shù)，如圖：

然后從最后一個(gè)分支節(jié)點(diǎn)n/2開(kāi)始調(diào)整堆，這里9/2=4:

然后從n/21開(kāi)始調(diào)整，即序號(hào)3開(kāi)始調(diào)整，接著從n/2-2執(zhí)行調(diào)整操作，如圖所示：

一直重復(fù)到序號(hào)為1的節(jié)點(diǎn)：

最終通過(guò)此次調(diào)整堆，得到新的堆為[9,8,6,7,4,1,3,5,2]，得到新的堆后開(kāi)始堆排序過(guò)程

開(kāi)始堆排序

構(gòu)建完初始堆后，此時(shí)，我們可以進(jìn)入堆排序，從上面的方法中，

我們可以已知我們構(gòu)建的最大堆的堆頂是最大的記錄，可以可以將堆頂交換到最后一個(gè)元素的位置，然后執(zhí)行堆頂下沉操作，然后再執(zhí)行堆調(diào)整操作（新的堆頂也是最大值），直到剩余一個(gè)節(jié)點(diǎn)，得到一個(gè)有序序列。

此時(shí)，我們又可以進(jìn)行堆調(diào)整操作，如下圖：

堆調(diào)整完畢，開(kāi)始把新的堆頂8和最后一個(gè)記錄2進(jìn)行交換，然后將堆頂下沉，調(diào)整為堆，如下圖所示：

從此我們得到新的堆頂7，然后把7跟最后一個(gè)元素3進(jìn)行交換，7下沉，然后堆調(diào)整，慢慢得到堆頂6和堆頂5，如圖所示：

然后是3下沉：

最后，堆頂2與最后一個(gè)記錄1進(jìn)行交換，只剩一個(gè)節(jié)點(diǎn)，堆排序結(jié)束，如下圖所示：

我們得到的新的序列按序號(hào)讀取數(shù)據(jù)，就是一個(gè)有序序列。

代碼實(shí)現(xiàn)

最后，我們用代碼來(lái)檢驗(yàn)一下我們的動(dòng)畫過(guò)程是否正確，如下：

packagemain

import"fmt"

//調(diào)整堆

funcadjustHeap(array[]int,currentIndexint,maxLengthint){

varnoLeafValue=array[currentIndex]//當(dāng)前非葉子節(jié)點(diǎn)

//j指向左孩子

//當(dāng)前非葉子節(jié)點(diǎn)的左節(jié)點(diǎn)為：2*currentIndex+1

forj:=2*currentIndex+1;j=maxLength;j=currentIndex*2+1{

ifjmaxLengtharray[j]array[j+1]{//如果有右孩子，且左孩子比右孩子小

j++//j指向右孩子

ifnoLeafValue=array[j]{

break//非葉子節(jié)點(diǎn)大于孩子節(jié)點(diǎn)，跳過(guò)不交換

array[currentIndex]=array[j]//移動(dòng)到當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)

currentIndex=j//j指向交換后的新位置，繼續(xù)向下比較

array[currentIndex]=noLeafValue//放在合適的位置

//初始化堆

funccreateHeap(array[]int,lengthint){

//建堆

fori:=length/2;ii--{

adjustHeap(array,i,length-1)

funcheapSort(array[]int,lengthint){

fori:=length-1;ii--{

array[0],array[i]=array[i],array[0]

adjustHeap(array,0,i-1)

funcmain(){

varunsorted=[]int{1,7,9,2,4,6,3,5,8}

varlength=len(unsorted)

fmt.Println("建堆之前：")

fori:=0;ilength;i++{

fmt.Printf("%d,",unsorted[i])

fmt.Println()

fmt.Println("建堆之后：")

createHeap(unsorted,length)

fori:=0;ilength;i++{

fmt.Printf("%d,",unsorted[i])

fmt.Printf("\n堆排序之后:\n")

heapSort(unsorted,length)

fori:=0;ilength;i++{

fmt.Printf("%d,",unsorted[i])

運(yùn)行結(jié)果：

[Running]gorune:\CodingWorkspaces\LearningGoTheEasiestWay\Go數(shù)據(jù)結(jié)構(gòu)\堆排序\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,

可以看到，創(chuàng)建堆的結(jié)果9,8,6,7,4,1,3,5,2和排序結(jié)果1,2,3,4,5,6,7,8,9都是和我們圖中的堆一樣，所以說(shuō)圖看懂了代碼也就變得有意思了。

總結(jié)

總結(jié)一下堆排序的復(fù)雜度：

時(shí)間復(fù)雜度：堆排序主要耗費(fèi)時(shí)間在初始堆和反復(fù)調(diào)整堆上，所以時(shí)間復(fù)雜度為O(nlogn)O(nlogn)O(nlogn)

空間復(fù)雜度：交換記錄需要一個(gè)輔助空間，所以空間復(fù)雜度為O(1)O(1)O(1)

穩(wěn)定性：堆排序