go語言堆排序怎么實現

157次閱讀

共計 866 個字符，預計需要花費 3 分鐘才能閱讀完成。

Go 語言堆排序的實現步驟如下：

首先，定義一個用于進行堆調整的函數 adjustHeap，該函數接受三個參數：待調整的切片 arr，當前需要調整的節點的下標 i，以及堆的大小 length。
在 adjustHeap 函數中，首先獲取當前節點的值，然后計算出其左子節點和右子節點的下標。
比較左子節點和右子節點的值，取較大值的下標作為 maxIndex。
判斷當前節點與其子節點的大小關系，如果當前節點的值小于 maxIndex 所對應的子節點的值，則交換兩者的值，并遞歸調用 adjustHeap 函數，以保證堆的性質。
在主函數中，首先構建一個初始堆，通過調用 adjustHeap 函數來從最后一個非葉子節點開始進行堆調整。
將堆頂元素與最后一個元素交換，然后將堆的大小減一，并調用 adjustHeap 函數對堆頂元素進行調整，以保持堆的性質。
重復步驟 6，直到堆的大小為 1，此時，整個序列已經有序。

下面是具體的代碼實現：

package main

import "fmt"

func adjustHeap(arr []int, i, length int) {temp := arr[i]
	for k := i*2 + 1; k < length; k = k*2 + 1 {if k+1 < length && arr[k] < arr[k+1] {k++}
		if arr[k] > temp {arr[i] = arr[k]
			i = k
		} else {break
		}
	}
	arr[i] = temp
}

func heapSort(arr []int) {length := len(arr)
	for i := length/2 - 1; i >= 0; i-- {adjustHeap(arr, i, length)
	}
	for i := length - 1; i > 0; i-- {arr[0], arr[i] = arr[i], arr[0]
		adjustHeap(arr, 0, i)
	}
}

func main() {arr := []int{9, 8, 7, 6, 5, 4, 3, 2, 1}
	heapSort(arr)
	fmt.Println(arr)
}