Gemini永久会员 堆排序 (Heap Sort) in Go

# 堆排序 (Heap Sort) in Go

堆排序是一种基于二叉堆数据结构的比较排序算法。下面是一个完整的Go语言实现：

```go
package main

import "fmt"

// heapSort 堆排序主函数
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[0], arr[i] = arr[i], arr[0]

// 对剩余元素重新构建最大堆
heapify(arr, i, 0)
}
}

// heapify 维护堆的性质
func heapify(arr []int, n, i int) {
largest := i    // 初始化最大值为当前节点
left := 2*i + 1 // 左子节点
right := 2*i + 2 // 右子节点

// 如果左子节点存在且大于当前最大值
if left < n && arr[left] > arr[largest] {
largest = left
}

// 如果右子节点存在且大于当前最大值
if right < n && arr[right] > arr[largest] {
largest = right
}

// 如果最大值不是当前节点，交换并继续堆化
if largest != i {
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
}
}

func main() {
arr := []int{12, 11, 13, 5, 6, 7}
fmt.Println("排序前:", arr)

heapSort(arr)
fmt.Println("排序后:", arr)
}
```

## 算法说明

1. **构建最大堆**：首先将无序数组构建成一个最大堆，这样最大的元素位于堆顶（数组开头）。

2. **排序阶段**：
   – 将堆顶元素（最大值）与数组末尾元素交换
   – 减少堆的大小（排除已排序的最大元素）
   – 对新的堆顶元素进行堆化，使其满足最大堆性质
   – 重复上述过程直到堆的大小为1

## 时间复杂度

– 构建堆的时间复杂度：O(n)
– 每次堆化的时间复杂度：O(log n)
– 总时间复杂度：O(n log n)
– 空间复杂度：O(1)（原地排序）

## 特点

– 不稳定排序算法
– 适合大数据量的排序
– 不需要额外的存储空间（原地排序）
– 实际应用中比快速排序慢，但最坏情况下性能更好（O(n log n) vs 快速排序的O(n²)）

这个实现使用了递归的堆化方法，也可以改为迭代实现以提高性能。