首页 > 编程语言 >Python数据结构与算法05——快速排序

Python数据结构与算法05——快速排序

时间:2024-02-22 21:55:18浏览次数:34  
标签:aimlist 排序 05 Python 元素 low heigh 数据结构 first

快速排序:递归
def quick_sort(aimlist, first, last):
    # 打印当前排序状态
    print(aimlist)

    # 如果子列表只有一个元素或没有元素,直接返回
    if first >= last:
        return

    # 初始化低位、高位和中间值
    low = first
    heigh = last
    mid = aimlist[first]

    # 开始循环,直到低位和高位相遇
    while low < heigh:
        # 从高位向低位搜索,找到第一个小于中间值的元素
        while low < heigh and aimlist[heigh] >= mid:#①
            heigh -= 1
        # 将该元素放到低位,同时高位指针向前移动
        aimlist[low] = aimlist[heigh] #aimlist[heigh]位置的元素已经被保存到aimlist[low]了  aimlist[heigh]相当于空位
        # 打印每一步的变化
        print(aimlist)

        # 从低位向高位搜索,找到第一个大于中间值的元素
        while low < heigh and aimlist[low] <= mid:#②
            low += 1
        # 将该元素放到高位,同时低位指针向后移动
        aimlist[heigh] = aimlist[low]#从低位向高位搜索的过程中 heigh没有变 low在变   所以①②的先后顺序是有说法的
        # 打印每一步的变化
        print(aimlist)

    # 循环结束时,将中间值放到当前低位位置,此时低位和高位相遇
    aimlist[low] = mid

    # 对中间值左边的子列表进行递归排序
    quick_sort(aimlist, first, low - 1)
    # 对中间值右边的子列表进行递归排序
    quick_sort(aimlist, low + 1, last)

# 测试用例
li = [2, 5, 1, 3, 56, 23, 66, 90]
quick_sort(li, 0, len(li) - 1)
print(li)

 

标签:aimlist,排序,05,Python,元素,low,heigh,数据结构,first
From: https://www.cnblogs.com/yyyjw/p/18028310

相关文章

  • 【Azure Function】示例运行 python durable function(model V2)
    问题描述参考官方文档(使用Python创建你的第一个持久函数:https://learn.microsoft.com/zh-cn/azure/azure-functions/durable/quickstart-python-vscode),部署后,却出现“Failedtoloadfunction”错误。在结合以上参考文档后,可以通过如下的步骤创建并运行PythonDurableFu......
  • 数据结构---第一讲 基本概念
    1.1什么是数据结构数据对象在计算机中的组织方式(逻辑结构、物理存储结构)数据对象必定与一系列加在其上的操作相关联,完成这些操作所用的方法就是算法描述数据结构:抽象数据类型(abstractdatatype)数据类型数据对象集数据集合相关联的操作集抽象(即不具体):描述数据类型......
  • 龙哥盟 Python 译文集 2024.2 更新
    每个程序员都应该知道的40个算法Python数学应用Python入门指南Python物联网入门指南Python比特币编程实用指南Python密码学实用指南Python数据结构和算法实用指南Python企业自动化实用指南PythonGPU编程实用指南Python物联网项目LearningScrapy中文版通......
  • python 3.10版本降为3.8版本
    1.安装pyenvpipintsall pyenv-win -ihttp://pypi.douban.com/simple/--trusted-hostpypi.douban.com 2.配置环境变量  3.安装3.8版本pyenvinstall3.8.04.项目中设置:pyenvlocal3.8.0全局设置:pyenvglobal3.8.05.确认版本已经切换:python--version ......
  • python正则表达式之
    1.Match从字符串起始位置开始匹配,两个参数(正则表达式,字符串).*代表匹配前面的字符无限次content='Hello1234567World_ThisisaRegexDemo'#通用匹配result=re.match('^Hello.*Demo$',content)print(result)print(result.group())print(result.span())贪婪......
  • Python处理Word,Excel,PDF
    openpyxl模块处理Excel表安装以下命令意思是:指定D盘下的Python解释器用豆瓣的源安装openpyxl模块D:\PycharmProjects\Study\venv\Scripts\python.exe-mpipinstallopenpyxl-ihttp://pypi.douban.com/simple--trusted-host=pypi.douban.com基本概念openpyxl库有三大模......
  • Python笔记11——函数
    十一、函数函数的作用:提高模块化程度,提高代码重复利用率。11.1定义一个函数一般格式:def函数名(参数列表):函数体以def关键字开头,后接函数标识符名称和圆括号()。所需参数必须都在圆括号中声明。(默认参数值和参数名称是按函数声明中定义的顺序匹配起来的。)函数内容以......
  • python 和shell 变量互相传递
    主要介绍python和shell变量互相传递方法,使用了环境变量、管道等方法。python->shell:1.环境变量importosvar=123或var='123'os.environ['var']=str(var)#environ的键值必须是字符串os.system('echo$var')2.字符串连接importospath='/root/a.txt'var=[1......
  • 第1章 Python入门
    Python介绍·简介Python是一种解释型、面向对象的语言。由吉多·范罗苏姆(GuidovanRossum)于1989年发明,1991年正式公布。官网:www.python.orgPython单词是“大蟒蛇”的意思。但是龟叔不是喜欢蟒蛇才起这个名字,而是正在追剧:英国电视喜剧片《蒙提·派森的飞行马戏团》(MontyPyt......
  • 【数据结构】C语言实现二叉树的相关操作
    树定义树(Tree)是n(n>=0)个结点的有限集若n==0,称为空树若n>0,则它满足如下两个条件:有且仅有一个特定的称为根(Root)的结点其余结点可分为m(m>=0)个互不相交的有限集T1,T2,T3,...Tm,其中每一个集合本身又是一棵树,称为根的子树(SubTree)术语结点:数据元素结点的度:结点......