go的堆排序

堆的概念：堆是一种图的树状结构，被用于实现“优先队列”。

1.首先创建堆：

   堆的特性：

   （1）.完全二叉树；

   （2）.每一个节点都大于其左右子节点；

   （3）.根节点最大（大堆）；

   （4）.左子节点2i+1，由子节点2i+2，父节点(i-1)/2；

package main import "fmt" func parentNode(i int) int{ return (i - 1)/2 } //左节点 func leftNode(i int) int{ return 2*i + 1 } //右节点 func rightNode(i int) int{ return 2*i + 2 } //创建heap func buildHeap(heap []int) { length := len(heap) for i := length/2 - 1; i >= 0; i-- { maxHeap(heap, i, length) } } func maxHeap(heap []int, i int, length int) { left := leftNode(i) right := rightNode(i) largest := 0 if left < length && heap[left] > heap[i] { largest = left }else { largest = i } if right < length && heap[right] > heap[largest] { largest = right } if largest != i { heap[i], heap[largest] = heap[largest], heap[i] //需要继续比较其父节点 maxHeap(heap, largest, length) } } func main() { a := []int{1, 24, 35, 343, 463, 46, 34, 35, 12, 123, 245, 413, 5, 132} buildHeap(a) fmt.Println(a) }

2.堆排序

package main import "fmt" //堆的特性 //1.是完全二叉树 //2.每一个节点都大于子节点(大堆) //3.根节点最大 //4.左子节点2i+1, 由子节点2i+2, 父节点(i-1)/2 func parentNode(i int) int{ return (i - 1)/2 } //左节点 func leftNode(i int) int{ return 2*i + 1 } //右节点 func rightNode(i int) int{ return 2*i + 2 } //创建heap func buildHeap(heap []int) int{ length := len(heap) for i := length/2 - 1; i >= 0; i-- { maxHeap(heap, i, length) } return length } func maxHeap(heap []int, i int, length int) { left := leftNode(i) right := rightNode(i) largest := 0 if left < length && heap[left] > heap[i] { largest = left }else { largest = i } if right < length && heap[right] > heap[largest] { largest = right } if largest != i { heap[i], heap[largest] = heap[largest], heap[i] //需要继续比较起父节点 maxHeap(heap, largest, length) } } func main() { a := []int{1, 24, 35, 343, 463, 46, 34, 35, 12, 123, 245, 413, 5, 132} heapLength := buildHeap(a) fmt.Println(a) for i := len(a) - 1; i >= 0; i-- { a[i], a[0] = a[0], a[i] heapLength-- maxHeap(a, 0, heapLength) } fmt.Println(a) }

　　

　　

转载于:https://www.cnblogs.com/xingyunshizhe/p/11311754.html