数据结构-排序-堆积排序法

素颜马尾好姑娘i 2023-10-04 16:27 22阅读 0赞

#### 堆积排序法 ####

堆积排序法是选择排序法的改进版，它可以减少在选择排序法中的比较次数，进而减少排序时间。堆积排序法用到了二叉树的技巧，它是利用堆积数来完成排序的。堆积树是一种特殊的二叉树，可以分为最大堆积树和最小堆积树两种。

**最大堆积树**

*  它是一个完全二叉树
 *  所有节点的值都大于或者等于它左右子节点的值
 *  树根是堆积树中最大的

**最小堆积树**

*  它是一个完全二叉树
 *  所有节点的值都小于或等于它左右子节点的值
 *  树根是堆积树中最小的

在排序之前，需要将二叉树转换成堆积树，转化步骤：

假设data=\[32、17、16、24、35、87、65、4、12\]

A\[0\]=32,A\[1\]=17,A\[2\]=16,A\[3\]=24,A\[4\]=35,A\[5\]=87,A\[6\]=65,A\[7\]=4,A\[8\]=12

1.  A\[0\]=32位树根，若A\[1\]大于父节点，则必须互换。此处A\[1\]=17<A\[0\]=32，故不互换
2.  A\[2\]=16<A\[0\],故不互换
3.  A\[3\]=24>A\[1\]=17,故互换
4.  A\[4\]=35>A\[1\]=24,故互换，再与A\[0\]=32比较，A\[1\]=35>A\[0\]=32,故互换
    
    … …
    
    … …

堆积排序就是建立在最大最小堆积树的基础上，以最大堆积树为例，因为根节点是最大的值，所以逐渐取出根节点，然后剩下的元素快速构建堆积树，再次取出根节点，然后剩下的元素快速构建堆积树，重复以上步骤，直到把所有的元素取出，就会得出从大到小的排序

**堆积排序法的分析**

*  在所有情况下，时间复杂度均为O(nlogn)
 *  堆积排序法不  
    \[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-L3aA3MKa-1624702001109)(/home/lnnu/.config/Typora/typora-user-images/image-20210626180608014.png)\]是稳定排序法
 *  只需要一个额外的空间，空间复杂度为O(1)

def heap(data,size):
        for i in range(int(size/2),0,-1):   #建立堆积树节点
            ad_heap(data,i,size-1)
        print()
        print('堆积的内容：',end='')
        for i in range(1,size):
            print('[%2d]'%data[i],end='')
        print('\n')
        for i in range(size-2,0,-1):
            data[i+1],data[1] = data[1],data[i+1]
            ad_heap(data,1,i)
            print('处理过程为：',end='')
            for j in range(1,size):
                print('[%2d]'%data[j],end='')
            print()
    
    def ad_heap(data
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-L3aA3MKa-1624702001109)(/home/lnnu/.config/Typora/typora-user-images/image-20210626180608014.png)],i,size):
        j = 2*i
        tmp = data[i]
        post = 0
        while j <= size and post == 0:
            if j < size:
                if data[j] < data[j+1]:
                    j += 1
            if tmp >= data[j]:
                post = 1
            else:
                data[int(j/2)] = data[j]
                j = 2*j
        data[int(j/2)] = tmp
    
    def main():
        data = [0,5,6,4,8,3,2,7,1]
        size = 9
        print("原始数据为：",end='')
        for i in range(1,size):
            print('[%2d'%data[i],end='')
        heap(data,size)
        print('排序结果为：',end='')
        for i in range(1,size):
            print('[%2d]'%data[i],end='')
    
    if __name__ == '__main__':
        main()

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210626180649381.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA==,size_16,color_FFFFFF,t_70