2020-11-29：手写代码：堆排序。
原创2020-11-29：手写代码：堆排序。
原创
福大大架构师每日一题
修改于 2020-11-30 14:37:22
修改于 2020-11-30 14:37:22
福哥答案2020-11-29：
1，先让整个数组都变成大根堆结构，建立堆的过程:
①从上到下的方法，时间复杂度为O(N*logN)。
②从下到上的方法，时间复杂度为O(N)。
2，把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆，一直周而复始，时间复杂度为O(N*logN)。
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 执行结果如下：
在这里插入图片描述
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读