手写堆排序

手写堆排序

摘要：本文记录使用go语言实现堆排序

堆的构建

• 堆性质： 对于每个小堆，父节点与两个子节点比较，父节点比左子节点大，也比右子节点大。

有五个数： 1,2,3,4,5 分别进行入栈。过程如下

(1) 堆为空时，元素1 放入堆

(2) 取出元素2，挂到元素1后面

(3) 比较元素2，与父元素元素1，由于元素2 比 元素1 大，所以两个元素交换

(4) 元素3 先放入堆最后

(5) 元素3 比父节点大，与父节点交换

(6) 元素4 放到堆最后

(6) 元素4 比父节点你先把给的和反正都吃了元素1 大，所以把元素4 与 元素1 交换

(7) 元素4 比父节点元素3 大，所以把元素4 与 元素3我 交换

(8) 同理，元素5 先放入堆最后，再分别与父节点比较，直到达到堆性质。

代码实现

package main

import "fmt"

// heapify 将父节点与子节点比较，并将最大值放到父节点(用于实现大顶堆)
func heapify(arr []int, n, i int) {
if i >= n {
// 递归退出条件
return
}
// 找出最大的
var prarent = i
var max = prarent
var c1 = prarent*2 + 1
var c2 = prarent*2 + 2
if c1 < n && arr[c1] > arr[max] {
max = c1
}
if c2 < n && arr[c2] > arr[max] {
max = c2
}
// 如果最大节点不是父节点，则最大的节点与父节点交换
if max != prarent {
arr[max], arr[i] = arr[i], arr[max]
// 递归的进行 heapify
heapify(arr, n, max)
}

}

// heapInit 遍历依次heapify
func heapInit(arr []int, n int) {
for i := 0; i < n; i++ {
heapify(arr, n, i)
}
}

// 利用堆实现排序
func heapSort(heapTree []int) {
if len(heapTree) == 0 {
return
}
var heapSize = len(heapTree)
for heapSize > 0 {
// 将堆顶元素放到最后
heapTree[0], heapTree[heapSize-1] = heapTree[heapSize-1], heapTree[0]
heapSize--

// 对堆顶元素执行heapify
heapify(heapTree, heapSize, 0)
}
}

func main() {
arr := []int{2, 1, 10, 3, 5, 4}

heapInit(arr, 6)
fmt.Println(arr) // [10 5 4 3 1 2]

heapSort(arr)

fmt.Println(arr) // 1 2 3 4 5 10

arr = []int{3, 3, 4, 2, 1}

heapInit(arr, 5)
fmt.Println(arr)

heapSort(arr) // [4 3 3 2 1]

fmt.Println(arr) // 1 2 3 3 4

}

原文地址：https://blog.csdn.net/xsw164711368/article/details/142691720

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！