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

2019 年 1 月 4 日 AI研习社

本文为 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实战教程

排序算法的复杂度

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

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


  冒泡排序

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



  选择排序

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



  插入排序

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



  归并排序

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

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

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



  快速排序

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

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

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

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



  喜欢吗?

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



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

长按链接点击打开或点击底部【阅读原文】:

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


AI研习社每日更新精彩内容,观看更多精彩内容:

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

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

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

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


等你来译:

对混乱的数据进行聚类

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

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

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

【AI求职百题斩 - 每日一题】

每日挑战改版啦,来看看今天的题目吧!

想知道正确答案?

回公众号聊天界面并发送“0104挑战”即可答题获取!

点击 阅读原文 查看本文更多内容

登录查看更多
2

相关内容

排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序。若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
【实用书】学习用Python编写代码进行数据分析,103页pdf
专知会员服务
190+阅读 · 2020年6月29日
【2020新书】使用高级C# 提升你的编程技能,412页pdf
专知会员服务
56+阅读 · 2020年6月26日
【哈佛《CS50 Python人工智能入门》课程 (2020)】
专知会员服务
109+阅读 · 2020年4月12日
【干货书】机器学习Python实战教程,366页pdf
专知会员服务
332+阅读 · 2020年3月17日
【新书】Pro 机器学习算法Python实现,379页pdf
专知会员服务
197+阅读 · 2020年2月11日
【书籍】深度学习框架:PyTorch入门与实践(附代码)
专知会员服务
160+阅读 · 2019年10月28日
《机器学习实战》代码(基于Python3)
专知
32+阅读 · 2019年10月14日
Github标星4w+,如何用Python实现所有算法
七月在线实验室
5+阅读 · 2019年5月21日
最全Python算法实现资源汇总!
AI100
3+阅读 · 2019年5月13日
Github标星2w+,热榜第一,如何用Python实现所有算法
大数据文摘
7+阅读 · 2019年4月28日
GitHub超2.7万星,最全Python入门算法来了
新智元
5+阅读 · 2019年4月28日
GitHub标星2.6万!Python算法新手入门大全
量子位
3+阅读 · 2019年4月27日
免费|机器学习算法Python实现
全球人工智能
5+阅读 · 2018年1月2日
如何入门Python与机器学习 | 赠书
CSDN大数据
9+阅读 · 2017年11月12日
Python NLP 入门教程
大数据技术
19+阅读 · 2017年10月24日
A Survey on Deep Learning for Named Entity Recognition
Arxiv
25+阅读 · 2020年3月13日
Arxiv
14+阅读 · 2020年2月6日
Arxiv
34+阅读 · 2019年11月7日
Arxiv
6+阅读 · 2018年3月28日
VIP会员
相关VIP内容
【实用书】学习用Python编写代码进行数据分析,103页pdf
专知会员服务
190+阅读 · 2020年6月29日
【2020新书】使用高级C# 提升你的编程技能,412页pdf
专知会员服务
56+阅读 · 2020年6月26日
【哈佛《CS50 Python人工智能入门》课程 (2020)】
专知会员服务
109+阅读 · 2020年4月12日
【干货书】机器学习Python实战教程,366页pdf
专知会员服务
332+阅读 · 2020年3月17日
【新书】Pro 机器学习算法Python实现,379页pdf
专知会员服务
197+阅读 · 2020年2月11日
【书籍】深度学习框架:PyTorch入门与实践(附代码)
专知会员服务
160+阅读 · 2019年10月28日
相关资讯
《机器学习实战》代码(基于Python3)
专知
32+阅读 · 2019年10月14日
Github标星4w+,如何用Python实现所有算法
七月在线实验室
5+阅读 · 2019年5月21日
最全Python算法实现资源汇总!
AI100
3+阅读 · 2019年5月13日
Github标星2w+,热榜第一,如何用Python实现所有算法
大数据文摘
7+阅读 · 2019年4月28日
GitHub超2.7万星,最全Python入门算法来了
新智元
5+阅读 · 2019年4月28日
GitHub标星2.6万!Python算法新手入门大全
量子位
3+阅读 · 2019年4月27日
免费|机器学习算法Python实现
全球人工智能
5+阅读 · 2018年1月2日
如何入门Python与机器学习 | 赠书
CSDN大数据
9+阅读 · 2017年11月12日
Python NLP 入门教程
大数据技术
19+阅读 · 2017年10月24日
Top
微信扫码咨询专知VIP会员