Python算法:三种高级排序的方法

简介: Python算法:三种高级排序的方法

前言


声明:本文所有动图来源为菜鸟教程


🍀作者简介:被吉师散养、喜欢前端、学过后端、练过CTF、玩过DOS、不喜欢java的不知名学生。


上一期说完了三种简单排序,这一期来说说三种高级排序方法


分别是


  • 快速排序
  • 希尔排序
  • 归并排序


1、快速排序


这个排序方法说起来和冒泡排序有点像,为什么这么说呢,咱先来看图

相对于上一期的简单排序而言,高级排序肯定就不是能一眼看出来了


不说废话了


这玩意分两步


第一步,快速排序首先需要的东西,是一个枢轴值,也就是基准


怎么说?


实际上就是,我选出来一个数作为基准


然后进行分割:比这个基准大的放在该基准的右边,比这个基准小的放在该基准的左边,和基准一样大的,放左右都行


第二步,将基准左/右侧的子序列进行递归排序


实例


def QuickSort(arr):
    if(len(arr)<2): #不用进行排序
        return arr
    else:
        pivot=arr[0]
        less=[i for i in arr[1:] if(i<=pivot)]
        great=[i for i in arr[1:] if(i>pivot)]
        return QuickSort(less)+[pivot]+QuickSort(great)
arr=list(map(int,input().split(' ')))
print("原始数据:",arr)
print("排序后的数据:",QuickSort(arr))

那么这里,我们并没有完全采用上述原理


而是使用重复二分的方式,将数据分为更大与更小两个列表


通过更小+基准+更大


重复拼接,来达到目的


首先来进行读取数据


然后调用函数,如果列表里只有一个元素或者没有元素,就不需要判断


否则,以第一个元素作为基准,分出比他大的和比他小的,分别放在两个列表中,进行拼接


https://www.bilibili.com/video/BV1wY4y1Z7Me?t=43.1


2、希尔排序


希尔排序其实不难,说白了就是插入排序plus,咱们可以很容易地理解


这个排序算法主要利用到了步长

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录"基本有序"时,再对全体记录进行依次直接插入排序。


接下来直接看实例,并讲解


实例


nums = list(map(int,input().split(' ')))
def ShellSort(nums):
    step = len(nums)//2 #初始化增量为数组长度的一半
    while step > 0: #增量必须是大于0的整数
        for i in range(step,len(nums)):#遍历需要进行插入排序的数
            while i >= step and nums[i] < nums[i-step]: #对每组进行插入排序
                nums[i],nums[i-step] = nums[i-step],nums[i]
        step //= 2#增量缩小一半
    print(nums)
ShellSort(nums)

上图原地址 :秒懂算法3-希尔排序_哔哩哔哩_bilibili


按上图来解释,首先我们去步长/跨度


用列表整体长度整除2,上图中一共有九张牌,9//2就等于4,由于我们的循环是从step,也就是第四位开始的,所以我们要判断的条件是八万是否要小于七万。


不小于,不执行


i递增,到了二万,她所对应的是四万,小于,即换位


以此类推到最后一位


结束循环,后缩小步长,再来一遍,直到步长为一,整体排一遍


3、归并排序


基本思想:


  • 分割:递归地把当前序列平均分割成两半
  • 集成:在保持元素顺序的同时将上一步得到的子序列集成到一起(归并)

这个算法可以说是只要理解快速排序,直接拿捏了


直接看算法

def merge(L,R):
    i, j = 0,0
    # 用于存放L与R的合并内容
    res = []
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            res.append(L[i])
            i += 1
        else:
            res.append(R[j])
            j += 1
    res += R[j:] if i == len(L) else L[i:]
    return res
def merge_sort(List):
    length = len(List)
    if length <= 1:
        return List
    else:
        mid = length//2
        left = merge_sort(List[:mid])
        right = merge_sort(List[mid:])
        return merge(left,right)
List = list(map(int,input().split(' ' )))
print(merge_sort(List))

首先进行一个读取数据


调用函数merge_sort


该函数与上述快排相差无几,只不过是从中值开始分的


返回值时调用函数


创建一个新列表,如果左侧大于右侧,将左侧数据通过append放置末尾

res += R[j:] if i == len(L) else L[i:]

该语句负责将剩余的数据拼接到列表中


目录
相关文章
|
8天前
|
监控 算法 安全
深度洞察内网监控电脑:基于Python的流量分析算法
在当今数字化环境中,内网监控电脑作为“守城卫士”,通过流量分析算法确保内网安全、稳定运行。基于Python的流量分析算法,利用`scapy`等工具捕获和解析数据包,提取关键信息,区分正常与异常流量。结合机器学习和可视化技术,进一步提升内网监控的精准性和效率,助力企业防范潜在威胁,保障业务顺畅。本文深入探讨了Python在内网监控中的应用,展示了其实战代码及未来发展方向。
|
24天前
|
机器学习/深度学习 人工智能 算法
基于Python深度学习的眼疾识别系统实现~人工智能+卷积网络算法
眼疾识别系统,本系统使用Python作为主要开发语言,基于TensorFlow搭建卷积神经网络算法,并收集了4种常见的眼疾图像数据集(白内障、糖尿病性视网膜病变、青光眼和正常眼睛) 再使用通过搭建的算法模型对数据集进行训练得到一个识别精度较高的模型,然后保存为为本地h5格式文件。最后使用Django框架搭建了一个Web网页平台可视化操作界面,实现用户上传一张眼疾图片识别其名称。
86 4
基于Python深度学习的眼疾识别系统实现~人工智能+卷积网络算法
|
9天前
|
人工智能 自然语言处理 算法
随机的暴力美学蒙特卡洛方法 | python小知识
蒙特卡洛方法是一种基于随机采样的计算算法,广泛应用于物理学、金融、工程等领域。它通过重复随机采样来解决复杂问题,尤其适用于难以用解析方法求解的情况。该方法起源于二战期间的曼哈顿计划,由斯坦尼斯拉夫·乌拉姆等人提出。核心思想是通过大量随机样本来近似真实结果,如估算π值的经典示例。蒙特卡洛树搜索(MCTS)是其高级应用,常用于游戏AI和决策优化。Python中可通过简单代码实现蒙特卡洛方法,展示其在文本生成等领域的潜力。随着计算能力提升,蒙特卡洛方法的应用范围不断扩大,成为处理不确定性和复杂系统的重要工具。
49 21
|
6天前
|
存储 算法 安全
控制局域网上网软件之 Python 字典树算法解析
控制局域网上网软件在现代网络管理中至关重要,用于控制设备的上网行为和访问权限。本文聚焦于字典树(Trie Tree)算法的应用,详细阐述其原理、优势及实现。通过字典树,软件能高效进行关键词匹配和过滤,提升系统性能。文中还提供了Python代码示例,展示了字典树在网址过滤和关键词屏蔽中的具体应用,为局域网的安全和管理提供有力支持。
34 17
|
15天前
|
存储 监控 算法
员工电脑监控屏幕场景下 Python 哈希表算法的探索
在数字化办公时代,员工电脑监控屏幕是保障信息安全和提升效率的重要手段。本文探讨哈希表算法在该场景中的应用,通过Python代码例程展示如何使用哈希表存储和查询员工操作记录,并结合数据库实现数据持久化,助力企业打造高效、安全的办公环境。哈希表在快速检索员工信息、优化系统性能方面发挥关键作用,为企业管理提供有力支持。
41 20
|
7天前
|
数据挖掘 数据处理 开发者
Python3 自定义排序详解:方法与示例
Python的排序功能强大且灵活,主要通过`sorted()`函数和列表的`sort()`方法实现。两者均支持`key`参数自定义排序规则。本文详细介绍了基础排序、按字符串长度或元组元素排序、降序排序、多条件排序及使用`lambda`表达式和`functools.cmp_to_key`进行复杂排序。通过示例展示了如何对简单数据类型、字典、类对象及复杂数据结构(如列车信息)进行排序。掌握这些技巧可以显著提升数据处理能力,为编程提供更强大的支持。
23 10
|
10天前
|
存储 人工智能 算法
深度解密:员工飞单需要什么证据之Python算法洞察
员工飞单是企业运营中的隐性风险,严重侵蚀公司利润。为应对这一问题,精准搜集证据至关重要。本文探讨如何利用Python编程语言及其数据结构和算法,高效取证。通过创建Transaction类存储交易数据,使用列表管理订单信息,结合排序算法和正则表达式分析交易时间和聊天记录,帮助企业识别潜在的飞单行为。Python的强大功能使得从交易流水和沟通记录中提取关键证据变得更加系统化和高效,为企业维权提供有力支持。
|
9天前
|
存储 算法 安全
U 盘管控情境下 Python 二叉搜索树算法的深度剖析与探究
在信息技术高度发达的今天,数据安全至关重要。U盘作为常用的数据存储与传输工具,其管控尤为关键。本文探讨Python中的二叉搜索树算法在U盘管控中的应用,通过高效管理授权U盘信息,防止数据泄露,保障信息安全。二叉搜索树具有快速插入和查找的优势,适用于大量授权U盘的管理。尽管存在一些局限性,如树结构退化问题,但通过优化和改进,如采用自平衡树,可以有效提升U盘管控系统的性能和安全性。
18 3
|
24天前
|
存储 算法 Serverless
剖析文件共享工具背后的Python哈希表算法奥秘
在数字化时代,文件共享工具不可或缺。哈希表算法通过将文件名或哈希值映射到存储位置,实现快速检索与高效管理。Python中的哈希表可用于创建简易文件索引,支持快速插入和查找文件路径。哈希表不仅提升了文件定位速度,还优化了存储管理和多节点数据一致性,确保文件共享工具高效运行,满足多用户并发需求,推动文件共享领域向更高效、便捷的方向发展。
|
14天前
|
算法 数据安全/隐私保护 计算机视觉
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。

热门文章

最新文章