如何用Python对数据排序？常用方法都在这里！
排序的艺术
排序就是将项目按特定顺序排列，具体的顺序则按元素的属性来确定。在整数的情况下，我们可以说小的数在前，大的数在后。按特定顺序排列项目，可以提高元素的搜索效率，因此，排序经常用于计算机科学。
在这篇文章中，我们将介绍一些常见的排序算法。我们将看到 Python 是如何应用于每个阶段的。如果你想了解更多数据分析相关内容，可以阅读以下这些文章：
数据科学家求职必备编程技巧
四个数据科学求职者的常见失误
数据科学家和数据工程师求职的5大区别
2021 Data Engineer求职必备技能
为了比较它们的运行时间，我在排序数组上使用了这个 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。
祝你排序愉快！！你还可以订阅我们的YouTube频道，观看大量数据科学相关公开课：https://www.youtube.com/channel/UCa8NLpvi70mHVsW4J_x9OeQ；在LinkedIn上关注我们，扩展你的人际网络！https://www.linkedin.com/company/dataapplab/
原文作者：Amit Singh Rathore
翻译作者：Lia
美工编辑：过儿
校对审稿：Jiawei Tong
原文链接：https://towardsdatascience.com/sorting-algorithms-with-python-4ec7081d78a1
