发帖
雷达卡
你日历中的下一个任务，你最喜欢的运动队在联赛中的排名，你手机里的通讯录，所有这些都有一个顺序。当我们处理信息时，顺序很重要。我们使用秩序来理解我们的生活并优化我们的决策。想象一下在字典中以混合的字母顺序查找一个单词，或者试图在无序的定价列表中找到最便宜的产品。我们下令做出更合理的决定（这实际上是一种错觉），这让我们对结果更有信心。
但是有一个问题：世界是混乱的，本质上是无序的（至少从我们人类的感知来看）。今天的数据是乱七八糟的，这是一个非常糟糕的组合。我们如何才能以对我们有意义的方式来整理这个庞大的信息漩涡？这就是计算机排序算法发挥关键作用的地方。
排序算法的宇宙
简单来说， 算法是解决问题的逐步方法。算法基于接受输入并执行一系列指定操作以达到结果。它们被广泛用于计算机编程、数学甚至我们的日常生活（例如，烹饪食谱是一种算法）等领域。
算法早在计算机发明之前就已经存在，但是自从现代技术的爆炸式增长以来，计算机算法已经在各处扩展和复制。现在，从庞大的计算机算法领域来看，我认为排序算法值得一章。
排序算法 是计算机科学的基础。它们 将无序的数据转换为按某些标准排序的数据，例如按字母顺序、从最高到最低的值或最短到最长的距离。
它们基本上将项目列表作为输入，对这些列表执行特定操作，并以有序的方式交付这些项目作为输出。排序算法的许多应用包括在零售网站上按价格组织商品以及确定搜索引擎结果页面上的网站顺序
那里有许多不同的排序算法，但它们的共同点是在可视化时更好地理解它们。在下面的例子中，我们使用 5 种不同的算法对一个无序列表进行排序： 选择排序、 插入排序、 冒泡排序、 合并排序 和 快速排序。让我们来看看。
选择排序
选择排序算法基于在未排序列表中找到最小或最大元素，然后以排序方式将其放置在正确位置的想法。在升序排序的情况下，最小的元素将在最前面，在降序排序的情况下，最大的元素将在开始。
因此，当按升序排序时，选择排序通过重复从列表的未排序部分中找到最小元素并将其放在开头来工作。在每次迭代中，从列表的未排序部分中挑选最小元素，并将其移动到列表的已排序部分。为了做到这一点，算法在通过时寻找最小值（在升序的情况下），并在完成通过后将其放置在适当的位置。
选择排序算法（升序）
看上面的例子。需要升序排序的列表分为两部分，左端排序部分和右端未排序部分。最初，已排序的部分是空的，未排序的部分是整个列表。从未排序的列表中选择最小的元素（在本例中为 2）（用洋红色标记）并与最左边的元素交换，该元素成为排序数组的一部分（现在为橙色）。这个过程继续将未排序的元素从未排序的列表中一个一个地移动到已排序的列表中，直到没有更多的元素被留下。
选择排序非常直观，但由于它需要扫描整个列表以找到下一个小值，因此在处理大量数据时可能会很慢。
插入排序
你有没有在游戏中整理过纸牌？如果答案是肯定的，那么这就是插入排序。
与选择排序一样，插入排序将元素划分为已排序和未排序的列表。在该算法中，按顺序搜索元素并将未排序的项目移动并插入到排序列表中，直到覆盖所有未排序的值。
插入排序算法（升序）
在我们的示例中，从左侧开始，算法将第一个元素 (29) 标记为已排序。然后它选择位于未排序列表中的第二个元素（10），并将其与放置在排序列表中的前一个元素进行比较。由于 10 小于 29，它将较高的元素向右移动并将较小的元素插入到第一个位置。现在元素 10 和 29 表示排序列表。该算法通过从右侧未排序列表中提取元素并将它们与左侧已排序列表中的元素进行比较来顺序执行此练习，以确定将它们插入的位置。
插入排序是自适应的，这意味着如果提供部分排序的数组作为输入，它会减少其总步数，从而提高效率。与选择排序一样，插入排序不适用于与其他排序算法相比松散的大数据量。
冒泡排序
冒泡排序基于重复比较相邻元素对，如果它们以错误的顺序存在则交换它们的位置的想法。
如果必须按升序对元素列表进行排序，则冒泡排序将首先将列表的第一个元素与第二个元素进行比较。如果第一个元素大于第二个元素，它将 交换 两个元素并继续比较第二个和第三个元素，依此类推。
1jCuqA5rX9ZkS0ecFgBhstA
冒泡排序算法（升序）
在我们的示例中，算法首先将第一个元素 (29) 与第二个元素 (10) 进行比较。由于 29 大于 10，因此它交换它们并将 29 作为列表中的第二个元素。然后，它对第二个元素 (29) 和第三个元素 (14) 执行相同的操作，并在所有列表元素中重复此操作。结果，列表中的最高元素 (41) 将在第一遍中放置在列表的末尾（右侧）。该算法将多次遍历所有元素，直到它们全部排序，将每个元素“冒泡”到它所属的位置。
冒泡排序通常被认为是一种低效的排序工具，因为它必须在元素的最终位置已知之前交换项目。但是，如果在传递期间没有交换，那么我们知道必须对列表进行排序。如果发现列表已排序，则可以修改冒泡排序以提前停止，这为其提供了识别已排序列表的能力。
合并排序
合并排序是一种非常有效的算法，它将元素列表分成两半，然后以排序方式组合它们。
该算法首先将一个列表反复分解为几个子列表，直到每个子列表包含一个元素并且不能再拆分（创建一个元素的分区）。每个子列表的第一个元素在它们之间进行比较，如果按升序排序，则两者中较小的元素将成为新合并排序列表的新元素。重复此过程，直到所有子列表都为空，并且一个新合并的列表覆盖所有子列表的所有元素，从而形成一个排序列表。
这里的秘诀是一个包含单个元素的列表已经排序，所以一旦我们将原始列表分解为只有一个元素的子列表，我们就成功地将问题分解为基本问题。这种方法被称为 “分治法”，它基于将单个大问题分解为较小的子问题的思想，解决较小的子问题并将它们的解决方案组合起来以找到原始大问题的解决方案.
1dpho84T29TjBbmzoDicILA
合并排序算法（升序）
在我们的示例中，该算法首先将元素列表拆分为 1 的分区。然后，它合并第一个 (29) 和第二个 (10) 元素，对它们进行排序（在本例中按升序排列），然后将它们放回名单。然后，它合并第一个（现在是 10）、第二个（现在是 29）和第三 (14) 个元素，对它们进行排序，然后将它们放回列表中。它对所有子列表执行此过程，合并子结果，直到达到一个唯一的排序列表。
由于 Merge Sort 将输入分成块，因此每个块都可以同时并行排序，从而产生极快的结果。
快速排序
QuickSort 是最有效的排序算法之一，它基于将数据集拆分为子组，然后递归地将其分成更小的组以优化排序过程。该算法的工作原理是在数据集中找到一个 “枢轴元素” 并将其用作排序的基础。
快速排序还使用 “分而治之”的 方法来划分和组织枢轴周围的元素，这样：枢轴左侧包含小于枢轴元素的所有元素，右侧包含所有大于枢轴元素的元素比枢轴（这称为 “分区”）。这样，枢轴值首先将整个元素分成两部分，然后通过为每个子部分找到一个枢轴来递归工作，直到所有部分只包含一个元素。
1li2R53Ax1CHoFlpkNgudtQ
快速排序算法
在我们上面的示例中，未排序分区的第一个元素被选为枢轴元素（以黄色突出显示）。较小的元素标记为绿色并在左侧排序，较高的元素以紫色突出显示并排列在右侧。
让我们看看顺序。开始时，选择 29（左侧的第一个元素）作为枢轴。当枢轴放置在适当的位置时，所有小于它的元素都放在左侧（一个子组），高于它的元素放在右侧（另一个子组）。然后选择 5（左侧未排序列表的第一个元素）作为新的枢轴元素，整个过程迭代，直到这一侧排序。
左侧组排序后，算法继续移动到右侧未排序组，并选择 41（左侧的第一个元素）作为枢轴，并在这一侧执行相同的过程，直到整个数据集是从低到高排序的。
在快速排序中，可以选择数据集中的任何元素作为枢轴：第一个元素、最后一个元素或任何其他随机元素。那么最好的做法是什么？与往常一样，没有一个直接的解决方案，这实际上取决于您要解决的问题。你可以：
始终选择第一个元素作为枢轴
始终选择最后一个元素作为枢轴
选择一个随机元素作为枢轴
选择中位数作为支点
如果分区后产生的细分不平衡（这意味着您在枢轴的一侧获得的元素很少，而在另一侧获得大量的元素），快速排序将需要更多时间才能完成。为避免这种情况，您可以选择 随机枢轴元素 并分散获得不平衡分区的风险。
选择哪一个？
自然，计算机科学家会不断发明其他排序算法，这些算法具有自己的优缺点，因此请谨慎选择排序算法。选择正确的排序算法，您的程序可以快速运行。选择错误的排序算法，您的程序可能看起来慢得让用户无法忍受。 作为一般规则，插入排序最适合小列表，冒泡排序最适合已经几乎排序的列表，而快速排序通常在日常使用中最快。
你明白了：一些算法在管理数量相对较少的项目时速度很快，但如果你强迫它们管理大量项目，速度就会很快变慢。另一方面，其他算法在对最初几乎正确排序的项目进行排序时非常快速和有效，但如果对随机散布在列表中的项目进行排序，则速度很慢。
但是，如果你能充分利用每一个呢？ 混合算法 是要走的路。
混合算法结合了解决同一问题的两种或多种其他算法，要么选择一个，要么在处理过程中在它们之间切换。
编辑推荐
1、2022年300个以上最佳免费数据科学课程
2、大厂数据分析面试指南！来自亚马逊、谷歌、微软、头条、美团的面试问题！
3、机器学习模型方法总结
4、历史最全机器学习/深度学习/人工智能专业术语表中英对照表
5、机器学习如何应用于商业场景？三个真实的商业项目
6、数据工作者的自我修养 | 哪些技能是必不可少的？
7、《汗牛充栋：数据分析书籍分享》CDA网校新课上线
8、文本挖掘常用的107个语料库
9、一图读懂“东数西算”工程
10、零基础转行数据分析，看这篇文章就够了
DA内容精选
京公网安备 11010802022788号
