堆排序golang实现

堆排序的原理与实现

在计算机科学中，堆排序（Heap Sort）是一种基于堆数据结构的排序算法。该算法使用最大堆或最小堆来进行排序，具体取决于升序还是降序的需求。

堆排序的原理

堆排序的基本思想是通过构建一个二叉堆（Heap），并利用堆的性质进行排序。堆是一个完全二叉树，可以分为两种类型：最大堆和最小堆。

最大堆满足父节点的值大于等于它的子节点，最小堆则相反，父节点的值小于等于它的子节点。在堆排序算法中，我们使用最大堆来进行升序排序。

堆排序的步骤

1. 将待排序的数据构建成最大堆。

2. 交换堆顶元素（最大值）和最后一个元素。

3. 将剩余的元素继续构建最大堆，重复步骤2。

4. 重复执行步骤2和步骤3，直到整个数组有序。

堆排序的实现

下面是用golang实现堆排序的代码：

package main

import (
	"fmt"
)

// 调整堆
func adjustHeap(arr []int, length int, parent int) {
	temp := arr[parent] // 取出当前父节点
	child := 2*parent + 1
	for child < length {
		// 找到两个子节点中较大的一个
		if child+1 < length && arr[child] < arr[child+1] {
			child++
		}
		// 如果父节点大于等于子节点，则跳出循环
		if arr[parent] >= arr[child] {
			break
		}
		// 子节点上浮
		arr[parent] = arr[child]
		parent = child
		child = 2*parent + 1
	}
	arr[parent] = temp // 将父节点放到最终位置
}

// 堆排序
func heapSort(arr []int) {
	length := len(arr)
	// 构建最大堆
	for i := length/2 - 1; i >= 0; i-- {
		adjustHeap(arr, length, i)
	}
	// 排序
	for i := length - 1; i > 0; i-- {
		// 交换堆顶元素和最后一个元素
		arr[0], arr[i] = arr[i], arr[0]
		// 重新调整堆
		adjustHeap(arr, i, 0)
	}
}

func main() {
	arr := []int{10, 7, 8, 9, 1, 5}
	heapSort(arr)
	fmt.Println("排序结果：", arr)
}

以上代码通过调用adjustHeap函数将待排序的数组构建成最大堆，并实现了堆排序算法。在main函数中定义了一个待排序的数组，经过heapSort函数进行排序后打印结果。

堆排序的时间复杂度和空间复杂度

堆排序的时间复杂度为O(nlogn)，其中n为待排序数组的长度。堆排序的空间复杂度为O(1)，原地排序。

总结

堆排序是一种高效的排序算法，利用堆数据结构的特性可以快速定位最值，并通过重复选择最值来实现排序。它的主要思想是通过构建最大堆来实现升序排序，或者构建最小堆来实现降序排序。虽然堆排序的时间复杂度较高，但是它具备了原地排序和稳定性的特点，适用于处理大数据量的排序任务。