Python数据结构【四】排序(二)难度:困难

2024-04-20 07:20

本文主要是介绍Python数据结构【四】排序(二)难度:困难,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 前言
    • 一、书接上回
    • 二、快速排序(Quick Sort)
      • 2.1 快速排序思想
      • 2.2 快速排序代码实现
      • 2.3 快速排序复杂度分析
    • 三、堆排序(Heap Sort)
      • 3.1 堆排序思想
      • 3.2 堆排序代码实现
      • 3.3 堆排序复杂度分析
  • 结语

前言

可私聊进一千多人Python全栈交流群(手把手教学,问题解答)

可私聊获取源代码和动画PPT进群可领取Python全栈教程视频 + 多得数不过来的计算机书籍:基础、Web、爬虫、数据分析、可视化、机器学习、深度学习、人工智能、算法、面试题等。

  • 🚀🚀加入我一起学习进步,一个人可以走的很快,一群人才能走的更远!

  • 一、书接上回

    上次学习了冒泡排序,插入排序,选择排序,今天需要学习的是快速排序,堆排序。

    相比于前面三个,这两个可以说是有一点点难度的了。

    二、快速排序(Quick Sort)

    快速排序,突出的就是一个快字,比前面三个时间复杂度少一点,因为快排使用了类似于二分+递归的方法。

    2.1 快速排序思想

    1. 取出一个元素(通常是第一个)

    2. 然后将该元素放入一个位置使得左边的元素都小于该元素,右边的元素都大于该元素

    3. 然后对该元素左右两边进行切割

    4. 然后递归

    5. 结束

    整了个动画来讲解第二步

    在这里插入图片描述

    2.2 快速排序代码实现

    由于第二步功能较多,所以我们可以使用一个函数封装起来。

    找中位数函数(也就是动图的实现)

    def find_mid(left, right, li):"""left: 左指针right: 右指针li: 列表之所以不是0和n-1是为了递归的时候也能使用"""swep = False                        # 代表左边有无空temp = li[left]while left < right:                 # 循环终止条件if swep == False:               # 如果左边有空位if li[right] < temp:        # 判断是否可以交换li[right],li[left] = li[left],li[right]     # 交换swep = True             # 左边无空位else:right -= 1                # 不交换,左边有空位,右指针移动else:                           # 左边无空位if li[left] > temp:         # 判断li[left],li[right] = li[right],li[left]     # 交换swep = False            # 左边有空位else:left += 1               # 无法腾出空位,左指针移动li[left] = temp                     # 找到位置,将元素插入return left                         # 此时左右重合,退出函数
    

    快排递归函数:

    def quick_sort(left, right, li):if left < right:                    # 递归终止条件mid = find_mid(left, right, li)quick_sort(left, mid-1, li)     # 排序左边的quick_sort(mid+1, right, li)    # 排序右边的
    

    测试用例:[5, 4, 2, 8, 3, 9]

    运行结果:

    在这里插入图片描述

    测试用例:[1, 1, 4, 5, 1, 4]

    运行结果:

    在这里插入图片描述

    2.3 快速排序复杂度分析

    时间复杂度:nlogn

    空间复杂度:nlogn (实际上这个是递归的空间复杂度,因为原地排序是不需要空间复杂度的)

    当然这些都是算平均的复杂度,时间上算法的时间空间复杂度都是由最优和最劣的情况的,这里就不一一赘述了

    三、堆排序(Heap Sort)

    堆排序,就是使用堆来进行排序的一种排序方法。

    • 堆——堆是一种特殊的完全二叉树
      • 大根堆——一种完全二叉树,满足任意节点都比孩子节点大
      • 小根堆——一种完全二叉树,满足其任意节点都比孩子节点小

    在这里插入图片描述

    当然树这个数据结构是没有箭头的,我只是想起来已经做出来了就懒得重做了。

    3.1 堆排序思想

    通过堆的向下调整来排序。(左右子树都满足大/小根堆,但是堆本身不满足)

    1. 建立一个堆(需要从小到大排就建立小根堆,需要从大到小就建立大根堆)
    2. 得到堆顶元素(此时堆是大根/小根堆,是有序的)
    3. 将堆顶元素去掉,替换为堆最后的元素,进行堆的向下调整(此时堆顶元素为最大/最小元素)
    4. 重复步骤2,3,直到堆为空(使用递归,判断根节点是否为空)

    由于堆的向下调整比较难,所以只做一个向下调整的演示动画。

    在这里插入图片描述

    如果将上述堆通过列表展示,则列表为:[2, 5, 4, 3, 8, 7]

    从根节点向下,然后每个子树都完全展示出来

    3.2 堆排序代码实现

    向下调整函数:

    def change_down(li, low, high):"""li: 无序数组low: 根节点元素high: 最后一个元素位置"""temp = li[low]                               # 存起来栈顶元素i = low                                      # i指向根节点j = 2 *i + 1                                 # j指向左孩子节点while j <= high:                             # 只要j不为空if j + 1 <= high and li[j+1] > li[j]:    # 如果右孩子节点大j = j + 1                            # j指向右孩子节点  if li[j] > temp:                         # 如果左孩子节点大li[i] = li[j]                        # 将大的放在栈顶i = j                                # 下一层j = 2* i + 1                         # 重新设定左孩子结点else:                                    # 如果栈顶元素是最大的li[i] = temp                         # 将栈顶元素存入栈顶或者某个子树的根节点break                                # 结束循环else:li[i] = temp                             # 将原栈顶元素放在叶子结点
    

    堆排序代码:

    def heap_sort(li):n = len(li)for i in range((n-2)//2, -1, -1):            # 从叶子结点的子树向每个子树的根节点遍历change_down(li, i, n-1)                  # 建堆for i in range(n-1, -1, -1):                 # 挨个取出栈顶元素li[0], li[i] = li[i], li[0]              # 将栈顶元素和最后一个元素进行交换change_down(li, 0, i-1)                  # 向下调整

    测试用例:[2, 4, 8, 7, 3, 5]

    运行截图:

    在这里插入图片描述

    测试用例:[5, 4, 2, 8, 3, 9, 5]

    运行截图:

    在这里插入图片描述

    3.3 堆排序复杂度分析

    时间复杂度:O(nlogn)

    空间复杂度:O(1) 如果使用一个辅助列表,那就是O(n)

    结语

    俗话说得好,光说不练——假把式。一定要多练,多思考。

    想不通就先不想,先去练,多练几次就明白了。

    正如古话说得好,书读百遍其义自见!

这篇关于Python数据结构【四】排序(二)难度:困难的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/919622

相关文章

python: 多模块(.py)中全局变量的导入

文章目录 global关键字可变类型和不可变类型数据的内存地址单模块(单个py文件)的全局变量示例总结 多模块(多个py文件)的全局变量from x import x导入全局变量示例 import x导入全局变量示例 总结 global关键字 global 的作用范围是模块(.py)级别: 当你在一个模块(文件)中使用 global 声明变量时,这个变量只在该模块的全局命名空

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如,在当前目录下创建一个名为 myenv 的虚拟环境: python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行: source myenv/bin/activate 3.与notebook连接 在虚拟环境中,使用 pip 安装 Jupyter 和 ipykernel: pip instal

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程(Gaussian Process,简称GP)是一种概率模型,用于描述一组随机变量的联合概率分布,其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数(或核函数) 1.3 核函数1.4 高斯过程回归(Gauss

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

nudepy,一个有趣的 Python 库!

更多资料获取 📚 个人网站:ipengtao.com 大家好,今天为大家分享一个有趣的 Python 库 - nudepy。 Github地址:https://github.com/hhatto/nude.py 在图像处理和计算机视觉应用中,检测图像中的不适当内容(例如裸露图像)是一个重要的任务。nudepy 是一个基于 Python 的库,专门用于检测图像中的不适当内容。该

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip