数据结构算法--4堆排序

简介: 堆排序过程概述:建立大根堆,将堆顶最大元素移出并替换为末尾元素,调整保持堆性质,重复此过程直至堆为空,实现排序。时间复杂度为O(nlogn)。Python中可用heapq模块进行堆操作。

堆排序过程:


>建立堆(大根堆)


>得到堆顶元素,为最大元素


>去掉堆顶,将堆最后一个元素放到堆顶,此时可通过一次调整使堆重新有序


>堆顶元素为第二大元素


>重复步骤3,直到堆变空



时是建立堆后大根堆模型

将9拿下来,为了节约内存,提高利用率,可以将9放到3(最后一个元素),然后3放到堆顶,再此经过调整,3放到合适的位置并且除了9的最大元素又被调到堆顶。

每次经过调整,整个堆的最后几个元素不断形成有序区,即,大根堆在不断变小

首先我们要调整一个无序列表等成为一个大根堆(先将列表看成一个堆)




我们要从最末尾开始调整,才能保证大元素一步步被调上去




我们可以看出是从最后一个元素的根节点开始调整,即5,9,1...


列表长为n=len(li),所以5的下标为(n-2)//2


我们可以先写调整部分的代码:


def sift(li,low,high):   # 堆的第一个元素和最后一个元素
    i=low
    j=2*i+1       # j刚开始是左孩子
    tmp=li[low]   # 把堆顶存起来
    while j<=high: # 只要j位置有数,没有越界
        if j+1<=high and li[j+1]>li[j]:   # 保证右孩子不越界,因为最右侧列表是有序区,不是堆
            j=j+1    # j指向右孩子          # 与左右孩子对比前,先左右孩子比较
        if li[j]>tmp:
            li[i]=li[j]
            i=j
            j=2*i+1
        else:
            li[i]=tmp
            break
    else:
        li[i]=tmp  # 到最后了,通过计算左孩子已经超出high了


堆排序的代码:


def heap_sort(li):
    n=len(li)
    for i in range((n-2)//2,-1,-1):   # 倒着走,一直往左遍历,第一个元素的前一个元素就是-1下标
        # i表示建堆时调整的部分的根的下标
        sift(li,i,n-1)   # 避免麻烦直接选最后,high作用只有一个就是确定别越界
    print(li)
    # 建堆完成了
    for i in range(n-1,-1,-1):     # 一直确定堆最后元素
        # i一直指向当前堆的最后一个元素
        li[0],li[i]=li[i],li[0]
        sift(li,0,i-1)


实验代码:


li=[i for i in range(12)]
random.shuffle(li)
print(li)
 
heap_sort(li)
print(li)


可以看出堆排序时间复杂度为O(nlogn)

当然python内部也有堆的内置模块


import heapq
import random
 
li=list(range(12))
random.shuffle(li)
 
print(li)
 
heapq.heapify(li)   # 默认建立小根堆
n=len(li)
for i in range(n):
    print(heapq.heappop(li))   # 每次弹出一个元素
目录
打赏
0
2
3
0
47
分享
相关文章
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
30 1
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
70 4
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
92 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
27天前
|
数据结构之路由表查找算法(深度优先搜索和宽度优先搜索)
在网络通信中,路由表用于指导数据包的传输路径。本文介绍了两种常用的路由表查找算法——深度优先算法(DFS)和宽度优先算法(BFS)。DFS使用栈实现,适合路径问题;BFS使用队列,保证找到最短路径。两者均能有效查找路由信息,但适用场景不同,需根据具体需求选择。文中还提供了这两种算法的核心代码及测试结果,验证了算法的有效性。
89 23
|
27天前
|
数据结构之蜜蜂算法
蜜蜂算法是一种受蜜蜂觅食行为启发的优化算法,通过模拟蜜蜂的群体智能来解决优化问题。本文介绍了蜜蜂算法的基本原理、数据结构设计、核心代码实现及算法优缺点。算法通过迭代更新蜜蜂位置,逐步优化适应度,最终找到问题的最优解。代码实现了单链表结构,用于管理蜜蜂节点,并通过适应度计算、节点移动等操作实现算法的核心功能。蜜蜂算法具有全局寻优能力强、参数设置简单等优点,但也存在对初始化参数敏感、计算复杂度高等缺点。
59 20
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
48 1
数据结构之鲸鱼算法
鲸鱼算法(Whale Optimization Algorithm,WOA)是由伊朗研究员Seyedali Mirjalili于2016年提出的一种基于群体智能的全局优化算法,灵感源自鲸鱼捕食时的群体协作行为。该算法通过模拟鲸鱼的围捕猎物和喷出气泡网的行为,结合全局搜索和局部搜索策略,有效解决了复杂问题的优化需求。其应用广泛,涵盖函数优化、机器学习、图像处理等领域。鲸鱼算法以其简单直观的特点,成为初学者友好型的优化工具,但同时也存在参数敏感、可能陷入局部最优等问题。提供的C++代码示例展示了算法的基本实现和运行过程。
47 0
数据结构之洪水填充算法(DFS)
洪水填充算法是一种基于深度优先搜索(DFS)的图像处理技术,主要用于区域填充和图像分割。通过递归或栈的方式探索图像中的连通区域并进行颜色替换。本文介绍了算法的基本原理、数据结构设计(如链表和栈)、核心代码实现及应用实例,展示了算法在图像编辑等领域的高效性和灵活性。同时,文中也讨论了算法的优缺点,如实现简单但可能存在堆栈溢出的风险等。
39 0
AI助理

阿里云 AI 助理已上线!

快来体验一下吧。