Python数据结构与算法(16)---快速排序

简介: Python数据结构与算法(16)---快速排序

快速排序


快速排序,又称Quick Sort,其本身对冒牌排序进行了相应的改进。


其基本原理:通过一轮排序将要排序的数据分割成独立的2个部分,其中一部分的所有数据都比另外一部分的所有数据小,然后再按照此放法对2部分数据分别进行快速排序,整个排序过程可以递归进行,直到整个数据变成有序序列。


具体算法实施过程如下:


1.首先,选取列表的最后一个元素最为基准数N,小于N的放前边,大于等于N的放后面。

2.然后,接着再取前边的最后一个数为基准,同上放置。

3.一直到每部分的下标相等,即完成快速排序。


其平均时间复杂度为O(n*log2n)


图解快速排序

还是以前文的列表数据为例。假设,我们的列表数据为[8,0,4,3,2,1]。那么,我们排序的过程如下图所示:


读者是否发现,相对于前面的排序,快速排序的过程要简单的多。而且对于通过一个列表,过程也要少的多?这也是其之所以叫快速排序的原因之所在。


实战:快速排序

介绍了前面的原理,这里我们直接上快速排序的代码。详细的代码步骤解析都在代码之中,博主就不在赘述,示例如下:

def move_num(my_list, low, high):
    N = my_list[high]  # 确定基数N
    move = low - 1  # 从左边减1开始
    for i in range(low, high):
        if my_list[i] <= N:
            move += 1  # 记录最近一个交换值的下标
            my_list[move], my_list[i] = my_list[i], my_list[move]  # 大的放后面,小的放move处
    my_list[move + 1], my_list[high] = my_list[high], my_list[move + 1]  # 最后一次,把N值放到move+1处
    return move + 1
def quick_sort(my_list, low, high):
    n = len(my_list)
    if n == 1:
        return my_list
    if low < high:  # low==high停止排序
        N = move_num(my_list, low, high)  # 一次比较排序
        quick_sort(my_list, low, N - 1)  # 递归前一部分排序
        quick_sort(my_list, N + 1, high)  # 递归后一部分排序
    return my_list
if __name__ == "__main__":
    my_list = [8, 0, 4, 3, 2, 1]
    print("排序前的数组:", my_list)
    print("排序后的数组:", quick_sort(my_list, 0, len(my_list) - 1))


运行之后,效果如下:


使用场景

有名字我们就可以直到,快速排序在排序的速度上更快,但需要注意的是,因为其递归需要额外的内存空间存储临时值,当需要排序的元素变得很多的时候。


则需要考虑到内存空间的使用要求,比如有十几万元素左快速排序,则会产生非常大的存储空间开销。所以,我们选择用那种算法应该因数据而异。

相关文章
|
20天前
|
搜索推荐 C语言
【排序算法】快速排序升级版--三路快排详解 + 实现(c语言)
本文介绍了快速排序的升级版——三路快排。传统快速排序在处理大量相同元素时效率较低,而三路快排通过将数组分为三部分(小于、等于、大于基准值)来优化这一问题。文章详细讲解了三路快排的实现步骤,并提供了完整的代码示例。
47 4
|
5天前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
|
16天前
|
机器学习/深度学习 人工智能 算法
基于Python深度学习的【垃圾识别系统】实现~TensorFlow+人工智能+算法网络
垃圾识别分类系统。本系统采用Python作为主要编程语言,通过收集了5种常见的垃圾数据集('塑料', '玻璃', '纸张', '纸板', '金属'),然后基于TensorFlow搭建卷积神经网络算法模型,通过对图像数据集进行多轮迭代训练,最后得到一个识别精度较高的模型文件。然后使用Django搭建Web网页端可视化操作界面,实现用户在网页端上传一张垃圾图片识别其名称。
63 0
基于Python深度学习的【垃圾识别系统】实现~TensorFlow+人工智能+算法网络
|
16天前
|
机器学习/深度学习 人工智能 算法
【手写数字识别】Python+深度学习+机器学习+人工智能+TensorFlow+算法模型
手写数字识别系统,使用Python作为主要开发语言,基于深度学习TensorFlow框架,搭建卷积神经网络算法。并通过对数据集进行训练,最后得到一个识别精度较高的模型。并基于Flask框架,开发网页端操作平台,实现用户上传一张图片识别其名称。
53 0
【手写数字识别】Python+深度学习+机器学习+人工智能+TensorFlow+算法模型
|
16天前
|
机器学习/深度学习 人工智能 算法
基于深度学习的【蔬菜识别】系统实现~Python+人工智能+TensorFlow+算法模型
蔬菜识别系统,本系统使用Python作为主要编程语言,通过收集了8种常见的蔬菜图像数据集('土豆', '大白菜', '大葱', '莲藕', '菠菜', '西红柿', '韭菜', '黄瓜'),然后基于TensorFlow搭建卷积神经网络算法模型,通过多轮迭代训练最后得到一个识别精度较高的模型文件。在使用Django开发web网页端操作界面,实现用户上传一张蔬菜图片识别其名称。
62 0
基于深度学习的【蔬菜识别】系统实现~Python+人工智能+TensorFlow+算法模型
|
21天前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
37 2
|
21天前
|
搜索推荐 Python
快速排序的 Python 实践:从原理到优化,打造你的排序利器!
本文介绍了 Python 中的快速排序算法,从基本原理、实现代码到优化方法进行了详细探讨。快速排序采用分治策略,通过选择基准元素将数组分为两部分,递归排序。文章还对比了快速排序与冒泡排序的性能,展示了优化前后快速排序的差异。通过这些分析,帮助读者理解快速排序的优势及优化的重要性,从而在实际应用中选择合适的排序算法和优化策略,提升程序性能。
32 1
|
1月前
|
算法 测试技术 开发者
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗;代码审查通过检查源代码发现潜在问题,提高代码质量和团队协作效率。本文介绍了一些实用的技巧和工具,帮助开发者提升开发效率。
37 3
|
1月前
|
机器学习/深度学习 人工智能 算法
【车辆车型识别】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+算法模型
车辆车型识别,使用Python作为主要编程语言,通过收集多种车辆车型图像数据集,然后基于TensorFlow搭建卷积网络算法模型,并对数据集进行训练,最后得到一个识别精度较高的模型文件。再基于Django搭建web网页端操作界面,实现用户上传一张车辆图片识别其类型。
74 0
【车辆车型识别】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+算法模型
|
2月前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)