golang堆排序怎么實(shí)現(xiàn)

小億
112
2023-10-26 16:27:56

Golang堆排序的實(shí)現(xiàn)步驟如下：

  1. 首先，創(chuàng)建一個(gè)函數(shù)heapify用于將給定的數(shù)組或切片轉(zhuǎn)換為一個(gè)最大堆。最大堆的定義是父節(jié)點(diǎn)的值大于或等于其子節(jié)點(diǎn)的值。
func heapify(arr []int, n int, i int) {
	largest := i  // 將當(dāng)前節(jié)點(diǎn)標(biāo)記為最大值
	left := 2*i + 1  // 左子節(jié)點(diǎn)的索引
	right := 2*i + 2  // 右子節(jié)點(diǎn)的索引

	// 如果左子節(jié)點(diǎn)存在且大于根節(jié)點(diǎn)，則將最大節(jié)點(diǎn)的索引更新為左子節(jié)點(diǎn)
	if left < n && arr[left] > arr[largest] {
		largest = left
	}

	// 如果右子節(jié)點(diǎn)存在且大于根節(jié)點(diǎn)，則將最大節(jié)點(diǎn)的索引更新為右子節(jié)點(diǎn)
	if right < n && arr[right] > arr[largest] {
		largest = right
	}

	// 如果最大節(jié)點(diǎn)的索引不是根節(jié)點(diǎn)，則將最大節(jié)點(diǎn)和根節(jié)點(diǎn)交換，并遞歸地對(duì)交換后的子樹(shù)進(jìn)行堆化
	if largest != i {
		arr[i], arr[largest] = arr[largest], arr[i]
		heapify(arr, n, largest)
	}
}
  1. 接下來(lái)，創(chuàng)建一個(gè)函數(shù)heapSort來(lái)執(zhí)行堆排序。
func heapSort(arr []int) {
	n := len(arr)

	// 構(gòu)建最大堆（初始化堆）
	for i := n/2 - 1; i >= 0; i-- {
		heapify(arr, n, i)
	}

	// 逐個(gè)提取堆中的元素，并進(jìn)行堆排序
	for i := n - 1; i >= 0; i-- {
		// 將當(dāng)前根節(jié)點(diǎn)（最大值）與數(shù)組的最后一個(gè)元素交換
		arr[0], arr[i] = arr[i], arr[0]

		// 重新構(gòu)建最大堆，但不包括已經(jīng)排序的元素
		heapify(arr, i, 0)
	}
}
  1. 最后，調(diào)用heapSort函數(shù)來(lái)對(duì)給定的數(shù)組進(jìn)行堆排序。
func main() {
	arr := []int{12, 11, 13, 5, 6, 7}
	heapSort(arr)
	fmt.Println("排序后的數(shù)組：", arr)
}

這樣就完成了使用Golang實(shí)現(xiàn)堆排序的過(guò)程。輸出結(jié)果將會(huì)是[5 6 7 11 12 13]。

0 踩