golang实现堆排序

算法题:
给定一个整型数组,将数组的中的元素按升序排序。

基本思路:
操作:排序
输入:无序整型数组
输出:有序整型数组

这里操作采用堆排序算法,堆排序的基本步骤如下:

1. 将整型数组构造成大顶堆结构
2. 返回堆顶元素
3. 减少堆的长度,有如下情形:
   a. 若堆的长度等于0,跳转到第4步
   b. 若堆的长度大于0,跳转到第2步
4. 返回有序数组

堆排序算法有个关键步骤是构建堆的过程,堆的定义如下:

堆是一个满二叉树,根元素的值大于左右子树所有节点的值,并且左右子树也是一个堆

从堆的定义可以看出,堆的定义是一个递归定义,针对这种递归定义的数据结构,往往会涉及到递归算法。

对于树的构造,一般性的有两种方式,一种是自上而下,另一种是自下而上,至于采用那种方式方便,要依据具体的情况。堆的构造过程是自下而上的方式。这种方式有个好处,每个小堆是否满足堆的性质,只要查看堆顶的元素是否满足堆的性质,如果不满足,可以将根和左右子节点的值进行比较,取得最大的值交换根元素的值,然后继续考虑被交换的位置。这个过程听起来复杂,但是实施起来并不复杂。

常理,到这里就可以进行编码了,但是这里我还是要继续的多讲一些东西。

堆排序算法和其他基本排序算法比起来,它的构造逻辑也是属于简单逻辑,这种逻辑得益于堆的定义,堆是一个满二叉树,也就是说堆可以使用数组进行表示,结点的父子关系可以通过数组的下标运算所得,另外结点之间的关系,可以简化成父节点和左右子节点的关系,父节点的值只要比左右子节点的值大就可以了,而左右子节点所在的左右子树又可以递归的使用这个性质。最重要的是,堆的调整是不需要进行节点调整的(如果你知道红黑树的实现,就可以体会这句话)。

好了,现在我们可以实现堆排序,代码如下:

package main
import "fmt"
// Heap 定义堆排序过程中使用的堆结构
type Heap struct {
 arr []int // 用来存储堆的数据
 size int // 用来标识堆的大小
}
// adjustHeap 用于调整堆,保持堆的固有性质
func adjustHeap(h Heap, parentNode int) {
 leftNode := parentNode*2 + 1
 rightNode := parentNode*2 + 2
 maxNode := parentNode
 if leftNode < h.size && h.arr[maxNode] < h.arr[leftNode] {
 maxNode = leftNode
 }
 if rightNode < h.size && h.arr[maxNode] < h.arr[rightNode] {
 maxNode = rightNode
 }
 if maxNode != parentNode {
 h.arr[maxNode], h.arr[parentNode] = h.arr[parentNode], h.arr[maxNode]
 adjustHeap(h, maxNode)
 }
}
// createHeap 用于构造一个堆
func createHeap(arr []int) (h Heap) {
 h.arr = arr
 h.size = len(arr)
 for i := h.size / 2; i >= 0; i-- {
 adjustHeap(h, i)
 }
 return
}
// heapSort 使用堆对数组进行排序
func heapSort(arr []int) {
 h := createHeap(arr)
 for h.size > 0 {
 // 将最大的数值调整到堆的末尾
 h.arr[0], h.arr[h.size-1] = h.arr[h.size-1], h.arr[0]
 // 减少堆的长度
 h.size--
 // 由于堆顶元素改变了,而且堆的大小改变了,需要重新调整堆,维持堆的性质
 adjustHeap(h, 0)
 }
}
func main() {
 // 测试代码
 arr := []int{9, 8, 7, 6, 5, 1, 2, 3, 4, 0}
 fmt.Println(arr)
 heapSort(arr)
 fmt.Println(arr)
}

最后说一句,程序员想提升自己的编码能力,不仅需要不停的训练,而且还要多多思考。

有疑问加站长微信联系(非本文作者)

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
• 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传