面试必备算法|图解快速排序(Python)

简介: python图解快速排序

快速排序

快速排序的思想

​ 快速排序通过一次排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。具体步骤如下:

  • 从数列中挑出一个元素,称为"基准"(pivot);
  • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区操作;
  • 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

图解快速排序

​ 这里展示放置第一个基准的过程,首先选择第一个数字作为基准。

在这里插入图片描述

​ 接下来我们在26和20的位置分别设置两个指针low和high,并用maddle来存储基准的值(使得列表中基准的位置可以用于元素替换)

在这里插入图片描述

​ 现在我们的目的是让小的数字在前面,大的数字在后面,鉴于我们现在在第一个基准的位置可以用于元素的替换(此处可以看作为空),所以我们从high指针开始进行操作(遍历向前直到找到比基准小的数字)。

在这里插入图片描述

​ 此时我们可以知道high的位置为空,也就是说high的位置可以用作下一个元素的存储位置,因此此时我们转换到操作low指针,通过low指针找到比基准54大的元素。

在这里插入图片描述

​ 和上面同样的原理,我们再继续操作high指针(这里展示剩下交换的过程,如果理解交换过程可以跳过)

在这里插入图片描述

​ 最后如果我们再把指针进行左移操作,就会使得low和high指针重合,此时重合的位置也就是我们最开始找到的基准(54)的位置,至此,我们就可以把基准(54)放到该位置上了。

在这里插入图片描述

​ 此时我们会发现在54前面的数字都比54小,后面的数字都比54大,这也就证明我们已经找好了54的位置,后续我们将54作为切分点,把前面和后面分成两个子列表并递归的执行上诉同样思想的操作就可以了。

快速排序的性质

最优时间复杂度:O(nlog2n)
最坏时间复杂度:O(n2)
稳定性:不稳定

快速排序代码实现

# start/end表示起始指针的位置(不是具体的值)
lst = list(map(int, input().split(',')))


def quick_sort(alist, start, end):
    # 如果前指针的位置大于等于后指针的位置

    if start >= end:
        return

    low = start
    high = end
    middle = alist[low]

    while low < high:
        while low < high and alist[high] >= middle:
            high -= 1
        alist[low] = alist[high]
        while low < high and alist[low] <= middle:
            low += 1
        alist[high] = alist[low]
    alist[low] = middle

    quick_sort(alist, start, low - 1)
    quick_sort(alist, low + 1, end)


quick_sort(lst, 0, len(lst) - 1)
print(lst)
AI 代码解读
目录
打赏
0
0
0
0
16
分享
相关文章
解锁文件共享软件背后基于 Python 的二叉搜索树算法密码
文件共享软件在数字化时代扮演着连接全球用户、促进知识与数据交流的重要角色。二叉搜索树作为一种高效的数据结构,通过有序存储和快速检索文件,极大提升了文件共享平台的性能。它依据文件名或时间戳等关键属性排序,支持高效插入、删除和查找操作,显著优化用户体验。本文还展示了用Python实现的简单二叉搜索树代码,帮助理解其工作原理,并展望了该算法在分布式计算和机器学习领域的未来应用前景。
深度洞察内网监控电脑:基于Python的流量分析算法
在当今数字化环境中,内网监控电脑作为“守城卫士”,通过流量分析算法确保内网安全、稳定运行。基于Python的流量分析算法,利用`scapy`等工具捕获和解析数据包,提取关键信息,区分正常与异常流量。结合机器学习和可视化技术,进一步提升内网监控的精准性和效率,助力企业防范潜在威胁,保障业务顺畅。本文深入探讨了Python在内网监控中的应用,展示了其实战代码及未来发展方向。
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
23 12
内网桌面监控软件深度解析:基于 Python 实现的 K-Means 算法研究
内网桌面监控软件通过实时监测员工操作,保障企业信息安全并提升效率。本文深入探讨K-Means聚类算法在该软件中的应用,解析其原理与实现。K-Means通过迭代更新簇中心,将数据划分为K个簇类,适用于行为分析、异常检测、资源优化及安全威胁识别等场景。文中提供了Python代码示例,展示如何实现K-Means算法,并模拟内网监控数据进行聚类分析。
29 10
|
26天前
|
控制局域网上网软件之 Python 字典树算法解析
控制局域网上网软件在现代网络管理中至关重要,用于控制设备的上网行为和访问权限。本文聚焦于字典树(Trie Tree)算法的应用,详细阐述其原理、优势及实现。通过字典树,软件能高效进行关键词匹配和过滤,提升系统性能。文中还提供了Python代码示例,展示了字典树在网址过滤和关键词屏蔽中的具体应用,为局域网的安全和管理提供有力支持。
52 17
深度解密:员工飞单需要什么证据之Python算法洞察
员工飞单是企业运营中的隐性风险,严重侵蚀公司利润。为应对这一问题,精准搜集证据至关重要。本文探讨如何利用Python编程语言及其数据结构和算法,高效取证。通过创建Transaction类存储交易数据,使用列表管理订单信息,结合排序算法和正则表达式分析交易时间和聊天记录,帮助企业识别潜在的飞单行为。Python的强大功能使得从交易流水和沟通记录中提取关键证据变得更加系统化和高效,为企业维权提供有力支持。
|
29天前
|
U 盘管控情境下 Python 二叉搜索树算法的深度剖析与探究
在信息技术高度发达的今天,数据安全至关重要。U盘作为常用的数据存储与传输工具,其管控尤为关键。本文探讨Python中的二叉搜索树算法在U盘管控中的应用,通过高效管理授权U盘信息,防止数据泄露,保障信息安全。二叉搜索树具有快速插入和查找的优势,适用于大量授权U盘的管理。尽管存在一些局限性,如树结构退化问题,但通过优化和改进,如采用自平衡树,可以有效提升U盘管控系统的性能和安全性。
26 3
【IO面试题 四】、介绍一下Java的序列化与反序列化
Java的序列化与反序列化允许对象通过实现Serializable接口转换成字节序列并存储或传输,之后可以通过ObjectInputStream和ObjectOutputStream的方法将这些字节序列恢复成对象。
面试官:单核 CPU 支持 Java 多线程吗?为什么?被问懵了!
本文介绍了多线程环境下的几个关键概念,包括时间片、超线程、上下文切换及其影响因素,以及线程调度的两种方式——抢占式调度和协同式调度。文章还讨论了减少上下文切换次数以提高多线程程序效率的方法,如无锁并发编程、使用CAS算法等,并提出了合理的线程数量配置策略,以平衡CPU利用率和线程切换开销。
面试官:单核 CPU 支持 Java 多线程吗?为什么?被问懵了!
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
本文详解自旋锁的概念、优缺点、使用场景及Java实现。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?

热门文章

最新文章