学习回顾算法（堆排序算法）

迷南。 2022-06-05 09:05 207阅读 0赞

## 堆排序算法简介 ##

堆排序（Heapsort）是指利用堆积数（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆要求是每个节点的值都不大于其父节点的值。在数组的非降序排序中，需要使用大根堆。因为最大值一定在堆顶。

## 堆排序原理 ##

堆排序利用了大根堆（或小根堆）堆顶记录的值最大（或最小）这一特征。  
**一、用大根堆排序的基本思想**  
1、先将初始数组A\[0…n\]构成一个大根堆。  
2、将数组中最大的记录（堆顶）和无序区的最后一个元素交换A\[n\]交换，由此得到新的无序区A\[0 … n\]和有序区A\[n\]，且满足A\[0 … n-1\] <= A\[n\]  
3、由于交换后的新根A\[0\]可能违反堆行政，故应该将当前无序区A\[0…n-1\]调整为大根堆。然后再次将A\[0…n-1\]中R\[0\]和该区间的最后一个元素A\[n-1\]交换，由此得到新的无序区A\[0…n-2\]和有序区A\[n-1, n\],满足A\[0…n-2\] <= A\[n-1\]  
…  
知道无序区只有一个元素为止。

**二、大根堆排序算法的基本操作**  
1、建堆，建堆是不断调整堆的过程，从len/2处开始调整，直到第一个节点，此处len是堆中元素的个数。建堆的过程是个线性的过程，从len/2到0处一直调整堆过程。  
2、调整堆：调整堆在构建堆的过程中会用到，而且在堆排序过程中也会用到。利用的思想是比较节点i和其子节点left(i),right(i)，选出三者最大者（或最小者），如果最大（小）者不是节点i而是它的一个孩子节点，那就狡猾节点i和该孩子节点。然后再调用调整堆过程。调整堆过程时间复杂度与堆的深度有关系，是lgn的操作。因为是沿着深度方向调整的。  
3、堆排序：堆排序是利用上面两个过程来进行的。首先是根据元素构建堆。然后取出根节点，将前面len-1个节点进行堆调整过程，然后再将根节点取出，这样一直到所有的节点都取出。

## 算法分析 ##

