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

本文为 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上关注我，在那里我发布了最新最伟大的人工智能、技术和科学！

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

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

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

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

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

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

手把手：用PyTorch实现图像分类器（第一部分）

手把手：用PyTorch实现图像分类器（第二部分）

等你来译：

对混乱的数据进行聚类

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

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

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