排序算法

从计算开始，排序问题就吸引了大量的研究，也许是因为有效解决它的复杂性，尽管它的陈述简单、熟悉。大约在1951年，贝蒂·霍尔伯顿(Betty Holberton )是早期排序算法的作者之一，他研究了电子数值积分计算机和UNIVAC 。^[1][2] 早在1956年就有对冒泡排序的分析。^[3]比较排序算法的基本要求是 Ω(n log n)比较(一些输入序列需要n log n 比较的倍数)；不基于比较的算法，如计数排序，可以具有更好的性能。自20世纪中期以来，渐近最优算法就已为人所知——有用的新算法仍在不断被发明出来，现在广泛使用的Timsort 可追溯到2002年，而空位插入排序最早于2006年发表。

排序算法在计算机科学导论中普遍存在，其中大量的算法为问题提供了各种核心算法概念的大体介绍，例如大O符号，分治算法，数据结构，例如堆和二叉树，随机算法，最佳、最差和一般情况分析，时空权衡，和（时间空间）上限和下限。

排序算法通常按以下方式分类:

• 计算复杂性 ( 最坏、平均和最佳表现)根据列表(n)的大小。对于典型的串行排序算法，较好的表现是O(n  log n)，或者并行排序中的 O(log² n)，不好的表现是O(n²)。(见大O符号)。串行排序的理想表现是O(n)，但这在一般情况下是不可能的。最佳并行排序是O(log n)。基于比较的排序算法对于大多数输入至少需要ω(n  log n)次比较。
• 计算的复杂性交换(对于“就地”算法)。
• 内存的使用(以及其他计算机资源的使用)。特别是，一些排序算法是“就地”。严格地说，就地排序除了要排序的元素之外，只需要O(1)个内存；有时O(log(n))额外的存储器被认为是“就地”的。
• 递归。一些算法要么是递归的，要么是非递归的，而另一些算法可能两者都是(例如，归并排序)。
• 稳定性:用相等的键(即值)保持记录的相对顺序。
• 无论它们是否是一种比较排序。比较排序仅通过用比较运算符比较两个元素来检查数据。
• 一般方法:插入、交换、选择、合并、等等。交换类别包括冒泡排序和快速排序。选择排序包括摇晃排序和堆排序。
• 无论算法是串行的还是并行的。本讨论的其余部分几乎完全集中在串行算法上，并只考虑串行操作。
• 适应性:输入的预压缩是否影响运行时间。考虑到这一点的算法被认为是自适应的。

2.1 稳定性

稳定的排序算法对重复元素进行排序，排序顺序与它们在输入中出现的顺序相同。对某些类型的数据进行排序时，在确定排序顺序时，只检查部分数据。例如，在右边的卡片分类示例中，卡片按其等级进行分类，而它们的花色被忽略。这使得原始列表有可能有多个不同的正确排序的版本。稳定的排序算法根据以下规则选择其中一个:如果两个项目比较相等，就像两个数值为5的卡片一样，那么它们的相对顺序将被保留，因此如果在输入中一个在另一个之前，它在输出中也将在另一个之前。

更正式地说，被排序的数据可以表示为值的记录或元组，用于排序的数据部分被称为键。在卡片示例中，卡片被表示为记录(等级、花色)，关键是等级。如果每当有两个记录R和S具有相同的键，并且R出现在原始列表中的S之前，那么在排序列表中R总是出现在S之前，则排序算法是稳定的。

当相等的元素无法区分时，例如整数，或者更一般地说，任何以整个元素为关键的数据，稳定性都不是问题。如果所有键都不同，稳定性也不是问题。

不稳定的排序算法可以专门实现为稳定的。这样做的一种方法是人为地扩展键比较，以便使用原始输入列表中条目的顺序来决定具有相同键的两个对象之间的比较。然而，这个顺序可能需要额外的时间和空间。

稳定排序算法的一个应用是使用主键和辅键对列表进行排序。例如，假设我们希望对一手牌进行排序，使得花色排列在梅花(♣)、钻石(♦)，心形(♥)，黑桃(♠)，在每套花色中，牌是按等级排序的。这可以通过首先按等级(使用任何排序)对卡片进行排序，然后按花色进行稳定排序来实现:

