python实现快速排序算法

这篇具有很好参考价值的文章主要介绍了python实现快速排序算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 快速排序

快速排序(英语:Quicksort),又称划分交换排序(partition-exchange sort),通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

2. 步骤

  • 从数列中挑出一个元素,称为"基准"(pivot),
  • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

过程如下图所示:

python 快速排序,Python,排序算法,算法,数据结构,python

3. 详细代码

def quick_sort(alist, start, end):
    """快速排序"""
    if start >= end:  # 递归的退出条件
        return
    mid = alist[start]  # 设定起始的基准元素
    low = start  # low为序列左边在开始位置的由左向右移动的游标
    high = end  # high为序列右边末尾位置的由右向左移动的游标
    while low < high:
        # 如果low与high未重合,high(右边)指向的元素大于等于基准元素,则high向左移动
        while low < high and alist[high] >= mid:
            high -= 1
        alist[low] = alist[high]  # 走到此位置时high指向一个比基准元素小的元素,将high指向的元素放到low的位置上,此时high指向的位置空着,接下来移动low找到符合条件的元素放在此处
        # 如果low与high未重合,low指向的元素比基准元素小,则low向右移动
        while low < high and alist[low] < mid:
            low += 1
        alist[high] = alist[low]  # 此时low指向一个比基准元素大的元素,将low指向的元素放到high空着的位置上,此时low指向的位置空着,之后进行下一次循环,将high找到符合条件的元素填到此处

    # 退出循环后,low与high重合,此时所指位置为基准元素的正确位置,左边的元素都比基准元素小,右边的元素都比基准元素大
    alist[low] = mid  # 将基准元素放到该位置,
    # 对基准元素左边的子序列进行快速排序
    quick_sort(alist, start, low - 1)  # start :0  low -1 原基准元素靠左边一位
    # 对基准元素右边的子序列进行快速排序
    quick_sort(alist, low + 1, end)  # low+1 : 原基准元素靠右一位  end: 最后


if __name__ == '__main__':
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    quick_sort(alist, 0, len(alist) - 1)
    print(alist)

4. 性能

  • 空间上:由于是对原数组进行就地排序,因此空间复杂度为O(1)
  • 最优时间复杂度:O(nlogn)
  • 最坏时间复杂度:O(n2):需要排序的数组是降序或者升序排序的
  • 稳定性:不稳定:容易受数据怎么排序的影响,数据改变了,排序的过程会改变,时间也会改变

在最好的情况,每次我们运行一次分区,我们会把一个数列分为两个几近相等的片段。这个意思就是每次递归调用处理一半大小的数列。因此,在到达大小为一的数列前,我们只要作log n次嵌套的调用。这个意思就是调用树的深度是O(log n),则总体的最优时间复杂度为:O(nlogn)

5. 相关链接

快速排序 - python版超详细讲解文章来源地址https://www.toymoban.com/news/detail-740610.html

到了这里,关于python实现快速排序算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构(C语言实现)——常见排序算法的基本思想及实现(快速排序的三种方法和优化及非递归实现快速排序)

    生活中几乎处处都会用到排序,比如:网购时的店铺顺序,学生成绩的排名等,今天我们就来学习数据结构中常见的几种排序算法。 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列

    2023年04月24日
    浏览(60)
  • python实现快速排序算法

    1. 快速排序 快速排序(英语:Quicksort),又称划分交换排序(partition-exchange sort),通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行

    2024年02月06日
    浏览(44)
  • python算法与数据结构---排序和归并排序

    掌握归并排序的基本原理 使用python语言解答归并排序题目 原理及过程 将两个有序的数组合并成一个有序数组称为 从上往下分解:把当前区间一分为二,直至分解为若干个长度为1的子数组 从上往下的合并:两个有序的子区域两两向上合并; 体现了分治思想,稳定排序 复杂

    2024年01月21日
    浏览(70)
  • 数据结构与算法Python版:基数排序

    简介 :基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog®m),其中

    2024年01月24日
    浏览(41)
  • [数据结构 -- 手撕排序算法第六篇] 递归实现快速排序(集霍尔版本,挖坑法,前后指针法为一篇的实现方法,很能打)

    目录 1、常见的排序算法 1.1 交换排序基本思想 2、快速排序的实现方法 2.1 基本思想 3 hoare(霍尔)版本 3.1 实现思路 3.2 思路图解 3.3 为什么实现思路的步骤2、3不能交换 3.4 hoare版本代码实现 3.5 hoare版本代码测试 4、挖坑法 4.1 实现思路 4.2 思路图解 4.3 挖坑法代码实现 4.4 挖坑

    2024年02月16日
    浏览(44)
  • python算法与数据结构(搜索算法和拓扑排序算法)---深度优先搜索

    了解树/图的 深度遍历,宽度遍历 基本原理; 会使用python语言编写 深度遍历,广度遍历 代码; 掌握 拓扑排序算法 搜索引擎 提到搜索两个子,大家都应该会想到搜索引擎,搜索引擎的基本工作步骤; 网页爬取 — 数据预处理 — 排序 — 查询 第一步,网页爬取,非常重要,

    2024年01月20日
    浏览(48)
  • Python篇——数据结构与算法(第四部分:希尔排序及其讨论、计数排序、桶排序、基数排序)

    希尔排序(shell sort)是一种分组插入排序算法 首先取一个整数d1=n/2,将元素分为d1个组,每组相邻两元素之间距离为d1,在各 组内 进行直接插入排序 取第二个整数d2=d1/2,重复上述分组排序过程,知道di=1,即所有元素在同一组内进行直接插入排序。 希尔排序每趟并不使某些

    2024年02月07日
    浏览(39)
  • 数据结构——排序算法之快速排序

        个人主页: 日刷百题 系列专栏 : 〖C/C++小游戏〗 〖Linux〗 〖数据结构〗   〖C语言〗 🌎 欢迎各位 → 点赞 👍+ 收藏 ⭐️+ 留言 📝  ​ ​ 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。 基本思想: 任取待排序元素序列中 的某元素作为基准值,按照

    2024年01月21日
    浏览(54)
  • 【数据结构与算法】十大经典排序算法-快速排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 快速排序(Quick Sort)是一种高效的排序算法,是对冒泡排序的优化。它采用分治法(Divide and Conquer)的思想,将待排序序列

    2024年02月13日
    浏览(62)
  • 【数据结构与算法】:选择排序与快速排序

    🔥 个人主页 : Quitecoder 🔥 专栏 :数据结构与算法 我的博客即将同步至腾讯云开发者社区,邀请大家一同入驻:腾讯云 欢迎来到排序的第二个部分:选择排序与快速排序! 选择排序是一种简单直观的比较排序算法。该算法的基本思想是在每一轮中选出当前未排序部分的最

    2024年03月17日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包