算法基础:五大排序算法Python实战教程

简介: 排序是每个软件工程师和开发人员都需要掌握的技能。
TB1mkCpz4jaK1RjSZFAXXbdLFXa.jpg

本文为 AI 研习社编译的技术博客,原标题 :

A tour of the top 5 sorting algorithms with Python code

作者 | George Seif

翻译 | 邓普斯•杰弗

校对 | shunshun        整理 | 菠萝妹

原文链接:

https://medium.com/@george.seif94/a-tour-of-the-top-5-sorting-algorithms-with-python-code-43ea9aa02889

算法基础:五大排序算法Python实战教程

TB1I26XABLoK1RjSZFuXXXn0XXa.jpg

排序算法的复杂度

排序是每个软件工程师和开发人员都需要掌握的技能。不仅要通过编程面试,还要对程序本身有一个全面的理解。不同的排序算法很好地展示了算法设计上如何强烈的影响程序的复杂度、运行速度和效率。

让我们看一下前6种排序算法,看看如何在Python中实现它们!

  冒泡排序

冒泡排序通常是在CS入门课程中教的,因为它清楚地演示了排序是如何工作的,同时又简单易懂。冒泡排序步骤遍历列表并比较相邻的元素对。如果元素顺序错误,则交换它们。重复遍历列表未排序部分的元素,直到完成列表排序。因为冒泡排序重复地通过列表的未排序部分,所以它具有最坏的情况复杂度O(n^2)。

TB1J8HEAxnaK1RjSZFtXXbC2VXa.gif TB1ZR_dApYqK1RjSZLeXXbXppXa.png

  选择排序

选择排序也很简单,但常常优于冒泡排序。如果您在这两者之间进行选择,最好默认选择排序。通过选择排序,我们将输入列表/数组分为两部分:已经排序的子列表和剩余要排序的子列表,它们构成了列表的其余部分。我们首先在未排序的子列表中找到最小的元素,并将其放置在排序的子列表的末尾。因此,我们不断地获取最小的未排序元素,并将其按排序顺序放置在排序的子列表中。此过程将重复进行,直到列表完全排序。

TB1wbjEAxjaK1RjSZKzXXXVwXXa.gif TB1fsveAAvoK1RjSZPfXXXPKFXa.png

  插入排序

插入排序比冒泡排序和选择排序既快又简单。有趣的是,有多少人在玩纸牌游戏时会整理自己的牌!在每个循环迭代中,插入排序从数组中删除一个元素。然后,它在另一个排序数组中找到该元素所属的位置,并将其插入其中。它重复这个过程,直到没有输入元素。

TB1pdLlAsfpK1RjSZFOXXa6nFXa.gif TB110TiAxTpK1RjSZFMXXbG_VXa.png

  归并排序

归并排序是分而治之算法的完美例子。它简单地使用了这种算法的两个主要步骤:

(1)连续划分未排序列表,直到有N个子列表,其中每个子列表有1个“未排序”元素,N是原始数组中的元素数。

(2)重复合并,即一次将两个子列表合并在一起,生成新的排序子列表,直到所有元素完全合并到一个排序数组中。

TB1IcveAAvoK1RjSZPfXXXPKFXa.gif TB1stvhAAvoK1RjSZFDXXXY3pXa.jpg

  快速排序

快速排序也是一种分而治之的算法,如归并排序。虽然它有点复杂,但在大多数标准实现中,它的执行速度明显快于归并排序,并且很少达到最坏情况下的复杂度O(n²) 。它有三个主要步骤:

(1)我们首先选择一个元素,称为数组的基准元素(pivot)。

(2)将所有小于基准元素的元素移动到基准元素的左侧;将所有大于基准元素的元素移动到基准元素的右侧。这称为分区操作。

(3)递归地将上述两个步骤分别应用于比上一个基准元素值更小和更大的元素的每个子数组。

TB1GTTXArPpK1RjSZFFXXa5PpXa.gif TB1B2_fApzqK1RjSZSgXXcpAVXa.png

  喜欢吗?

在Twitter上关注我,在那里我发布了最新最伟大的人工智能、技术和科学!

想要继续查看该篇文章相关链接和参考文献?

长按链接点击打开或点击【算法基础:五大排序算法python实战教程】:

https://ai.yanxishe.com/page/TextTranslation/1374

AI研习社每日更新精彩内容,观看更多精彩内容:雷锋网(公众号:雷锋网)雷锋网雷锋网

AI/机器学习年度2018年度进展综述

算法基础:五大排序算法Python实战教程

手把手:用PyTorch实现图像分类器(第一部分)

手把手:用PyTorch实现图像分类器(第二部分)

等你来译:

对混乱的数据进行聚类

初学者怎样使用Keras进行迁移学习 

强化学习:通往基于情感的行为系统 

一文带你读懂 WaveNet:谷歌助手的声音合成器