在每套花色中，稳定排序保持已经完成的按等级排序。这种思想可以扩展到任意数量的键，并被基数排序所利用。通过使用字典键比较，对于不稳定的排序也可以达到相同的效果，例如，首先根据花色进行比较，如果花色相同，然后根据等级进行比较。

在这张表格里，n是要排序的记录数。“平均”和“最差”列给出了每种情况下的时间复杂度，假设每个键的长度是恒定的，因此所有比较、交换和其他所需的操作都可以在恒定的时间内进行。“内存”表示在相同假设下，所需的辅助存储量超出了列表本身所使用的量。下面列出的运行时间和内存要求应该理解为在大O符号内部，因此对数的基数并不重要；符号log² n表示(log n)²。

3.1 比较排序

以下是所有比较排序的表格，在一般或最坏的情况下，其性能不能优于O(n log n)。

3.2 非比较排序

下表描述了整数排序算法和其他非比较排序的排序算法。因此，它们不受限于Ω(n log n)。以下假设有n个要排序的项目，带有大小键k，数字大小d，要排序的数字范围为r。其中许多是基于这样的假设，即k足够大，以至于所有条目都具有唯一的密钥值，因此n ≪ 2^k，≪的意思是“少得多”。在单位成本的随机存取机模型中，运行时间为   ，例如基数排序，仍然需要Θ(n log n)，因为n仅限于不超过   ，要排序的元素越多，就需要越大的k以便存储它们。^[13]

Samplesort 可用于并行化任何非比较排序，方法是将数据有效地分布到几个桶中，然后将排序传递给几个处理器，而不需要合并，因为桶已经在彼此之间进行了排序。

3.3 其他

与上面讨论的算法相比，有些算法很慢，例如bogosort无限运行时间和傀儡分类它有O（n^2.7)运行时间。这些分类通常是为了教育目的而描述的，以证明算法的运行时间是如何估计的。下表描述了一些排序算法，由于性能极低或专门的硬件要求，这些算法在传统软件环境中的实际使用是不切实际的。

理论计算机科学家有详细的其他排序算法，在假设附加约束下会具有比 O(n log n) 更好的时间复杂性，包括:

• 韩氏算法，用于从有限大小的域中排序密钥的确定性算法，需要O(n log log n)时间和O（n)空间。^[16]
• 托鲁普算法，一种用于从有限大小的域中排序密钥的随机算法，需要O(n log log n)时间和O（n)空间。^[17]
• 一种随机整数排序算法需要    的预期时间和O（n)空间。^[18]

虽然有大量的排序算法，但在实际实现中，少数算法占主导地位。插入排序广泛用于小数据集，而对于大数据集，使用渐近有效的排序，主要是堆排序、归并排序排序或快速排序。有效的实现通常使用混合算法，将整体排序的渐近有效算法与递归底部小列表的插入排序相结合。高度优化的实现使用更复杂的变体，如安卓、Java和Python中使用的Timsort (归并排序、插入排序和附加逻辑)，以及一些 C与C++程序设计学习与实验系统排序实现和NET中使用的introsort (快速排序和堆排序)(以变体形式)。

对于更受限的数据，如固定间隔内的数字，如计数排序或基数排序被广泛使用。冒泡排序及其变体很少在实践中使用，但在教学和理论讨论中很常见。

当对对象进行物理排序时，如按字母顺序排列的论文(如测试或书籍)，人们通常直观地对小集合使用插入排序。对于较大的集合，人们通常首先使用桶，例如通过首字母，多个桶允许对非常大的集合进行实际排序。空间通常相对开销小，例如将物体分散在地板上或大面积区域，但操作成本很高，特别是将物体移动很远——参考位置很重要。合并排序也适用于物理对象，特别是因为可以使用两只手，每个列表一只手进行合并，而其他算法，如堆排序或快速排序，不太适合手工使用。其他算法，如图书馆排序，一种留下空格的插入排序变体，也适用于物理使用。

4.1 简单分类

最简单的两种排序是插入排序和选择排序排序，由于开销低，这两种排序对小数据都有效，但对大数据都无效。实际上，插入排序通常比选择排序快，因为几乎排序的数据比较少且性能良好，因此在实践中更受欢迎，但选择排序使用较少的写入，因此在写入性能成为限制因素时使用。

插入排序

