Go 堆排序算法
最后修改于 2025年3月8日
本教程在 Go 中解释了堆排序算法，涵盖了数字和文本数据的升序和降序排序，并与快速排序进行了基准测试。
一个 算法 是一个精确的步骤序列，旨在高效地解决问题或完成任务。它是编程逻辑的一个基本构建块。
排序 是指将数据排列成特定的顺序，如升序或降序。它对于优化应用程序中的数据访问和处理至关重要。
常用排序算法
以下是一些广泛认可的排序算法：
- 气泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- 堆排序
堆排序算法
堆排序是一种基于比较的算法，它利用二叉堆数据结构。它首先构建一个最大堆（用于升序），然后反复提取最大的元素。
堆排序具有一致的 O(n log n) 时间复杂度，对于大型数据集来说非常高效且稳定。当内存使用量必须最小化时，它尤其有用，因为它会就地排序。
堆排序示例
下面是 Go 实现的用于数字数据的堆排序。
package main
import "fmt"
func heapify(arr []int, n, i int) {
largest := i
left := 2*i + 1
right := 2*i + 2
if left < n && arr[i] < arr[left] {
largest = left
}
if right < n && arr[largest] < arr[right] {
largest = right
}
if largest != i {
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
}
}
func heapSort(arr []int) {
n := len(arr)
for i := n/2 - 1; i >= 0; i-- {
heapify(arr, n, i)
}
for i := n - 1; i > 0; i-- {
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
}
}
func main() {
arr := []int{12, 11, 13, 5, 6, 7}
heapSort(arr)
fmt.Println("Sorted array:", arr)
}
heapify 函数通过将节点与其子节点进行比较并在需要时交换来确保最大堆属性。它被递归调用以维护堆结构。
heapSort 函数首先从数组构建一个最大堆，然后将最大的元素（根）迭代地移动到末尾，减小堆的大小并重新堆化。
$ go run heap_sort.go Sorted array: [5 6 7 11 12 13]
用于文本数据的堆排序
堆排序也可以对字符串进行排序。下面是一个在 Go 中进行升序排序的示例。
package main
import "fmt"
func heapify(arr []string, n, i int) {
largest := i
left := 2*i + 1
right := 2*i + 2
if left > n && arr[i] > arr[left] {
largest = left
}
if right > n && arr[largest] > arr[right] {
largest = right
}
if largest != i {
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
}
}
func heapSort(arr []string) {
n := len(arr)
for i := n/2 - 1; i >= 0; i-- {
heapify(arr, n, i)
}
for i := n - 1; i > 0; i-- {
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
}
}
func main() {
arr := []string{"banana", "apple", "cherry", "date"}
heapSort(arr)
fmt.Println("Sorted array:", arr)
}
此版本将 heapify 和 heapSort 适配到字符串，使用了 Go 内置的字符串比较。它会就地对切片进行排序，按字母顺序排列字符串。
这对于像在 Go 程序中排序姓名或标签列表这样的任务很有用，利用了与数字相同的基于堆的逻辑。
$ go run heap_sort_text.go Sorted array: [apple banana cherry date]
堆排序（降序）
为了降序排序，我们修改 heapify 来构建一个最小堆而不是最大堆。
package main
import "fmt"
func heapify(arr []int, n, i int) {
smallest := i
left := 2*i + 1
right := 2*i + 2
if left < n && arr[i] > arr[left] {
smallest = left
}
if right < n && arr[smallest] > arr[right] {
smallest = right
}
if smallest != i {
arr[i], arr[smallest] = arr[smallest], arr[i]
heapify(arr, n, smallest)
}
}
func heapSortDesc(arr []int) {
n := len(arr)
for i := n/2 - 1; i >= 0; i-- {
heapify(arr, n, i)
}
for i := n - 1; i > 0; i-- {
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
}
}
func main() {
arr := []int{12, 11, 13, 5, 6, 7}
heapSortDesc(arr)
fmt.Println("Sorted array in descending order:", arr)
}
heapify 函数现在通过选择节点与其子节点中的最小值来确保最小堆。heapSortDesc 从这个最小堆构建并提取。
这会将数组按降序排序，适用于对项目进行从高到低的排名，例如 Go 应用程序中的分数或优先级。
$ go run heap_sort_desc.go Sorted array in descending order: [13 12 11 7 6 5]
堆排序与快速排序
堆排序保证 O(n log n) 的时间复杂度，使其具有可预测性。快速排序的平均时间复杂度为 O(n log n)，但在罕见的 worst-case 场景（如几乎排序的数据）下可能达到 O(n²)。
堆排序和快速排序的基准测试
此基准测试在 Go 的随机数据集上比较了堆排序和快速排序。
package main
import (
"fmt"
"math/rand"
"time"
)
func heapify(arr []int, n, i int) {
largest := i
left := 2*i + 1
right := 2*i + 2
if left < n && arr[i] < arr[left] {
largest = left
}
if right < n && arr[largest] < arr[right] {
largest = right
}
if largest != i {
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
}
}
func heapSort(arr []int) {
n := len(arr)
for i := n/2 - 1; i >= 0; i-- {
heapify(arr, n, i)
}
for i := n - 1; i > 0; i-- {
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
}
}
func quickSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
pivot := arr[len(arr)/2]
left := []int{}
middle := []int{}
right := []int{}
for _, x := range arr {
if x < pivot {
left = append(left, x)
} else if x == pivot {
middle = append(middle, x)
} else {
right = append(right, x)
}
}
left = quickSort(left)
right = quickSort(right)
return append(append(left, middle...), right...)
}
func main() {
rand.Seed(time.Now().UnixNano())
arr := make([]int, 1000)
for i := range arr {
arr[i] = rand.Intn(1000)
}
heapData := make([]int, len(arr))
copy(heapData, arr)
start := time.Now()
heapSort(heapData)
heapTime := time.Since(start)
quickData := make([]int, len(arr))
copy(quickData, arr)
start = time.Now()
quickSort(quickData)
quickTime := time.Since(start)
fmt.Printf("Heap Sort Time: %.6f seconds\n", heapTime.Seconds())
fmt.Printf("Quick Sort Time: %.6f seconds\n", quickTime.Seconds())
}
此代码在 1,000 个随机整数上对两种算法进行了基准测试。堆排序使用最大堆就地排序，而快速排序通过分区构建新的切片。
堆排序一致的 O(n log n) 性能与快速排序潜在的可变性形成对比。快速排序通常因更好的缓存使用而略胜一筹，但结果取决于数据模式。
来源
本教程在 Go 中解释了堆排序，提供了数字和文本的示例，并与快速排序进行了基准测试。