2020-11-29:手写代码:堆排序。

举报
福大大架构师每日一题 发表于 2020/11/29 22:11:46 2020/11/29
【摘要】 福哥答案2020-11-29:1,先让整个数组都变成大根堆结构,建立堆的过程:    1)从上到下的方法,时间复杂度为O(N*logN)。    2)从下到上的方法,时间复杂度为O(N)。2,把堆的最大值和堆末尾的值交换,然后减少堆的大小之后,再去调整堆,一直周而复始,时间复杂度为O(N*logN)。3,堆的大小减小成0之后,排序完成。golang代码如下:```gopackage clas...

福哥答案2020-11-29:
1,先让整个数组都变成大根堆结构,建立堆的过程:
    1)从上到下的方法,时间复杂度为O(N*logN)。
    2)从下到上的方法,时间复杂度为O(N)。
2,把堆的最大值和堆末尾的值交换,然后减少堆的大小之后,再去调整堆,一直周而复始,时间复杂度为O(N*logN)。
3,堆的大小减小成0之后,排序完成。

golang代码如下:

```go
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  执行结果如下:

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。