福哥答案2020-11-29:
1,先让整个数组都变成大根堆结构,建立堆的过程:
1)从上到下的方法,时间复杂度为O(NlogN)。
2)从下到上的方法,时间复杂度为O(N)。
2,把堆的最大值和堆末尾的值交换,然后减少堆的大小之后,再去调整堆,一直周而复始,时间复杂度为O(NlogN)。
3,堆的大小减小成0之后,排序完成。
golang代码如下:
package class04 import ( "fmt" "testing" ) /* 堆排序 1,先让整个数组都变成大根堆结构,建立堆的过程: 1)从上到下的方法,时间复杂度为O(N*logN) 2)从下到上的方法,时间复杂度为O(N) 2,把堆的最大值和堆末尾的值交换,然后减少堆的大小之后,再去调整堆,一直周而复始,时间复杂度为O(N*logN) 3,堆的大小减小成0之后,排序完成 与堆有关的题目 已知一个几乎有序的数组。几乎有序是指,如果把数组排好顺序的话,每个元素移动的距离一定不超过k,并且k相对于数组长度来说是比较小的。 请选择一个合适的排序策略,对这个数组进行排序。 */ //go test -v -test.run TestHeapSort func TestHeapSort(t *testing.T) { fmt.Println("----------------------") if true { arr := []int{1, 5, 3, 9, 7, 2, 1, 2, 2, 8} fmt.Println("原数组 = ", arr) heapSort(arr) fmt.Println("排序后 = ", arr) fmt.Println("\r\n----------------------") } } // 堆排序额外空间复杂度O(1) func heapSort(arr []int) { if len(arr) < 2 { return } // O(N*logN) // for (int i = 0; i < arr.length; i++) { // O(N) // heapInsert(arr, i); // O(logN) // } for i := len(arr) - 1; i >= 0; i-- { heapify(arr, i, len(arr)) } heapSize := len(arr) heapSize-- swap(arr, 0, heapSize) // O(N*logN) for heapSize > 0 { // O(N) heapify(arr, 0, heapSize) // O(logN) heapSize-- swap(arr, 0, heapSize) // O(1) } } // arr[index]刚来的数,往上 func heapInsert(arr []int, index int) { for arr[index] > arr[(index-1)/2] { swap(arr, index, (index-1)/2) index = (index - 1) / 2 } } // arr[index]位置的数,能否往下移动 func heapify(arr []int, index int, heapSize int) { left := index*2 + 1 // 左孩子的下标 for left < heapSize { // 下方还有孩子的时候 // 两个孩子中,谁的值大,把下标给largest // 1)只有左孩子,left -> largest // 2) 同时有左孩子和右孩子,右孩子的值<= 左孩子的值,left -> largest // 3) 同时有左孩子和右孩子并且右孩子的值> 左孩子的值, right -> largest largest := 0 if left+1 < heapSize && arr[left+1] > arr[left] { largest = left + 1 } else { largest = left } // 父和较大的孩子之间,谁的值大,把下标给largest if arr[largest] > arr[index] { } else { largest = index } if largest == index { break } swap(arr, largest, index) index = largest left = index*2 + 1 } } func swap(arr []int, i int, j int) { tmp := arr[i] arr[i] = arr[j] arr[j] = tmp }
敲命令 go test -v -test.run TestHeapSort 执行结果如下: