梳理排序算法的基本原理

到目前为止，本系列文章已经涵盖了各种各样的数据结构（此处“一系列”一词显然是双关），我非常享受探索程序员以及他们开发的软件如何利用这些结构来解决各种有趣的问题。但今天的文章很特别，因为我们终于要深入探讨一些构成计算机科学世界的、更偏重科学性的内容（如果可以这样称呼的话）。

好了，我就不多说了，咱们直接进入正题。我们终于要开始学习算法了——太棒了！在接下来的几周里，我将深入探讨计算机科学中最常用、引用最广泛的一些算法。

如果你没有计算机科学背景（或者你编程经验尚浅），深入学习算法听起来可能相当可怕，甚至令人望而生畏。但别担心……我们会一起克服难关，最终成为算法专家！那么，让我们先从最基础的知识开始。具体来说：算法究竟是什么？我们将学习很多关于算法的知识，所以我们最好先把这个定义牢记在心，对吧？

原来，“算法”这个词听起来很高级，但名声不太好。它们远没有听起来那么可怕。算法其实只是程序应该做什么以及如何做的指令集，听起来很专业而已。换句话说：它不过是你的代码使用手册。就是这样。（真的！）软件领域中最常被引用的算法通常是排序算法的子集，或者说是为程序或系统如何组织一组数据提供指令的算法。

为什么要自我整顿？

在深入探讨算法对数据进行排序的不同方法之前，我们必须先深刻理解计算机科学中的排序究竟是什么，以及它为什么如此重要。

在日常生活中，我们都或多或少地遇到过需要整理物品的情况。比如，我最近搬家了，虽然我觉得打包得还算不错，但还是有很多东西乱七八糟的。我匆忙地把一堆文件和手稿塞进了搬家纸箱。结果，等到拆箱的时候，一切都乱成一团，纸张也散落一地，真是糟糕透了。我不得不一边拆箱一边手动按页码整理。如果你对排序算法有所了解，就会发现，给一副扑克牌排序、给一本书排序，或者给一组数字排序，都是排序算法常见的应用实例。

这些例子正是我们代码和应用程​​序中日常运行情况的延伸！排序在计算机科学领域尤其有用，原因有二：

1. 从纯粹的人性化角度来看，它使单个数据集更容易阅读。
2. 这样可以更轻松地实现搜索算法，从而从整个数据集中查找或检索项目。

以我为例，如果我的手稿没有整理好所有页面，你可以想象在一堆 200 页杂乱无章的纸张中找到一页纸是多么痛苦的经历。

所以，从实际的、人类的角度来看，排序是有意义的。但是，为什么计算机也需要排序呢？它们速度很快，对吧？它们不需要像人一样把信息看得那么清楚易懂。排序对它们有什么好处呢？

从计算机科学的角度来看，排序扮演着尤为重要的角色，因为计算机、程序或应用程序需要搜索的数据集通常非常庞大。这种规模之大，远远超出了大多数人能够想象的搜索能力！我们稍后会再讨论这个问题。

首先，让我们明确一下在计算机科学语境下，“排序”究竟指的是什么。排序是指根据某种属性对集合中相似项进行组织。这里有两点需要注意：

• 我们可以根据任何一个属性对一组项目进行升序或降序排序，而这个属性实际上可以是任何东西。按大小、字典序（字母顺序）、数字顺序、日期、时间……等等，应有尽有！
• 我们只能对同质（或类型相同）的数据集进行排序。换句话说，我们无法对同时包含单词和数字的数据集进行排序，因为该数据集没有我们可以用来排序的共同属性。

在上面的例子中，我们排序了两个同质列表：list_one 和 list_two。所有元素类型相同，并且我们按升序对它们进行排序。值得一提的是，这些排序后的列表（分别为 list_one_sorted 和 list_two_sorted）是它们原始未排序列表的排列或重新排序。