插入排序是一种简单的排序算法，对于小列表和大部分已排序的列表相对有效，并且通常用作更复杂算法的一部分。它的工作原理是从列表中一个接一个地取出元素，并将它们插入到新的排序列表中的正确位置。^[19]在数组中，新列表和剩余元素可以共享数组的空间，但是插入开销很大，需要将后面的所有元素移动一个。(见下文)是插入排序的变体，对较大的列表更有效。

选择排序

选择排序是一个就地的比较排序。它有 O (n²)复杂性，这使得它在大型列表上效率低下，并且通常比类似的插入排序性能更差。选择排序以其简单著称，并且在某些情况下比更复杂的算法具有性能优势。

该算法找到最小值，将其与第一个位置的值交换，并对列表的其余部分重复这些步骤。^[20]它只不过是n次交换，因此在交换开销很大的情况下非常有用。

4.2 高效分类

实用的一般排序算法几乎总是基于平均时间复杂度(通常是最坏情况下的复杂度)为 O(n log n)，其中最常见的是堆排序、归并排序和快速排序。每种方法都有优点和缺点，最重要的是归并排序的简单实现使用了O(n)额外的空间，简单的快速排序实现有O(n²)最坏情况下的复杂性。这些问题可以以更复杂的算法为代价来解决或改善。

虽然这些算法对随机数据是渐近有效的，但为了对现实世界数据的实际效率，进行了各种修改。首先，这些算法的开销在较小的数据上变得很大，因此通常使用混合算法，一旦数据足够小，通常会切换到插入排序。其次，算法通常在已经排序的数据或几乎排序的数据上表现不佳——这些在现实世界中很常见，并且可以用O(n)通过适当的算法计算时间。最后，它们在某种程度上也可能是易变的，稳定性通常是理想的特性。因此，经常使用更复杂的算法，例如Timsort(基于归并排序)或内含排序(基于快速排序，返回堆排序)。

归并排序

归并排序利用将已经排序的列表合并到新排序列表中的特性。它从比较每两个元素开始(即1与2，然后3与4...)，如果第一个应该在第二个之后就交换它们。然后，它将两个结果列表中的每一个合并成四个列表，然后将这些四个列表合并，依此类推；直到最后两个列表被合并到最终的排序列表中。^[21]在这里描述的算法中，这是第一个可以很好地可扩展到非常大的列表的算法，因为它最坏的运行时间是O(n log n)。它也很容易应用于列表，而不仅仅是数组，因为它只需要顺序访问，而不需要随机访问。然而，它有额外的O(n)空间复杂性，并且在简单的实现中涉及大量副本。

由于其在复杂算法“Timsort ”中的使用，归并排序在实际实现中的受欢迎程度相对较高，Timsort用于编程语言“ Python ”中的标准排序例程^[22]和 Java (从JDK7 开始)^[23]中。归并排序本身是Perl 中的标准例程，^[24]并且至少从2000年开始在Java的JDK1.3中使用。^[25]

堆排序

堆排序是选择排序的更高效版本。它也是通过确定列表中最大(或最小)的元素，将它放在列表的末尾(或开头)，然后继续操作列表的其余部分，但是它是通过使用一种称为堆(一种特殊类型的二叉树)的数据结构来有效地完成这项任务。^[26]一旦数据列表被制成堆，根节点就保证是最大(或最小)的元素。当堆被移除并放在列表末尾时，列表就会被重新排列，以便剩余的最大元素移动到根元素。使用堆，查找下一个最大的元素需要O(logn)时间，而不是用于简单选择排序中的线性扫描的O(n)。这允许堆排序在 O(n log n)内完成，这也是最坏情况的复杂性。

快速排序

快速排序是分而治之的算法，实现依赖于划分操作:将一个数组中的元素选定为一个主元。^[27][28]所有小于主元的元素被移动到它之前，所有大于主元的元素被移动到它之后。这可以在线性时间和原地有效地完成。然后，较小和较大的子列表被递归排序。这产生平均时间复杂度为O(n log n)，因此这是一种流行的算法。快速排序(使用就地分区)的有效实现通常是不稳定的排序，并且有些复杂，但在实践中是最快的排序算法之一。连同它适度的O(logn)空间使用，快速排序是最流行的排序算法之一，在许多标准编程库中都可以使用。