目录
相关文章
|
14天前
|
算法 数据安全/隐私保护 开发者
马特赛特旋转算法:Python的随机模块背后的力量
马特赛特旋转算法是Python `random`模块的核心,由松本真和西村拓士于1997年提出。它基于线性反馈移位寄存器,具有超长周期和高维均匀性,适用于模拟、密码学等领域。Python中通过设置种子值初始化状态数组,经状态更新和输出提取生成随机数,代码简单高效。
101 63
|
6天前
|
机器学习/深度学习 人工智能 算法
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
宠物识别系统,本系统使用Python作为主要开发语言,基于TensorFlow搭建卷积神经网络算法,并收集了37种常见的猫狗宠物种类数据集【'阿比西尼亚猫(Abyssinian)', '孟加拉猫(Bengal)', '暹罗猫(Birman)', '孟买猫(Bombay)', '英国短毛猫(British Shorthair)', '埃及猫(Egyptian Mau)', '缅因猫(Maine Coon)', '波斯猫(Persian)', '布偶猫(Ragdoll)', '俄罗斯蓝猫(Russian Blue)', '暹罗猫(Siamese)', '斯芬克斯猫(Sphynx)', '美国斗牛犬
59 29
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
|
12天前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
|
21天前
|
BI Python
SciPy 教程 之 Scipy 显著性检验 8
本教程介绍SciPy中显著性检验的应用,包括如何利用scipy.stats模块进行显著性检验,以判断样本与总体假设间的差异是否显著。通过示例代码展示了如何使用describe()函数获取数组的统计描述信息,如观测次数、最小最大值、均值、方差等。
25 1
|
22天前
|
Python
SciPy 教程 之 Scipy 显著性检验 6
显著性检验是统计学中用于判断样本与总体假设间是否存在显著差异的方法。SciPy的scipy.stats模块提供了执行显著性检验的工具,如T检验,用于比较两组数据的均值是否来自同一分布。通过ttest_ind()函数,可以获取两样本的t统计量和p值,进而判断差异是否显著。示例代码展示了如何使用该函数进行T检验并输出结果。
22 1
|
23天前
|
Python
SciPy 教程 之 Scipy 显著性检验 3
本教程介绍Scipy显著性检验,包括其基本概念、原理及应用。显著性检验用于判断样本与总体假设间的差异是否显著,是统计学中的重要工具。Scipy通过`scipy.stats`模块提供了相关功能,支持双边检验等方法。
25 1
|
24天前
|
机器学习/深度学习 人工智能 算法
基于Python深度学习的【垃圾识别系统】实现~TensorFlow+人工智能+算法网络
垃圾识别分类系统。本系统采用Python作为主要编程语言,通过收集了5种常见的垃圾数据集('塑料', '玻璃', '纸张', '纸板', '金属'),然后基于TensorFlow搭建卷积神经网络算法模型,通过对图像数据集进行多轮迭代训练,最后得到一个识别精度较高的模型文件。然后使用Django搭建Web网页端可视化操作界面,实现用户在网页端上传一张垃圾图片识别其名称。
72 0
基于Python深度学习的【垃圾识别系统】实现~TensorFlow+人工智能+算法网络
|
24天前
|
机器学习/深度学习 人工智能 算法
【手写数字识别】Python+深度学习+机器学习+人工智能+TensorFlow+算法模型
手写数字识别系统,使用Python作为主要开发语言,基于深度学习TensorFlow框架,搭建卷积神经网络算法。并通过对数据集进行训练,最后得到一个识别精度较高的模型。并基于Flask框架,开发网页端操作平台,实现用户上传一张图片识别其名称。
68 0
【手写数字识别】Python+深度学习+机器学习+人工智能+TensorFlow+算法模型
|
24天前
|
机器学习/深度学习 人工智能 算法
基于深度学习的【蔬菜识别】系统实现~Python+人工智能+TensorFlow+算法模型
蔬菜识别系统,本系统使用Python作为主要编程语言,通过收集了8种常见的蔬菜图像数据集('土豆', '大白菜', '大葱', '莲藕', '菠菜', '西红柿', '韭菜', '黄瓜'),然后基于TensorFlow搭建卷积神经网络算法模型,通过多轮迭代训练最后得到一个识别精度较高的模型文件。在使用Django开发web网页端操作界面,实现用户上传一张蔬菜图片识别其名称。
68 0
基于深度学习的【蔬菜识别】系统实现~Python+人工智能+TensorFlow+算法模型
|
23天前
|
Python
SciPy 教程 之 Scipy 显著性检验 5
显著性检验用于判断样本与总体假设间的差异是否由随机变异引起,或是假设与真实情况不符所致。SciPy通过scipy.stats模块提供显著性检验功能,P值用于衡量数据接近极端程度,与alpha值对比以决定统计显著性。
23 0