好了，现在我们已经了解了定义和规则，接下来让我们讨论最重要的问题：计算机如何利用排序？为什么排序后的数据更好？就像排序后的数据对人类来说更易读一样，排序后的数据也大大简化了机器的处理工作。

让我们来看看如果没有整理会是什么样子。剧透一下：似乎很糟糕。

在上面的例子中，我们有一个很小的未排序数字列表。想象一下，我们想找到数字 33，但却不知道它在哪里。或者，更糟糕的情况是：我们想找到一个根本不在列表中的数字！最坏的情况下，我们必须遍历列表中的每一个数字，直到找到最后一个，然后才发现这个数字根本不在列表中！换句话说，这需要线性时间。而使用我们示例的数据集，遍历所有数字所需的时间会非常短。

但如果是1亿个数字呢？或者10亿个呢？

好了，别慌！我们不会去处理一亿个数字，别担心。让我们来看看，在同一个数据集中，如果数据已经排序，找到一个特定的数字会是什么样子。

如果你觉得上面的例子似曾相识，那是因为它正是我们熟悉的二分查找！在完全相同的示例数据集中查找某个数字（即使该数字根本不存在于列表中），其时间复杂度也永远不会超过对数级。希望你还记得，这一切都是因为二分查找的实现方式是每次比较都排除一半的可能结果。

这正是我们的程序如何利用排序的！二分查找是插入、删除或从大型数据集中读取和检索信息的绝佳方法。即使数据集有 1 亿条记录，只要列表已排序，我们的代码也能轻松完成搜索。

各种分类

既然我们都理解了排序的概念，现在就该来详细了解一下常用的不同排序算法了。

排序算法的分类方法有很多，但我们这里只关注其中六种：时间复杂度、空间复杂度（或内存使用量）、稳定性、内部排序或外部排序、递归排序或非递归排序、比较排序或非比较排序。这些分类对于程序员编写排序算法或选择要实现的算法来说至关重要。

这一切最终都会回到我们在本系列文章中已经熟悉的一个主题：不同的工具各有优缺点。在接下来的几周里，我们将深入探讨一些常见的算法，并利用这些分类来帮助我们判断任何给定排序算法的优缺点——以及该算法何时可能有用（或何时可能不太有用！）。

让我们更详细地看一下这些分类：

1. 时间复杂度

对算法进行分类的最简单方法是按时间复杂度，也就是在给定不同输入规模的情况下运行算法所需的相对时间。

由于我们已经相当熟悉时间复杂度（或者我们经常称之为大 O表示法）的概念，因此，当我们开始更详细地学习算法时，我们将用这种方式来分解所有的算法。

2. 空间复杂度/内存使用

不同的算法需要不同的空间，这取决于它们的空间复杂度。在排序算法的背景下，思考空间复杂度的另一种方法是回答这个问题：这个算法运行需要多少内存？

算法的空间复杂度有两种分类方式：原地复杂度或异地复杂度。

原地算法是指直接对输入数据进行操作的算法。这种算法的危险之处在于，数据在转换过程中会被完全改变，这意味着原始数据集实际上会被破坏！然而，它的空间效率更高，因为该算法只需要极少的额外内存空间——通常是常数大小，即 O (1) ——这在内存不足的情况下非常有用。

相比之下，异地排序算法并不直接操作原始数据集；而是创建一个新的副本，并对复制的数据执行排序。这种方法可能更安全，但缺点是算法的内存占用会随着输入规模的增大而增加。

3. 稳定性

通常情况下，一个数据集会有多个元素具有相同的“排序键”；换句话说，列表中的多个项目在排序方式上可以被认为是相等的。

在这个例子中，有两个数字 4，一个是绿色的，另一个是红色的。

鉴于有两个元素可以“同等”排序，因此该列表有两种排序方式：绿色 4 可以排在第一位，就像它在原始列表中那样，或者红色 4 可以排在第一位。

这正是排序算法稳定性的定义所在。