关于快速排序的重要提示是，它的最坏情况性能是O(n²)；虽然这种情况很少见，但在朴素的实现中(选择第一个或最后一个元素作为主元)，会作为一种常见情况发生在已排序的数据中。因此，快速排序中最复杂的问题是选择一个好的主元，因为一贯错误的主元选择会导致O(n²)性能，但是良好的选择了主元会带来 O(n log n) 的性能，这是渐近最优的。例如，如果在每个步骤中，中间值被选择为主元，则算法的性能能达到O(n log n)。但通过中位数算法在对未排序列表的操作找到的中位数 会带来O(n)的开销，因此这种排序会带来大量开销。实际上，随机选择主元几乎肯定会产生 O(n log n)的性能。

希尔排序

希尔排序，不同于冒泡排序，它将元素移动到许多交换位置。

希尔排序是由唐纳德·希尔在1959年发明的。它通过一次将无序元素移动到多个位置来改进插入排序。希尔排序背后的概念是在   时间的插入排序，其中k是两个不适当元素之间的最大距离。这意味着，一般来说，它们性能达到O（n²)，但是对于大部分已排好序的数据，只有少数元素不在正确位置上的话，它们的执行速度更快。因此，通过首先对远处的元素进行排序，并逐渐缩小要排序的元素之间的间距，最终排序的计算速度要快得多。一种实现可以描述为将数据序列排列在二维数组中，然后使用插入排序对数组的列进行排序。

希尔排序最差情况下的时间复杂度是一个开放问题，取决于所使用的步长序列，已知的复杂度范围从O（n²)到O（n^4/3)和θ(n log² n)中。这一点，再加上希尔排序的就地，只需要相对少量的代码，并且不需要使用调用堆栈，使得它在内存要求高的情况下非常有用，例如在嵌入式系统和操作系统内核中。

4.3 冒泡排序及其变体

冒泡排序和诸如鸡尾酒类的变体是简单但效率非常低的种类。因此，它们经常出现在介绍性文本中，并且由于易于分析而具有一定的理论意义，但在实践中很少使用，主要是出于娱乐目的。一些变体，如希尔排序，对它们的行为有公开的疑问。

冒泡排序

冒泡排序是一个简单的排序算法。算法从数据集的开头开始。它比较前两个元素，如果第一个大于第二个，它会交换它们。它继续对每对相邻元素执行此操作，直到数据集结束。然后，它又从前两个元素开始，重复直到最后一遍没有交换。^[29]该算法的平均时间和最坏情况下的性能为0(n²)，所以它很少用于对大型无序数据集进行排序。冒泡排序算法可用于对少量项目进行排序(其渐近效率不高)。冒泡排序也可以有效地用在几乎已排好序的任何长度的列表上(也就是说，元素没有明显的无序)。例如，如果任意数量的元素仅在一个不正确的位置(例如0123546789和1032547698)，冒泡排序的交换将在第一次通过时按将他们排列好，第二次通过将按顺序查找所有元素，因此排序将只需要2n时间。

^[30]

梳排序

梳排序是一种基于冒泡排序的相对简单的排序算法，最初由Wlodzimierz Dobosiewicz于1980年设计。^[31]它后来被斯蒂芬·莱西和理查德·博克斯重新发现和推广在发表于1991年4月的字节杂志文章中。基本思想是消除海龟，即列表末尾附近的小值，因为其在冒泡排序会大大降低排序速度。（兔子它通过首先交换数组中彼此相距一定距离的元素，而不是仅交换彼此相邻的元素，然后收缩所选的距离，直到它作为正常的冒泡排序操作。因此，如果希尔排序可以被认为是插入排序的一个广义版本，交换彼此间隔开一定距离的元素，那么梳排序可以被认为是适用于冒泡排序的相同概括。

4.4 分布排序

分布排序指的是，数据根据它们的输入分布到多个中间结构，然后收集并放置在输出上的任何排序算法。例如，桶排序和闪存排序都是基于分布的排序算法。分布排序算法可以在单个处理器上使用，或者它们可以是分布式算法，其中单个子集在不同的处理器上单独排序，然后组合。这允许对太大而无法放入单个计算机内存的数据进行外部排序。

计数排序

