Go 数据结构之堆排序示例详解

08-29 27阅读 0评论

堆排序

排序是一种树形选择排序算法

简单选择排序算法每次选择一个关键字最小的记录需要 O(n) 的时间,而堆排序选择一个关键字最小的记录需要 O(nlogn)的时间。

堆可以看作一棵完全二叉树的顺序存储结构

在这棵完全二叉树中,如果每个节点的值都大于等于左边孩子的值,称为大根堆(最大堆、又叫大顶堆)。如果每个节点的值都小于等于左边孩子的值,称为小根堆(最小堆,小顶堆)。

可以,用数学符号表示如下:

Go 数据结构之堆排序示例详解

堆排序过程

构建初始堆在输出堆的顶层元素后,从上到下进行调整,将顶层元素与其左右子树的根节点进行比较,并将最小的元素交换到堆的顶部;然后不断调整直到叶子节点得到新的堆。

假如,{1, 7, 9, 2, 4, 6, 3, 5, 8}建堆,然后进行堆排序输出。

动画显示

初始化堆,建堆操作图画演示:

首先根据无序序列 {1, 7, 9, 2, 4, 6, 3, 5, 8}按照完全二叉树的顺序构建一棵完全二叉树,如图:

Go 数据结构之堆排序示例详解

然后从最后一个分支节点n/2开始调整堆,这里 9/ 2 = 4:

Go 数据结构之堆排序示例详解

然后从 n/2−1 开始调整,即序号 3开始调整,接着从 n/2-2 执行调整操作,如图所示:

一直重复到序号为 1的节点:

Go 数据结构之堆排序示例详解

最终通过此次调整堆,得到新的堆为 [9, 8, 6, 7, 4, 1, 3, 5, 2] ,得到新的堆后开始堆排序过程

开始堆排序

构建完初始堆后,此时,我们可以进入堆排序,从上面的方法中,

我们可以已知我们构建的最大堆的堆顶是最大的记录,可以可以将堆顶交换到最后一个元素的位置,然后执行堆顶下沉操作,然后再执行堆调整操作(新的堆顶也是最大值),直到剩余一个节点,得到一个有序序列。

Go 数据结构之堆排序示例详解

此时,我们又可以进行堆调整操作,如下图:

Go 数据结构之堆排序示例详解

堆调整完毕,开始把新的堆顶 8和最后一个记录 2进行交换,然后将堆顶下沉,调整为堆,如下图所示:

Go 数据结构之堆排序示例详解

从此我们得到新的堆顶 7 ,然后把 7跟最后一个元素 3进行交换,7 下沉,然后堆调整,慢慢得到堆顶 6 和 堆顶5,如图所示:

Go 数据结构之堆排序示例详解

然后是 3下沉:

Go 数据结构之堆排序示例详解

最后,堆顶 2 与最后一个记录 1进行交换,只剩一个节点,堆排序结束,如下图所示:

Go 数据结构之堆排序示例详解

我们得到的新的序列按序号读取数据,就是一个有序序列。

代码实现

最后,我们用代码来检验一下我们的动画过程是否正确,如下:

package main import "fmt" // 调整堆 func adjustHeap(array []int, currentIndex int, maxLength int) { var noLeafValue = array[currentIndex] // 当前非叶子节点 // j 指向左孩子 // 当前非叶子节点的左节点为:2 * currentIndex + 1 for j := 2*currentIndex + 1; j <= maxLength; j = currentIndex*2 + 1 { if j < maxLength && array[j] < array[j+1] { // 如果有右孩子,且左孩子比右孩子小 j++ // j 指向右孩子 } if noLeafValue >= array[j] { break // 非叶子节点大于孩子节点,跳过不交换 } array[currentIndex] = array[j] // 移动到当前节点的父节点 currentIndex = j   // j 指向交换后的新位置,继续向下比较 } array[currentIndex] = noLeafValue // 放在合适的位置 } // 初始化堆 func createHeap(array []int, length int) { // 建堆 for i := length / 2; i >= 0; i-- { adjustHeap(array, i, length-1) } } func heapSort(array []int, length int) { for i := length - 1; i > 0; i-- { array[0], array[i] = array[i], array[0] adjustHeap(array, 0, i-1) } } func main() { var unsorted = []int{1, 7, 9, 2, 4, 6, 3, 5, 8} var length = len(unsorted) fmt.Println("建堆之前:") for i := 0; i < length; i++ { fmt.Printf("%d,", unsorted[i]) } fmt.Println() fmt.Println("建堆之后:") createHeap(unsorted, length) for i := 0; i < length; i++ { fmt.Printf("%d,", unsorted[i]) } fmt.Printf("\n堆排序之后: \n") heapSort(unsorted, length) for i := 0; i < length; i++ { fmt.Printf("%d,", unsorted[i]) } } 

运行结果:

[Running] Go run "e:\Coding Workspaces\LearningGOTheEasiestWay\go 数据结构\堆排序\main.go"建堆之前:1,7,9,2,4,6,3,5,8,建堆之后:9,8,6,7,4,1,3,5,2,堆排序之后:1,2,3,4,5,6,7,8,9,

可以看到,创建堆的结果 9,8,6,7,4,1,3,5,2和排序结果 1,2,3,4,5,6,7,8,9都是和我们图中的堆一样,所以说图看懂了代码也就变得有意思了。

总结

总结一下堆排序的复杂度:

时间复杂度:堆排序主要耗费时间在初始堆和反复调整堆上,所以时间复杂度为 O(nlogn)O(nlogn)O(nlogn)

空间复杂度:交换记录需要一个辅助空间,所以空间复杂度为 O(1)O(1)O(1)

稳定性:堆排序多次交换关键字,可能会发生相等关键字排序前后位置不一样的情况,所以不稳定

推荐大家都自己画图体验一下堆排序的过程,这中间设计除了涉及到算法的精妙,也能体会到二叉树的遍历过程。

以上就是Go 数据结构之堆排序示例详解的详细内容,更多关于Go 数据结构堆排序的资料请关注云初冀北其它相关文章!

免责声明
本站提供的资源,都来自网络,版权争议与本站无关,所有内容及软件的文章仅限用于学习和研究目的。不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负,我们不保证内容的长久可用性,通过使用本站内容随之而来的风险与本站无关,您必须在下载后的24个小时之内,从您的电脑/手机中彻底删除上述内容。如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。侵删请致信E-mail:goliszhou@gmail.com
$

发表评论

表情:
评论列表 (暂无评论,27人围观)

还没有评论,来说两句吧...