当我们考虑“信息技术”时，可能会想到的图像是在屏幕上迅速闪烁的代码线，人工智能的未来以及令人难以置信的虚拟图像如此真实地呈现，以至于我们无法将它们与现实本身区分开。但是，尽管如此，计算机也必须处理行人任务。实际上，计算机科学无非是对所有简单或先进算法背后的所有子任务的研究。在这些任务中，我们现在将花一些时间看一台计算机可以眨眼所能做的事情，但是普通孩子认为这是一场噩梦：整理或分类。
排序是人们最重的工作之一，但是机器能够快速有效地进行。
有趣的是，在“分类”一词中，两个隐藏的含义在解决方案时需要截然不同的方法。首先是将事物放在井中的更明显含义：接收一堆数据并按照给定的模式按顺序（顺序）。例如，教师可能已经进行了大量考试，他们需要按姓氏按字母顺序订购完成的测试。如果我们想做的是在较长时间内保留规定的订单，这是一个不同的问题。举例来说，让我们考虑一个以特定方式组织所有书籍的库（它们是“订购”或“排序”）。当一批新的书籍到来时，图书馆员负责将新条目放在适当的地方，以尊重现有的订单。第二个问题发生在计算机中（例如，一旦结构结构，数据库往往会保存），而不是“现实生活”中混乱在给予机会时倾向于接管的情况。
在本文中，我们将重点关注第一个问题。场景始终相同：一台计算机会收到一堆数据，对于每对数据，它应该将其放置在另一个数据之前。这种方法是为我们抽象问题的一种方式。如果我们正在组织数字或我们以他们的姓氏来安排他们的姓氏，则同样有效。重要的是，哪些数据元素“之前”。结果必须始终是元素本身的序列，但安排得当。令人着迷的是，对于一个很容易解释的问题，不仅有一种或两种算法，而且有数十个算法。我们将在这里解释其中一些
在“现实生活”中，混乱倾向于接管。
旅程是逐步进行的
我们将讨论的前两种算法处理元素的输入数据集。意思是，在第一步中，他们选择了要按顺序排列的值之一，并使用它做点什么。正如我们稍后将看到的那样，这不是最有效的方法，而是最简单的方法。
让我们从Minsort开始 - 它的名称来自“最低排序”。这个概念是继续前进，在每个步骤中，将集合的最小元素（最小元素）列入已有排序的列表中。因为每次集合中只有“较大”元素，这确保我们在过程结束时我们将有一个有序的序列。
让我们看一个示例，其中有以下元素：“ 3、2、4、1、5。”Minsort将执行五个步骤以获取有序列表：
它将寻找最小元素（在这种情况下为1），并将其定位为第一顺序值。其余元素为“ 3、2、4、5。”
现在，它将寻找新的最小元素（这是2个），并将其放置在我们列表的末尾，现在将是“ 1，2”。其余元素为“ 3、4、5”。
新的最小元素为3，排序列表为“ 1、2、3”，剩余4和5。
在下一步中，4位于订购列表的末尾“ 1、2、3、4”的末端。
最后一个数字是5，它将关闭我们的列表“ 1、2、3、4、5。”
要注意的一个重要点是，尽管在步骤2之后，要排序的数字集已按顺序排列，但该算法并不是“意识到”这一事实（如果该集合是由1,000个元素而不是5个元素。
Minsort的步骤数始终等于要订购的元素数量
在同一算法家族中，我们发现插入排序。在这种情况下，我们还将增加已经有序的列表，但是我们将选择每个正在考虑的元素的正确位置，而不是每次选择最小的元素。例如，如果我们有“ a，c”列表，并且要插入字母“ b”，我们将确保输出是列表：“ a，b，c。”让我们看一下我们的“ 3、2、4、1、5”示例，并使用插入排序订购：
要解决的第一个元素是3，它成为我们有序列表中的第一个元素。
然后，我们将2个算法插入列表中的2，算法知道2在3之前出现，因此由此产生的有序列表为“ 2，3”。
现在是第4号。由于4大于2，因此该算法通过第一个位置，因为4大于3。结果是一个新列表：“ 2、3、4。”
我们将继续将所有元素继续如此，直到列表最终为“ 1、2、3、4、5”，正如我们所期望的。
无论其最终功能如何，一个重要的算法属性是完成运行必须采取多少步骤。这就是我们所说的算法的复杂性，也是计算的基本研究集中之一。在Minsort的示例中，在每个步骤中，我们都必须寻找最小的元素。这需要与剩余元素之间的比较一样多。因此，我们的示例需要5+4+3+2+1 = 15步。通常，如果我们要安排n个元素，我们需要采取n*（n+1）/2步 - 您可以吗？确认如果n为5，则结果为15）。计算插入排序的复杂性更为复杂，因为这将取决于我们在找到正确的位置之前必须通过的已经有序的列表。但是，平均结果与Minsort相同。
我们可以做得更好：我们可以找到更有效地对数据元素进行更有效的算法。这不是一个琐碎的问题：对元素进行分类所需的时间越少，意味着用户必须等待的时间就越少。更少的时间也意味着减少能源消耗：更多的时间享受火车上通勤的智能手机，而排放量则更少。
分裂和征服
前面提到的算法的问题在于，他们试图在全球范围内处理其任务，这意味着分别解决完整列表的每个元素，但要一次。我们的下一批算法旨在将初始元素集分为各种子集，这些元素将分别解决。因此，在谈论算法时，我们会说“分裂和征服”，参考古罗马格言。
让我们从“合并”有一个合并开始？技术底色，是指加入事物的特定方式（要素）。但是，让我们不要领先。合并排序分为两个阶段：首先将初始集合分为两半，然后将它们分为两半，依此类推，直到最终以仅包含一个元素的集合为止。
在我们的示例中，我们将“ 3、2、4、1、5”分为“ 3、2、4”和“ 1、5”（不可避免的是，当我们的一组将比我们正在处理不均匀数量的元素）。然后将“ 3、2、4”分为“ 3、2”和“ 4”以及？“ 1，5”分为单个元素的集合。最后，“ 3，2”也被分开，以达到仅拥有一个元素的目标的目标。我们可以像树一样可视化这个过程（或者至少像计算机科学家所理解的“树”）：
树1
合并排序的第二阶段在于重建列表，但要确保在订购的每个步骤中。我们必须欣赏的第一件事是，只有一个包含一个元素的列表将始终被订购。其次，如果我们有两个已经订购的列表，我们可以通过并行检查并每次选择两个列表的较小元素来轻松加入它们。从技术上讲，此过程是“合并”一对有序列表的内容。
在我们的示例中，我们从两个列表“ 3”和“ 2”开始。合并它们会导致列表“ 2，3”。我们已经查看了此级别的所有列表，因此我们将在树上上升一个级别。首先，我们有“ 2，3”列表（“ 3，2”和“ 4”的有序版本，将它们合并到有序列表“ 2、3、4”中，在树的另一侧，我们得到列表“ 1，5”，最后，我们必须合并“ 2、3、4”和“ 1、5”。这整个过程可以看作是分离阶段的倒数：
树2
所有这一切的吸引力是要订购的子集变得越来越小：每一步我们将集合划分一半。从数学上讲，我们看到树上的“级别”的数量是2的初始元素数的对数，这是在Yore时期的数学课程的提醒，N的对数是N到2的基础。将是为了获得原始n的指数。例如，对数为2的对数为3，因为2对3等于8。在每个级别，我们必须合并到一开始就和我们所拥有的元素一样多，因此最终我们确定合并的复杂性排序为n*log_2n。具体数字并不像它比先前讨论的算法要小的事实重要。
合并排序元素的方法非常容易：每一侧一半。但是，还有另一种方法可以解决该问题，这是由快速排序算法使用的。我们要做的是从列表中选择任何元素作为分离器，也称为枢轴（最终选择枢轴的选择并不重要）。我们将将比分离器小的元素与较大的元素分开。
在我们的示例“ 3、2、4、1、5”中，我们将选择中心元素作为分离器。在第一步中，中心元素是4，因此我们将元素划分为较小的元素（3、2、1）和较大的元素（5）。现在，我们使用“ 3、2、1”做同样的事情：我们将将2个作为中心元素，然后将较小（1）和较大（3）分开。我们可以在树上看到这个过程：
树3
这种方法的吸引力是，现在我们不需要第二次合并时：如果我们从树上最低的分支中阅读元素，我们会立即获得订购的列表！这种方法的唯一困难是，除了分区外，我们还必须记住我们用作枢轴的东西。
进行合并排序的计算稍复杂，对于QuickSort，我们获得了相似的复杂程度。那么，名称中的“快速”来自哪里？事实证明，如果我们考虑算法的其他变量，例如内存使用情况和数据备份传输，那么QuickSort最终是实践中比合并排序更好的选择。然而，只有在我们顺序运行算法时，此分析才有效。如果我们可以将工作分配在各种并行处理器之间，那么合并将证明自己是值得的竞争者。无论如何，在谈论订购或分类数据时，大多数程序员最终都会使用QuickSort或其某种变化。
组织成桩
现在让我们想象以下内容：我们给您一堆护照，并要求您按数字进行排序（并且我们假设护照确实是一个数字，而不是字母和数字的混乱）。你会怎么办？
肯定没有什么比我们迄今为止所描述的。否：您将首先用一堆以1起从1开始的护照，另一个以2开始的护照，依此类推（如果您像我一样从0）。然后，您将占据1号堆，然后重复第二个数字，直到您最终只有一块护照（或者有一个可以通过简单的眼球安排的小堆。）恭喜，您已经执行了算法不知道它：radix排序（也称为“桶排序”）。
分类系统包括“堆积”类似元素。
没有进行比较研究，这似乎是人类分类的最“自然”的方式。但是，该算法并不经常用于编程。原因是因为我们将数字“看到”为一系列数字，41自然是4，然后是1。对于计算机，一个数字是一个总体实体，并且不可分割：如果我们想使用计算机复制我们的护照订购练习，要获得“数字的第一个数字”，这将花费我们很多工作。除此之外，我们很容易生产10堆，因为我们已经完全同化了数字的顺序。不过，计算机会看到由1s和0s组成的数字，因此，制作2个桩将“更有意义”。因此，我们返回合并或QuickSort方法。
有更好的方法吗？
计算机科学非常依赖数学。具体而言，与物理或化学相反，在信息技术中，我们可以在任何情况下测试特定定理，而不仅仅是要验证的假设。一个这样的定理告诉我们，我们无法在使用Merge或QuickSort分类事物的时间上有所改善。
但是要当心！该定理仅适用于我们的最初问题。如果我们可以假设已经订购了集合的一部分，例如将元素插入数据库的情况，我们可以做得更好。此外，所有这些讨论都认为我们正在使用一台常规计算机，只能一次执行一个操作。一旦量子计算出现主流，该障碍可能会消失。
亚历杭德罗·塞拉诺（Alejandro Serrano Mena）