当已知每个输入属于特定集合S时，计数排序适用。该算法需要O(|S| + n)时间和O(|S|)内存，其中n是输入的长度。它的工作原理是创建一个|大小为S的整数数组|和使用i个容器用来计算第i个成员在输入S中的次数。然后，通过增加其对应的容器的值来对每个输入进行计数。之后，计数阵列循环通过以按顺序排列所有输入。这种排序算法通常不能使用，因为算法需要S足够小才能有效，但它非常快，并且表现出很好的渐近行为，如n增加。它也可以被修改以提供稳定的行为。

桶排序

桶排序是一种分治排序算法，它通过将数组划分为有限数量的桶来泛化计数排序。然后，使用不同的排序算法或递归应用桶排序算法，对每个桶进行单独排序。

当数据集的元素均匀分布在所有桶中时，桶排序效果最佳。

基数排序

基数排序是一种通过处理单个数字中的不同位对数字进行排序的算法。n个数字包括k个位，每个数字都在O(nk)时间被排好序。基数排序可以从最低位(LSD)或从最高有效数字(MSD)处理每个数字的位。LSD算法首先按最低有效数字对列表进行排序，同时使用稳定的排序保持它们的相对顺序。然后按下一个数字对它们进行排序，依次从最低有效到最高有效，最后得到一个排序列表。虽然LSD基数排序需要使用稳定排序，但MSD基数排序算法不需要(除非需要稳定排序)。就地MSD基数排序不稳定。计数分类内部常常使用的基数排序算法。混合排序方法，例如对于小容器使用插入分类，基数排序的性能显著提高。

当要排序的阵列的大小接近或超过可用的主存储器时，必须使用(慢得多的)磁盘或交换空间，所以排序算法的内存使用模式变得重要，并且当阵列容易适应内存时可能相当有效的算法可能变得不切实际。在这种情况下，比较的总数变得(相对而言)不太重要，内存部分必须复制到磁盘或从磁盘交换的次数可以主导算法的性能特征。因此，传递次数和比较的本地化可能比原始比较次数更重要，因为相邻元素之间的比较以系统总线速度进行(或者通过缓存，甚至以中央处理器速度进行)，与磁盘速度相比，这几乎是即时的。

例如，流行的递归快速排序算法在有足够内存的情况下提供了相当合理的性能，但是由于它复制数组部分的递归方式，当数组不适合内存时，它变得不太实用，因为它可能会导致大量磁盘之间的慢速复制或移动操作。在这种情况下，另一种算法可能更好，即使它需要更多的总比较次数。

解决这个问题的一种方法是在数组中创建一个索引，然后对索引进行排序，而不是对整个数组进行排序，这种方法在复杂记录(例如在关系数据库中)按相对较小的键字段排序时效果很好。(然后可以通过一次读取索引来产生整个数组的排序版本，但是通常这是不必要的，因为有排序的索引就足够了。)因为索引比整个阵列小得多，所以它可以很容易地放入整个阵列无法放入的内存中，从而有效地消除了磁盘交换问题。这个过程有时被称为“标签排序”。^[32]

另一种克服内存大小问题的技术是使用外部分类例如，其中一种方法是将两种算法结合起来，利用每种算法的优势来提高整体性能。例如，数组可以被细分为大小适合内存的块，每个块的内容使用有效的算法进行排序(例如快速排序)，结果使用k-类似于合并排序 中使用的方式合并。这比在整个列表上执行合并排序或快速排序要快。^[33][34]

技术也可以结合起来。为了对大大超过系统内存的非常大的数据集进行排序，甚至索引也可能需要使用算法或算法组合进行排序，该算法或算法组合被设计为与虚拟内存一起合理执行，即减少所需的交换量。

相关问题包括部分排序(仅排序k列表中最小的元素，或者计算k最小的元素，但是无序的)和选择(计算k第最小的元素)。这些问题可以通过总排序来解决，但存在更有效的算法，即通过推广排序算法来获得。最显著的例子是与快速排序相关的快速选择。相反，一些排序算法可以通过重复应用选择算法来导出；快速排序和快速选择可以看作是相同的旋转运动，不同之处仅在于一个是在两侧递归(快速排序，分治)还是在一侧递归(快速选择，减治)。

排序算法的一种反面是洗牌算法。它们本质上不同，因为它们需要随机数的来源。混洗也可以通过排序算法实现，即通过随机排序:给列表的每个元素分配一个随机数，然后基于随机数进行排序。然而，这在实际情况通常不会实现，并且有一种众所周知的简单有效的洗牌算法:费雪-耶茨洗牌。