稳定的算法能够保持元素的相对顺序；如果键相同，我们可以保证元素在排序后的列表中保持与排序前相同的顺序。相反，不稳定的算法则无法保证，如果两个元素具有相同的排序键，它们的相对顺序是否会被保留。

4. 内部因素与外部因素

由于我们的机器能够相当轻松地处理大型数据集，因此经常会有一些应用程序需要处理海量数据。在某些情况下，这些数据量甚至可能超过机器主内存（或 RAM）的容量。

算法在对记录进行排序时存储数据的方式，是我们对排序算法进行分类的另一种方式。

如果所有需要排序的数据都可以保存在主内存中，则该算法为内部排序算法。但是，如果记录必须存储在主内存之外——换句话说，存储在外部存储器中，例如磁盘或磁带——则该算法被称为外部排序算法。

5. 递归或非递归

有些算法采用分而治之的方法来排序：也就是说，将大型数据集分割成较小的输入，然后递归地对所有这些较小的输入调用排序函数。这被称为递归排序算法。

相反，非递归排序算法——你猜对了——就是不实现递归的算法！也就是说，它们不会通过对较小的输入调用相同的函数来对较小的子集进行排序。

值得一提的是，大多数算法并非必须递归实现；它们可以用迭代的方式编写和实现。但是，排序算法是否递归，最终成为区分不同算法的一种简便方法。

6. 比较排序

最后，还可以根据排序算法实际执行排序元素工作的方式对其进行分类。

任何在对较大数据集进行排序过程中，一次比较两个项目或一对项目的排序算法都称为比较排序。这类算法使用某种比较器（例如：>= 或 <=）来确定任意两个元素中哪一个应该先排序。

不使用任何类型的比较器进行排序的排序算法称为非比较排序。

就我们的目的而言，本系列文章中我们将要探讨的几乎所有算法都将被归类为比较排序。然而，需要记住的是，并非所有排序算法都需要比较器来定义数据集的顺序和排序！

到处都是分类、分类！

好了，我们已经列举完了所有的分类。希望现在你已经明白排序算法在计算机科学中的重要性！人们花费了大量的时间和精力来研究和撰写排序算法！这其中自有缘由。

排序后的数据几乎驱动着一切。想想看：无论何时你使用网页或移动应用，你都可以按某个属性对大量数据进行排序。数据库也使用一种叫做 B 树的技术来对海量数据集进行排序和搜索。它们处理的数据量之大，我们人类根本无法想象！

我们已经了解了二分查找，也知道它的使用频率和强大功能。你猜怎么着？排序后的数据是使用二分查找的前提条件！

但从更广泛的层面来看，排序算法也应用于统计学，例如，用于确定数据集的中位数，或查找统计异常值！排序算法还用于个人机器上的负载均衡，尤其适用于在多处理器上处理大量数据。

接下来的几周，我们将更深入地了解排序算法对计算机科学的重要性。排序算法有很多种，但我们将介绍一些最常见的算法：

下周，我们将尝试把其中几种排序算法应用到实际问题中，并开始更深入地探索这些排序算法。也许当我们完成这次算法深度解析时，你会改变自己生活中处理事情的方式。又或许，你从此以后再也不想听到任何关于排序的话题。我大胆预测，这两种情况发生的概率各占一半。

资源

关于排序算法，市面上充斥着大量的论文和博士论文：哪些算法最好，哪些算法最高效，以及如何根据不同类别对它们进行排名和分类。光是阅读和学习这些资料，你可能就要花上好几年时间。当然，如果你想找个简单的入门途径，也可以看看这些资源！

1. 非比较排序算法，Ananda Gunawardena 教授
2. 数据结构——排序技术，TutorialsPoint
3. 排序算法，维克多·S·亚当奇克教授
4. 排序算法——稳定性，伊利诺伊大学芝加哥分校数学、统计学和计算机科学系
5. 排序应用，罗伯特·塞奇威克教授和凯文·韦恩教授
6. 排序算法简介，mycodeschool

本文最初发表于medium.com。