跨境o2o网站建设方案,网站设计要点 优帮云,易语言做网站爆破工具,广东如何做网络推广营销策划方案目录
前言
堆排序
代码示例
1. 算法包
2. 堆排序代码
3. 模拟程序
4. 运行程序
5. 从大到小排序
堆排序的思想
堆排序的实现逻辑
1. 构建最大堆
2. 排序
循环次数测试
假如 10 条数据进行排序
假如 20 条数据进行排序
假如 30 条数据进行排序
假设 5000 条数据…目录
前言
堆排序
代码示例
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/pkgfmt
)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. 动态数据排序
当数据集合动态变化如插入、删除操作频繁堆排序的堆结构可以高效地维护数据的排序状态 总的来说堆排序因其良好的最坏情况时间复杂度以及对动态数据排序的友好性在多种场景下都是非常有用的排序算法
