package main

import "fmt"

func main() { arr := []int{6, 1, 2, 7, 9, 3, 4, 5, 10, 8} heapSort(arr) fmt.Println("---") fmt.Println(arr) }

//堆排序 func heapSort(arr []int) { //求数组长度 //根据堆的规律，假设子节点的规律，假设子节点的坐标为i //左子节点坐标为2i+1,右子节点坐标为2i+2 //父节点的坐标为（i-1）/2. 此处可以计算无论最后一位数字在做左子节点，还是右子节点。父节点的坐标一定是（i-1）/2。 golang中/取整 //假设切片长度是len（arr），那么最后一位的坐标序号为len(arr)-1,可计算出父节点的位置为（len(arr)-1）/2 length := len(arr) last_node := length - 1 //建立最大堆，最大堆的概念就是父节点总是比子节点数字大。arr[0]最大 buildMaxheap(arr) //此处的含义是将堆的堆首与堆尾交换的过程，即为将最大值换到最后，最小值放到最先，然后再对arr[:n-1}执行此递归的过程 //比如 312 -> 21 3-->1 2 3=123 for i := last_node; i > 0; i-- { arr[0], arr[i] = arr[i], arr[0] heapify(arr[:i], 0) } }

//建最大最大堆，进行循环 func buildMaxheap(arr []int) { length := len(arr) last_node := length - 1 parent := (last_node - 1) / 2 for i := parent; i >= 0; i-- { heapify(arr, i)

}

}

//通过下标进行最大值比较过程 func heapify(arr []int, i int) { length := len(arr) left := 2i + 1 right := 2i + 2 max := i if left < length && arr[left] > arr[max] { max = left } if right < length && arr[right] > arr[max] { max = right } if max != i { arr[max], arr[i] = arr[i], arr[max] heapify(arr, max) //此处是向下递归，目的就是建立最大堆，因为比较的过程并不能保证最大堆,只是让他们换了位置。

}

}