排序算法：堆排序，golang实现

目录

前言

堆排序

代码示例

1. 算法包

2. 堆排序代码

3. 模拟程序

4. 运行程序

5. 从大到小排序

堆排序的思想

堆排序的实现逻辑

1. 构建最大堆

2. 排序

循环次数测试

假如 10 条数据进行排序

假如 20 条数据进行排序

假如 30 条数据进行排序

假设 5000 条数据，对比 冒泡、选择、插入、快速、归并

堆排序的适用场景

1. 大数据集排序

2. 外部排序

3. 优先级队列

4. 动态数据排序

---

前言

在实际场景中，选择合适的排序算法对于提高程序的效率和性能至关重要，本节课主要讲解"堆排序"的适用场景及代码实现。

堆排序

堆排序（Heap Sort）是一种基于比较的排序算法，它利用堆这种数据结构所设计。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。在堆排序算法中，我们通常采用最大堆（每个父节点的值都大于或等于其子节点的值）来进行排序。

代码示例

下面我们使用Go语言实现一个堆排序

1. 算法包

创建一个 pkg/algorithm.go

touch pkg/algorithm.go

（如果看过上节课的快速排序，则已存在该文件，我们就不需要再创建了）

2. 堆排序代码

打开 pkg/algorithm.go 文件，代码如下

从小到大 排序

package pkg// BubbleSort 冒泡排序
...// SelectionSort 选择排序
...// InsertionSort 插入排序
...// QuickSort 快速排序
...// partition 分区操作
...// 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[i], arr[0] = arr[0], arr[i]// 调用 max heapify on the reduced heapheapify(arr, i, 0)}
}// heapify 将以 i 为根的子树调整为最大堆
func heapify(arr []int, n int, i int) {largest := i // 初始化最大为根l := 2*i + 1 // 左子节点r := 2*i + 2 // 右子节点// 如果左子节点大于根if l < n && arr[l] > arr[largest] {largest = l}// 如果右子节点大于当前的最大值if r < n && arr[r] > arr[largest] {largest = r}// 如果最大值不是根if largest != i {arr[i], arr[largest] = arr[largest], arr[i] // 交换// 递归地堆化受影响的子树heapify(arr, n, largest)}
}

3. 模拟程序

打开 main.go 文件，代码如下：

package mainimport ("demo/pkg""fmt"
)func main() {// 定义一个切片，这里我们模拟 10 个元素arr := []int{84, 353, 596, 848, 425, 849, 166, 521, 228, 573}fmt.Println("Original data:", arr) // 先打印原始数据pkg.HeapSort(arr)                  // 调用堆排序fmt.Println("New data:  ", arr)    // 后打印排序后的数据
}

4. 运行程序

go run main.go

能发现， Original data 后打印的数据，正是我们代码中定义的切片数据，顺序也是一致的。

New Data 后打印的数据，则是经过堆排序后的数据，是从小到大的。

5. 从大到小排序

如果需要 从大到小 排序也是可以的，在代码里，需要将两个 if 判断比较的 符号 进行修改。

修改 pkg/algorithm.go 文件：

package pkg// BubbleSort 冒泡排序
...// SelectionSort 选择排序
...// InsertionSort 插入排序
...// QuickSort 快速排序
...// partition 分区操作
...// 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[i], arr[0] = arr[0], arr[i]// 调用 max heapify on the reduced heapheapify(arr, i, 0)}
}// heapify 将以 i 为根的子树调整为最大堆
func heapify(arr []int, n int, i int) {largest := i // 初始化最大为根l := 2*i + 1 // 左子节点r := 2*i + 2 // 右子节点// 如果左子节点小于根if l < n && arr[l] < arr[largest] {largest = l}// 如果右子节点小于当前的最大值if r < n && arr[r] < arr[largest] {largest = r}// 如果最大值不是根if largest != i {arr[i], arr[largest] = arr[largest], arr[i] // 交换// 递归地堆化受影响的子树heapify(arr, n, largest)}
}

只需要一丁点的代码即可

从 package pkg 算第一行，上面示例中在第四十四行代码，第四十九行代码，我们将 ">" 改成了 "<" ，这样就变成了 从大到小排序了

堆排序的思想

• 利用堆的性质：堆排序利用堆的性质，通过不断调整堆来使得每次都能从堆顶取出当前序列的最大（或最小）元素，从而达到排序的目的
• 原地排序：堆排序是一种原地排序算法，它只需要用到 O(1) 的额外空间来进行排序（除了输入的数组外，不需要使用其他数据结构）
• 不稳定性：堆排序是一种不稳定的排序算法，因为在调整堆的过程中，可能会改变相同元素的相对顺序
• 时间复杂度：堆排序的时间复杂度是 O(n log n)，这主要来自于构建最大堆和每次调整堆的时间复杂度

堆排序的实现逻辑

堆排序主要分为两个步骤：

1. 构建最大堆

• 将待排序的序列构造成一个最大堆，此时，整个序列的最大值就是堆顶的根节点
• 构建最大堆的过程是从最后一个非叶子节点开始（即 n/2-1 位置，因为数组是从 0 开始索引的），对每个非叶子节点调用 heapify 函数，使其和其子树满足最大堆的性质

2. 排序

• 将堆顶元素（最大值）与堆数组的末尾元素进行交换，此时末尾就是最大值
• 由于堆的大小减少 1，我们再次将堆顶元素调整为最大值，以满足最大堆的性质
• 重复这个过程，直到堆的大小为 1，算法结束

循环次数测试

参照上面示例进行测试（因考虑到每次手动输入 10 条、20 条、30 条数据太繁琐，所以我写了一个函数，帮助我自动生成 0到1000 的随机整数）

假如 10 条数据进行排序

总计循环了 32 次

假如 20 条数据进行排序

总计循环了 79 次

假如 30 条数据进行排序

总计循环了 136 次

假设 5000 条数据，对比 冒泡、选择、插入、快速、归并

• 冒泡排序：循环次数 12,502,499 次
• 选择排序：循环次数 12,502,499 次
• 插入排序：循环次数 6,323,958 次
• 快速排序：循环次数 74,236 次
• 堆排序：循环次数 59,589 次
• 归并排序：循环次数 60,288 次

堆排序的适用场景

堆排序特别适用于以下场景

1. 大数据集排序

由于堆排序的时间复杂度是 O(n log n)，在处理大数据集时效率较高

2. 外部排序

当数据太大，不能全部加载到内存时，可以使用堆排序进行外部排序，因为它只需要读取一次输入数据，然后逐步输出排序结果

3. 优先级队列

堆经常被用作优先级队列的实现方式，堆排序可以看作是从无序的优先队列中重建有序的优先队列的过程

4. 动态数据排序

当数据集合动态变化（如插入、删除操作频繁），堆排序的堆结构可以高效地维护数据的排序状态

总的来说，堆排序因其良好的最坏情况时间复杂度，以及对动态数据排序的友好性，在多种场景下都是非常有用的排序算法