**1、时间复杂度**  
堆排序过程中建堆的时间复杂度是O(n）只调用一次；调整堆的时间复杂度是lgn。调用了 n-1次。所以排序的时间复杂度为O(nlgn）

**2、空间复杂度**  
直接交换元素即可，空间复杂度为O(1)

**3、稳定性**  
它是不稳定的排序方法。（排序的稳定性是指如果在排序的序列中，存在前后相同的两个元素的话，排序前 和排序后他们的相对位置不发生变化）

## 实例分析 ##

以初始元素为2, 4, 7, 5, 8, 1, 3, 6, 6  
**一、初始元素如下**  
![初始值][SouthEast]  
**二、创建堆**  
1、列表长度为9，调整堆，父节点为第四个，值为8，无子节点

2、父节点递减，取第3个元素，值为5，子节点为第7，第8个元素。由于子节点比父节点大，右子节点不比左子节点大，交换左节点（第7个元素）。  
![交换第3和第7个元素][3_7]  
3、父节点递减，取第2个元素，值为7，左子节点（第5个元素）是1，右子节点（第6个元素）是3。不交换

4、父节点递减，取第1个元素，值为1，左子节点（第3个元素）是6，右子节点（第4个元素）是8，由于右子节点最大，所以和父节点交换。交换第1个元素和第4个元素  
![交换第1个元素和第4个元素][1_4]

5、父节点递减，取第0个元素，值为2，左子节点（第1个元素）是8，右子节点（第7个元素）是7。由于左子节点比右子节点大且比父节点大。所以和父节点交换，交换第0个元素和第一个元素。  
![这里写图片描述][SouthEast 1]  
这时候父节点为第一个元素，值为2，左子节点为6，右子节点为4，左子节点和父节点交换。  
![这里写图片描述][SouthEast 2]  
下一个循环，父节点是3个元素，左子节点是5，右子节点是6，交换父节点和右子节点。  
![这里写图片描述][SouthEast 3]  
**三、堆排序**  
1、第一次排序  
1）创建堆后第0个元素最大。和最后一个元素交换  
![这里写图片描述][SouthEast 4]  
2）调整堆，由于第0个元素值为2，其左子节点第1个元素值为6，右子节点值为7。交换父节点和右子节点。  
![这里写图片描述][SouthEast 5]  
下一个循环，父节点是第2个元素，值为2。左子节点为1，由子节点为3。交换父节点和右子节点。  
![这里写图片描述][SouthEast 6]  
这时候第0个元素最大了。  
3）第0个元素和最后一个元素交换（最后一个是第7个了）  
![这里写图片描述][SouthEast 7]  
**重复步骤2）1），同时未排序区长度逐一减小**

## 代码实现 ##

**1、golang实现**

package main
    
    import (
        "fmt"
    )
    
    func HeadAdjust(values []int, i, length int) {
        var iChild int
        //
        for ; 2*i+1 < length; i = iChild {
            //获取子节点的位置
            iChild = 2*i + 1
            //如果有右子节点的话，获取较大子节点的位置
            if iChild < length-1 && values[iChild+1] > values[iChild] {
                iChild++
            }
            //如果父节点小于较大的子节点的话，交换父子节点，否则调整结束
            if values[i] < values[iChild] {
                values[i], values[iChild] = values[iChild], values[i]
            } else {
                break
            }
        }
    }
    
    func HeadSort(values []int) {
        iLen := len(values)
    
        //构造堆
        for i := iLen / 2; i >= 0; i-- {
            HeadAdjust(values, i, iLen)
            //fmt.Println(values)
        }
    
        //逐个提取最大元素。
        for i := iLen - 1; i > 0; i-- {
            values[0], values[i] = values[i], values[0]
            //fmt.Println(values)
            HeadAdjust(values, 0, i)
            //fmt.Println(values)
        }
    }
    
    func main() {
        values := []int{
       2, 4, 7, 5, 8, 1, 3, 6, 6}
        fmt.Println(values)
        HeadSort(values)
        fmt.Println(values)
        return
    }

打开注释后的结果：

[2 4 7 5 8 1 3 6 6]
    [2 4 7 5 8 1 3 6 6]
    [2 4 7 6 8 1 3 5 6]
    [2 4 7 6 8 1 3 5 6]
    [2 8 7 6 4 1 3 5 6]
    [8 6 7 6 4 1 3 5 2]
    [2 6 7 6 4 1 3 5 8]
    [7 6 3 6 4 1 2 5 8]
    [5 6 3 6 4 1 2 7 8]
    [6 6 3 5 4 1 2 7 8]
    [2 6 3 5 4 1 6 7 8]
    [6 5 3 2 4 1 6 7 8]
    [1 5 3 2 4 6 6 7 8]
    [5 4 3 2 1 6 6 7 8]
    [1 4 3 2 5 6 6 7 8]
    [4 2 3 1 5 6 6 7 8]
    [1 2 3 4 5 6 6 7 8]
    [3 2 1 4 5 6 6 7 8]
    [1 2 3 4 5 6 6 7 8]
    [2 1 3 4 5 6 6 7 8]
    [1 2 3 4 5 6 6 7 8]
    [1 2 3 4 5 6 6 7 8]
    [1 2 3 4 5 6 6 7 8]

[SouthEast]: /images/20220605/ee1b4fdab8434c7dbe41b4ac822d2359.png
[3_7]: /images/20220605/f0d571914e354c8f99a66436356b2351.png
[1_4]: /images/20220605/777c037ca5984237a85090f526fe7114.png
[SouthEast 1]: /images/20220605/530d8366afe04137a327c91ff34b20a3.png
[SouthEast 2]: /images/20220605/b5e1ab8211dd4e3b86eef589edbad5eb.png
[SouthEast 3]: /images/20220605/0604650270e24ef080aac4ce8e6f1b71.png
[SouthEast 4]: /images/20220605/064988855f2248bd974651a4a859240b.png
[SouthEast 5]: /images/20220605/0b9120e786c8432eab2ac4d855109097.png
[SouthEast 6]: /images/20220605/0ba6f4ed74264fe29940f38468150e47.png
[SouthEast 7]: /images/20220605/3f9dae7b74844a368f8c305b0364578d.png