今日份知识你摄入了么？
图片来源：Unsplash摄影：Max Panama
排序的艺术
排序就是将项目按特定顺序排列，具体的顺序则按元素的属性来确定。在整数的情况下，我们可以说小的数在前，大的数在后。按特定顺序排列项目，可以提高元素的搜索效率，因此，排序经常用于计算机科学。
在这篇文章中，我们将介绍一些常见的排序算法。我们将看到 Python 是如何应用于每个阶段的。为了比较它们的运行时间，我在排序数组上使用了这个 Leetcode 问题。问题的要求如下。
要求：

我用所有常见的排序算法去解决了这个问题。下面是解决结果所用的时间和内存消耗。
图片由作者提供

注意：TLE 指超出时间限制。

冒泡排序（Bubble Sort）
这是最简单的排序算法。迭代整个列表，并在每次迭代中，成对比较元素，并不断交换它们，来把较大的元素移到列表的末尾。
  • 非递归过程
  • 稳定
  • 原地算法（in-place algorithm）
  • 复杂度：O(n²)
选择排序（Selection Sort）
在这个算法中，我们会创建列表的两个部分，一个是已排序的，另一个是未排序的。我们不断地从列表的未排序段中移除最小的元素，并将其附加到已排序的段中。我们不交换中间元素。因此，该算法能以最少的交换次数对数组进行排序。
  • 非递归过程
  • 不稳定
  • 原地算法（in-place algorithm）
  • 复杂度：O(n²)
插入排序（Insertion Sort）
和选择排序类似，在这个算法中，我们将列表分成已排序和未排序两部分。然后对未排序的段进行迭代，并将该段中的元素插入到已排序列表中的正确位置。
  • 非递归过程
  • 稳定
  • 原地算法（in-place algorithm）
  • 复杂度：O(n²)
希尔排序（Shell Sort）
Shell 排序是对插入排序的优化方法，它是通过在固定的时间间隔内，对所有元素重复执行插入排序来实现的。上一次迭代的间隔是1。在这里，它变成了常规的插入排序，并保证数组将被排序。需要注意的是，当我们这样做的时候，数组几乎已经排好序了，因此迭代速度很快。
  • 非递归过程
  • 稳定
  • 原地算法（in-place algorithm）
  • 复杂度：O(n²) ，也取决于区间选择
堆排序（Heap Sort）
像前两个算法一样，我们创建列表的两个部分，一个已排序，一个未排序。在这里，我们使用堆数据结构，来有效地从列表的未排序段中获取最大元素。应用Heapify方法，用递归来获得顶部的最大元素。
  • 非递归过程
  • 不稳定
  • 原地算法（in-place algorithm）
  • 复杂度：O(nlogn)
归并排序（Merge Sort）
这是一种分治算法。在这个算法中，我们将一个列表分成两半，然后继续将列表一分为二，直到它只有一个元素。然后我们归并所有已排序的列表。我们一直这样做，直到得到一个包含所有元素的已排序列表。
  • 递归过程
  • 稳定
  • 需要额外的空间
  • 复杂度：O(nlogn)
快速排序（Quick Sort）
在这个算法中，我们围绕一个主元素划分列表，围绕着这个主元素对值进行排序。在我的解决方案中，我使用了列表中的最后一个元素作为主元值。当pivot值将列表分成几乎相等的两半时，可以获得最佳性能。
  • 递归过程
  • 原地算法（in-place algorithm）
  • 不稳定
  • 复杂度：O(nlogn)
计数排序（Counting Sort）
该算法并不做元素之间的比较。而是用整数的数学特性进行排序。我们计算一个数字出现的次数，并将计数存储在索引所代表的键值的数组中。
  • 非递归过程
  • 原地算法（in-place algorithm）但需要额外空间
  • 稳定的
  • 复杂度：O(n)
尝试了所有这些不同的算法后，出于好奇，我又提交了默认的排序方法。运行时间为 152 (ms)，速度非常快。
Python 的默认排序使用了 Tim Sort，该排序方法结合了合并排序和插入排序。

通过我们的小实验，我们了解了不同的算法、它们的运行时间和内存的消耗。现在，我们知道了算法的内存、CPU 时间和稳定性等参数。我们需要根据具体的问题具体评估这些参数，来找到最合适的算法。
我们还可以将这些基本排序算法组合成更强大的算法，如Tim Sort。

祝你排序愉快！！
原文作者：Amit Singh Rathore
翻译作者：Lia
美工编辑：过儿
校对审稿：Jiawei Tong
原文链接：https://towardsdatascience.com/sorting-algorithms-with-python-4ec7081d78a1
本周公开课预告
往期精彩回顾

2021年数据科学家，最需要这7个技能！
商业分析中，针对不同模型要准备哪些内容?
创业公司是如何利用定价订阅服务赚钱的？
Machine Learning Model：建立机器学习模型的四个概念
新兴数据岗位：Analytics Engineer分析工程师是什么？



点「在看」的人都变好看了哦
点击“阅读原文”查看数据应用学院核心课程
继续阅读
阅读原文