02. 堆排序算法
<h1>1. 堆排序算法</h1>
<p>算法描述：首先建一个堆，然后调整堆，调整过程是将节点和子节点进行比较，将 其中最大的值变为父节点，递归调整调整次数lgn,最后将根节点和尾节点交换再n次 调整<strong>O(nlgn)</strong>.</p>
<h4>算法步骤</h4>
<ul>
<li>创建最大堆或者最小堆（我是最小堆）</li>
<li>调整堆</li>
<li>
<p>交换首尾节点(为了维持一个完全二叉树才要进行收尾交换)</p>
<p>package sort</p>
<p>import "fmt"</p>
<p>//堆排序
func main() {
arr := []int{1, 9, 10, 30, 2, 5, 45, 8, 63, 234, 12}
fmt.Println(HeapSort(arr))
}
func HeapSortMax(arr []int, length int) []int {
// length := len(arr)
if length <= 1 {
return arr
}
depth := length/2 - 1 //二叉树深度
for i := depth; i >= 0; i-- {
topmax := i //假定最大的位置就在i的位置
leftchild := 2<em>i + 1
rightchild := 2</em>i + 2
if leftchild <= length-1 && arr[leftchild] > arr[topmax] { //防止越过界限
topmax = leftchild
}
if rightchild <= length-1 && arr[rightchild] > arr[topmax] { //防止越过界限
topmax = rightchild
}
if topmax != i {
arr[i], arr[topmax] = arr[topmax], arr[i]
}
}
return arr
}
func HeapSort(arr []int) []int {
length := len(arr)
for i := 0; i < length; i++ {
lastlen := length - i
HeapSortMax(arr, lastlen)
if i < length {
arr[0], arr[lastlen-1] = arr[lastlen-1], arr[0]
}
}
return arr
}</p>
</li>
</ul>