堆排序算法 golang实现

文章目录

堆排序算法 golang实现

算法描述

算法描述：首先建一个堆，然后调整堆，调整过程是将节点和子节点进行比较，将其中最大的值变为父节点，递归调整调整次数lgn,最后将根节点和尾节点交换再n次调整。

算法步骤

创建大根堆或者小根堆。
调整堆。
交换首尾节点(为了维持一个完全二叉树才要进行收尾交换)。

代码

实现1:

package main

import "fmt"

func HeapSortMax(arr []int, length int) []int {
	if length < 1 {
		return arr
	}
	depth := length / 2 - 1 //二叉树深度
	for i := depth; i >= 0; i-- {
		topmax := i    //假定最大的位置就在i的位置
		leftchild := 2 * i + 1
		rightchild := 2 * 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
}

func main() {
	arr := []int{1, 9, 10, 30, 2, 5, 45, 8, 63, 234, 12}
	fmt.Println(HeapSort(arr))
}

输出结果：

[1 2 5 8 9 10 12 30 45 63 234]

实现2:

package main

import "fmt"

func heapify(arr []int, n int, i int) {
	//堆的维护
	largest := i  		//i为当前父节点的下标
	lson := i * 2 + 1   //左孩子
	rson := i * 2 + 2   //右孩子
	if lson < n && arr[largest] < arr[lson] {
		largest = lson
	}
	if rson < n && arr[largest] < arr[rson] {
		largest = rson
	}
	if largest != i {
		arr[largest], arr[i] = arr[i], arr[largest]
		heapify(arr, n, largest)
	}
}

func HeapSort(arr []int, n int)  {
	//建堆
	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]
		heapify(arr, i, 0)
	}
}

func main() {
	arr := []int{1, 9, 10, 30, 2, 5, 45, 8, 63, 234, 12}
	HeapSort(arr, len(arr))
	fmt.Println(arr)
}