如何用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