关于排序的更多信息

我敢再提出这个话题。 我将从Mikhail Opanasenko（oms7）的文章的链接开始，就完成的工作量以及引用的链接数量而言，这是非常令人印象深刻的。 他开始准备自己的资料，但不了解该出版物，随后在熟悉之后，需要对其进行实质性处理。 对于那些已经阅读本文的人，我通知您，在我的材料中，我们研究了各种数据类型，特别是字符串和实数，使用了boost和bsd库，并提到了本文中缺少的一些其他主题。

有数十种不同的方式可以按顺序排列数据项。 其中，有些可以快速运行，例如，它们可以在几分钟之内对计算机RAM中的任何数据阵列进行排序。 更具体地说，可以说快速排序在不到一百秒钟的时间内就可以在一台好的现代个人计算机中组织十亿个整数。 如果您使用原始的非快速方法（例如气泡排序或选择排序）对大量元素进行排序，则用于此类数据处理的时间可能会超出任何预期-这种“处理”实际上可能需要几天，几周甚至几年的时间。 这种巨大差异是由于以下事实造成的：快速方法的排序时间大约与N log N和原始N ²成正比。 随着N的增加，两个值之间的差异变得非常明显。 因此，合理的做法是仅将原始方法用于处理小数据，例如在现代计算机上处​​理多达数千个元素。 用它们来教授编程和逻辑思维的基础也是很自然的，因为它们比快速方法简单得多。

我想了解当前标准库中现有的排序方法。 找出它们之间的主要特征，工作速度以及特征之间的差异有多大。 此外，我们将在进行比较和头脑锻炼的过程中考虑一些不难实现的方法。 还值得注意的是，GCC编译器以及可能其他优秀的编译器的优化程序可以很好地与各种程序协同工作，从而使代码加速数倍（有时甚至超过5倍）。

让我们从最简单最慢的气泡排序方法开始。 根据此方法，您需要反复遍历数据数组，比较相邻元素，并在相邻元素之间的顺序中断时更改它们的位置。 每次通过之后，至少要有一个元素（最大或最小-取决于所选顺序）。 除了简单之外，此方法还有另一个优点；它不需要额外的内存。 可以注意到冒泡方法的另一个功能-它可以非常快速地处理已经排序的数据，在某些情况下使其成为最快的方法之一。 如果仅对数据进行部分排序，则此方法可以更快地使用它们，但在大多数情况下只能使用很少的数据。 对于测试，我使用了以下实现 。

另一种缓慢的方法是选择排序。 在这里，每次通过时，首先要找到数据中的最大和最小元素，然后将这些元素放置在与所选顺序相对应的极端位置。 在下一遍，我们对没有这些极端元素的数据进行排序。 此方法与气泡排序一样简单，并且不需要额外的内存，但是速度明显更快。 而且，通过这种方法进行的排序执行了记录的最小数量的数据元素排列。 因此，当排列比比较慢得多时，如果数据元素的数量很少，则可以通过选择方法进行排序。 这是我的实现 。 通常会实现这种排序，每遍仅放置一个元素。 堆排序（或金字塔式）（将在后面讨论）是所讨论排序的最高级版本。

最后一种慢速方法（插入排序）的代码可能是实现排序的所有代码中最短的，因此，对于要排序的项目数量很少（数十个）的情况，有时这种方法会被复杂的快速排序所使用。 这有点类似于按气泡排序，因为在这里和那里连续比较相邻的元素。 但是按插入排序将在数据的已排序部分中寻找正确位置的下一个元素，而不仅仅是将极端元素推到极端位置。 使用这种方法，也不需要额外的内存。 像气泡排序一样，插入排序对有序数据非常快，而对部分有序数据则更快。 在后一种情况下，速度明显快于气泡。 通常，按插入排序比按选择排序快一些。 而且与后者不同，它像气泡分选一样稳定。 最糟糕的是，插入排序以相反的顺序处理数据，有时它会变得最慢。 对于测试，使用以下实现 。 如果您不使用线性搜索，而是使用二进制搜索，例如使用std :: bsearch函数，则可以稍微加快速度。 通过使用列表类型的结构可以显着加速，将元素插入其中的速度非常快。 您还可以注意到，这是最自然的排序-例如，在打牌时通常会直观地使用它。

Shell排序是快速方法中最简单的方法，非常适合刚开始学习编程的学生。 这只是气泡排序的一些修改。 它们之间的唯一区别是，在Shell排序中，比较元素之间的距离是从一个通道到另一个通道而变化的，从第一遍的较大到最后一遍，因此，在这些最后的遍中，Shell方法退化为通过气泡的原始排序。 唐纳德·壳牌（Donald Shell）发布了基本的排序算法，该算法于1959年获得了自己的名字。 因此，这是第一批快速工作的通用分类。 为了进行比较，两年后发布了快速排序算法，而蒂姆流行的排序或自省式排序仅在90年代才知道。 Shell排序与一些有趣的尚未解决的数学问题有关，其中主要的问题之一是如何最佳地选择比较元素之间的位移。 找到了一些记录序列，例如A102549 。 这样的序列是通过巨大的计算发现的，因此它们的长度非常短，A102549只有8个元素，仅足以存储多达3,000个元素的数据。 对于大数据，几乎需要随机观察续集。 使用的值接近2的幂， e ，2.25和3的幂。质数接近2的幂显示最差的结果，明显次于最好的结果。 但是事实证明，其他三个选项对性能的影响大致相同，并且可能非常接近最优。 而且，在这三种情况下，使用质数并没有带来明显的好处。 很好奇的是，维基百科（以2.25为基数）对相应作品的引用提出的偏见并未显示出测试的最佳结果，尽管它们与最佳作品的差异很小（不超过5-10％）。 使用A102549作为起点也没有得到任何明显的结果。 Mikhail Opanasenko还试图解开Shell排序，并获得了一个有趣的结果，即由公式s _{n + 1} = 10s _n / 3选择的位移产生了很好的效果，甚至可能接近理想值。 我的结果证实了这一点。 在许多情况下，正是这种偏见提供了最佳结果，尽管并非总是如此，与最接近结果的差距很小（约5％）。 我用于实现Shell排序的代码使用带偏移量的小表，尽管如果您不使用质数，那么表的这些偏移量几乎可以立即计算出来，就像在实现这种给定变体之一时所做的那样。

有趣的是，如果我们以稍有不同的方式使偏移量接近三的幂并使用稍有不同的算法（请参阅实现 ），则在32位数字上，我们将获得接近最佳速度的速度，但在更长的数字上和在行上，我们将获得明显的减速，有时超过100％。 下表还列出了oms7使用的最佳算法的结果，但是尽管顺序显示出良好的结果，但在绝对值方面却大大落后于领导者。

是否会有找到最佳偏移量的方法？ 也许吧，但我敢建议这不是很快。 Shell排序用于Linux内核，并且至少在一个C库中，其代码用于标准qsort（）函数。 从理论上已经证明，Shell最佳排序速度仅比“实际”快速对数方法稍慢。 实际上，对于最佳Shell排序，平均数据处理时间对其大小的依赖性由公式∽N（log N / log log N ） ^2来描述 ，即使对于非常大的N也非常接近于其他快速方法的典型公式∽N log N. 通常，Shell排序的顺序通常比理论上更快的方法还要快，并且仅在处理相当大的数组（大约一千万个元素）时才开始对它们排序。 这种排序绝对不需要额外的内存，并且在填充数据的各种选项中表现稳定，与快速排序相比，它具有优势。 Shell方法不具有稳定性。

快速排序仅比Shell算法复杂一点，仍然是组织随机分散数据的最快方法之一。 但是，这种分类有几个缺点。 她需要额外的内存，在极少数情况下，根据二次方的依赖性，它的工作速度非常慢。 此方法的主要思想是将数据分为两部分：一个部分中的数据应比另一部分中的数据多或少（取决于所选顺序）。 有几种分离方法。 理想情况下，每次划分时，两个部分的大小应大致相同，并且最糟糕的是，当一个部分在划分过程中仅由一个元素组成时。 让我们考虑快速排序算法的几种实现方式，特别是Hoar方法 ，在该方法中 ，从排序数据的中间选择将数据分为两部分的参考元素。

我们还考虑了极为紧凑的Lomuto算法 ，该算法有时比所考虑的Hoare方法略快（约1％）。 但是，在典型的特殊情况下，例如，在有序，逆向或malovariant数据上，Lomuto方法显示出极慢的速度。 另外，在考虑用于快速排序的选项中，这实际上是实际运行中对堆栈大小最贪婪的选择：当对相对较小的数组进行排序时，只有这种排序没有足够的8 MB堆栈空间，我不得不通过ulimit来设置此大小。 这种对堆栈的贪婪会导致处理大数据（数千万行）时的速度大大降低，而且我很难称呼它的本质。 我只能指出，最好不要将下一段中的排序与此类数据一起使用。

Lomuto方法选择最后一个元素作为参考元素，但是有可能根本不需要任何支持元素就可以进行快速排序，更准确地说，由于已经进行了数据二等分，因此在此元素的选择发生了。 事实证明，这种按速度特性进行的排序接近于Lomuto方法，尽管通常更快一点，在极端情况下，它明显比Lomuto快，但比Hoar慢。

2009年，发布了一种两锚快速排序算法 ，该算法成为Java语言的标准。 与最佳典型算法相比，此算法将排列数量减少了20％，但比较的数量没有变化。 它的作者是弗拉基米尔·雅罗斯拉夫斯基。 通常，它确实比其他快速排序要快。 我利用众所周知的事实在x86架构上对交换进行了优化，交换通常比赋值要快，而对于C ++字符串，交换要快得多。 到目前为止考虑的所有快速分类都没有稳定性。

需要额外的内存来快速排序，以组织递归调用。 但是，可以通过优化尾部递归来将第二个此类调用替换为循环，就速度而言，这可能不会带来任何收益，但会大大减少所用附加数据的大小。 我通过这种优化实现了Hoar排序选项。 此外，在系统程序中，您可以检查堆栈指针，如果堆栈指针接近临界值，则可以简单地重置所有递归调用并再次开始排序-在这种情况下，很明显，您需要使用不会降低几乎排序数据的速度的快速排序选项，以上提议的Hoar版本。 从GCC中的标准C语言库开始，考虑使用额外的内存是快速排序的主要思想。 它通常放弃递归。 取而代之的是，他们使用她的模拟，这使三分之一的人可以减少堆栈上的负载。 该代码结果相当大，大约150行。 关于这种分类，下面仍然会有一些内容。

哈希排序可以非常快，接近N。 但是，有时它可以对二次依赖性起作用。 这种分类方法的速度非常取决于输入。 如果通过散列函数将数据均匀分布在辅助数组上，那么我们将获得最快的线性关系。 并且，如果将所有数据分组在相距很近的几个“质心”附近，或者当存在许多相同的数据元素时，也就是说，当发生许多哈希冲突时，我们将得到最差的类型N ²依赖性。 与树排序一样，要对散列进行排序，还需要大量其他数据，例如， 在下面的代码清单中 ，每个可排序整数（int32，x86-64）需要12个额外的字节。 哈希排序的一个有趣特性是，数据元素之间不存在比较操作，这使该排序与上面考虑的所有排序区别开来。 更准确地说，仅在发生碰撞时才需要执行这些操作。 当对键与整个数据元素匹配的数据进行排序时，可以为相同元素的数量使用一个额外的计数器，但这是一个可疑的优化。 您还可以使用二叉树而不是列表来存储哈希冲突数据，这在有很多冲突的情况下极大地加快了个别情况的工作，但是总的来说，当使用二叉树时，在许多情况下，它会减慢速度，尽管在这种情况下，数据必须存储几乎100个字节的附加信息。 我使用二叉树实现了用于哈希排序的三个选项 ：一个使用无序树，另外两个使用std和boost库中的标准树。 除了非常短的字符串以外，哈希排序实际上不适合对文本字符串进行排序，因为不可能为此类数据建立良好的哈希函数。 我无法将标准C ++哈希（unordered_multiset）用于排序：我试图使用单调哈希函数和排序关系代替相等性-这是行不通的。

数组排序与上一个非常相似。 还使用辅助数组，在该数组中，哈希函数输入值。 在发生碰撞的情况下，有必要将被占用元素的连续片段向左或向右移动，将散列函数指示的位置释放给新元素。 为了获得良好的速度，辅助阵列必须比原始阵列多几倍（从2-3倍）。 随着辅助数组大小的增加，速度仅增加到某个极限，具体取决于排序的数据和与其关联的哈希函数，然后（通常为4-5）减小。 操作速度与散列的速度大致相同，但是在好的数据上速度要快一些，而在坏的数据上速度要慢得多。 这种排序也需要大量额外的内存。如果将排序数组中的元素数量限制为略多于40亿，则三重辅助数组将需要与使用散列进行排序相同数量的附加数据，而三重辅助数组将需要28个字节，这明显少于按树排序或小于散列的数量。与树木。这种排序也几乎不适合使用字符串。维基百科上没有关于这种算法的文章，但这是我的实现。

有趣的是，在Wikipedia的一篇很好的概述文章中，没有提到诸如数组排序和哈希这样的中间方法，它们可以自然地放在基于比较元素的方法和基于元素的绝对值的方法之间。

自19世纪以来，按位排序是最快的排序方法之一，根本没有使用比较。（基数排序）。她的想法很简单-您需要处理一组数据表示形式（对于测试，我采用了8位，11位和16位的组）。为每个组建立表，然后以相对简单的方式合并结果。使用按位排序有两种主要方法。使用数字从右到左对数字进行排序（这是LSD-最低有效数字选项），从左到右对字符串进行排序（这是MSD-最高有效数字选项）更为方便。按位排序通常比任何其他数据排序方法都快得多。令人惊讶的是，对按位排序的支持仍然不是很重要：boost和标准C ++库中都没有，我什至不知道它的版本适用于任何知名的使用C ++数字或字符串的库。这种有当然有缺点。它对要排序的数据类型非常敏感，例如，您需要针对每种大小的数据拥有自己的此类排序版本，需要对无符号和有符号整数进行特殊选择，并且支持使用实数可能需要大量的工作。当使用从最低有效字节到最高有效字节的顺序时，其变体通常需要额外的内存，比初始数据要多一些（这比按哈希或数组排序的树要少得多，甚至比按树排序的情况还要少）。此外，此选项对排序长字符串几乎没有用。我的这种代码您需要为无符号和有符号整数做出特殊选择，并且支持使用实数可能需要花费很多精力。当使用从最低有效字节到最高有效字节的顺序时，其变体通常需要额外的内存，比初始数据要多一些（这比按哈希或数组排序的树要少得多，甚至比按树排序的情况还要少）。此外，此选项对排序长字符串几乎没有用。我的这种代码您需要为无符号和有符号整数做出特殊选择，并且支持使用实数可能需要花费很多精力。当使用从最低有效字节到最高有效字节的顺序时，其变体通常需要额外的内存，比初始数据要多一些（这比按哈希或数组排序的树要少得多，甚至比按树排序的情况还要少）。此外，此选项对排序长字符串几乎没有用。我的这种代码此选项不适用于对长字符串进行排序。我的这种代码此选项不适用于对长字符串进行排序。我的这种代码在这里，它基于oms7文章中提到的代码。反向字节顺序选项具有更多用途，非常适合对字符串进行排序。可以实现此选项，而无需使用额外的内存（这样做的代价是失去了稳定性属性），就像在bsd库的radixsort（）函数中所做的那样。我的密码对于此选项，它也基于oms7代码，它使用额外的内存，稍大的源数据，具有稳定性，但未针对字符串进行优化，因此与已提到的bsd库中的类似函数radiadsort（）相比，其性能特征明显较差。 。当使用小的数值数组时，这种排序可能会显示出令人惊讶的不良结果，其工作速度甚至比气泡还慢几个数量级，尽管我们所谈论的很小的值不超过几毫秒，而且这种差异并不容易注意到。这是因为它使用了较小的辅助数组，但是在对较小的数据进行排序时，这些较小的大小可能会大于排序后的数据本身。为了避免变慢，在这种情况下，“从左到右”选项使用插入排序而不是主要排序。总之，值得注意的是，这是我所知的唯一相对流行的，始终可靠地以∽速度运行的排序。N，但是这里的比例系数取决于数据元素的大小，对于字符串或长数字，它可能会非常明显。

按位MSD排序的一个选项是波束排序，波束排序是一种数据结构，可让您有效地放置关联数组的键。尽管优化了内存的使用，但我的实现仍然非常贪婪。通过速度，对长行进行排序时可获得最佳结果。

此外，我们将考虑一些可以在标准库中找到的排序。

让我们从我已经写过的标准C库（qsort，GCC的一种变体）中的快速库开始。我只能在此添加，这种排序以及其他C排序（例如，来自BSD库的以下排序）均不适用于对象数据，尤其是C ++字符串，这是由于此类数据不是POD导致的。有问题的源头后，可以通过用常规分配替换memcpy操作来轻松解决问题。您可能还会注意到，在某些标准C库中，这种排序可能不一定很快，可以用其他替换。在当前版本的GCC中，这种排序甚至具有稳定属性。有时在收集数据时使用上述c-sorting会感到惊讶，例如，通过功能对象使用std :: vector类型时，它们可能会造成困难-我建议您将其与对象数据一起谨慎使用。根据运行情况，这种排序有时相对较慢：在处理数字时，其速度明显不及其他快速排序的实现，但是在使用si字符串时，这种方法会更好，仅使用两个控制点进行排序有时会使它前进，但是从长远来看，标准qsort几乎总是超过它。当我尝试对十亿个整数进行排序时，发现了最有趣的东西-事实证明，填充类型7会导致时间依赖性接近二次定律，也就是说，可能的“处理”持续长达数年（我没有等待结尾并停止了它）在运行21小时后）。数据较少时，这种排序通常可以选择快速工作的锚点。数据较少时，这种排序通常可以选择快速工作的锚点。数据较少时，这种排序通常可以选择快速工作的锚点。

尽管std :: sort中使用的确切方法取决于实现，但仅在GCC上提供信息，尽管C ++标准库中使用了内省式排序。根据运行情况，这是使用数字进行点差排序之后第二快的方法，点差排序的优点很小（从几乎0到30％），但是使用字符串排序时，情况要差得多-可能比引导点低3-4倍。这实际上是一种快速排序，其中考虑了两种特殊情况：1）如果递归的数量太大，则切换到按堆排序； 2）如果要排序的元素数量很少，则将切换到按插入排序。

来自C ++标准库的稳定排序（std :: stable_sort）顾名思义，它具有稳定性-保留具有相同键的元素之间的相对顺序。尽管我只是根据我自己的经验写的，但是这个属性很少是没有必要的，尽管我写得相当毫无根据。它可以使用额外的内存，从而使其速度更快。令人惊讶的是，这种排序通常比std :: sort更快。

在流行语言python中，Tim的排序用作标准。为了进行测试，我使用了github存储库中的版本。它在部分排序的数据上显示了创纪录的良好结果，但平均而言，它仍然比领导者慢得多。通常，它的速度是快速排序和Shell排序之间的平均值，尽管有时它接近领导者。它具有稳定性。它实现了一个相对复杂的算法，在2015年的标准实现中发现了一个错误，但是，要使其表现出来就需要一种相当不现实的情况。

BSD C库具有按位排序（radixsort）及其稳定版本（sradixsort）。不幸的是，这两种类型都只能用于C字符串。从测试数据可以看出，这是当今对字符串进行排序的最快方法，因此令人惊讶的是，对于C ++字符串没有标准的选择。

BSD的C库有更多种类的合并（归并）这种排序被称为最快的顺序访问数据（文件，列表）之一，并且可能在C ++标准库中用于对列表进行排序（std :: list和std :: forward_list）。顺便说一句，她自1948年以来就广为人知，其开发者之一是一位非常著名的数学家和第一台计算机系统von Neumann的专家。在快速方法中，尽管通常比Shell方法要快一些，但是这种排序并没有以最佳特性来区分。它需要额外的内存，并且通常以可持续方式实施。

另外，还有一堆排序（堆排序）。通常将堆用于具有优先级的最佳排队，但也可以用于排序。排序堆不需要额外的内存，但是它们没有稳定性属性。在数字速度上，它比Shell方法要慢得多（最多3到6倍），但是对于不是很短的行，它显示出很好的结果，超过了Shell方法（随着行长的增加，优势不断增加）。

堆排序在C ++标准库中也可用。这种排序是通过两个操作完成的：构建堆（std :: make_heap），然后进行实际排序（std :: sort_heap）在这里，与bsd库不同，排序只是堆操作之一。通常，此排序选项比上一个稍快（bsd选项仅在短数字和长s行上显示更好的结果）。

使用标准的C ++库，您可以对二进制平衡树（std :: multiset）进行排序-只需填充树然后四处走走。可以将这种方法视为非递归快速排序。由于标准内存分配器的速度很慢，因此会出现一些问题，因此，为了获得最佳结果，您需要使用自己的分配器，该分配器的速度可以提高10-30％。还应该注意的是，这种方法需要大量额外的内存，每个数据元素都带有g ++，此外，您还需要存储32个字节（在x86-64体系结构上）-尝试将这样的树存储为堆会很有趣，即无需额外存储字节如果使用boost :: container :: multiset，则需要更少的内存：每个数据元素仅增加24个字节。但是，像助推器一样标准库显示了一个令人不愉快的惊喜-在此过程中，它们有时需要的内存多于所需的内存。也许这是由于二叉树的平衡。代码-在这里。

boost库具有spreadsort，这是21世纪发明的算法。这是当今知名库中最快的整体方法。这种排序使用了一些按位排列的想法，并且像这样，对于参数的类型可能会很烦躁。通常，这种排序显示出创纪录的结果，有时明显优于最接近的竞争对手。唯一的例外是C线的排序，在这种情况下，它明显不如bsd库中的按位方法。在对长C线进行排序时，它可能不如其他方法，例如旋转排序或使用两个锚点进行快速排序。传播排序（boost v1.62）显示了一个非常讨厌的问题-在对小的（最多1000个元素）C字符串数组进行排序时，它会出错。如作者所述，

还有一种新的pdqsort算法可以改进自省排序。这种新算法尚未在Wikipedia上进行描述。其结果-虽然还不错，但并不是特别令人印象深刻。它比std ::在短整数上排序慢，但在字符串和长整数上快。在这两种情况下，差异都不大。对于长C ++字符串，此排序的最佳结果是-在这里，尽管很明显，但仅次于扩展排序的领导者。

在增强中，您仍然可以找到旋转排序。这也是一种新算法，与以前的算法不同，它具有稳定性属性，并且在Wikipedia上也没有描述。通常他与领导者很近，但落后于他。尽管不是太多，但它需要额外的内存。

完成对flat_stable_sort所有同一boost库的。这是维基百科上尚未描述的另一种新的鲁棒算法。这是迄今为止最快的方法，但比大多数其他快速库方法稍逊一筹。它使用很少的额外内存（但是，它始终需要8 KB的固定大小的表），并且通常比Shell方法要快得多。

考虑表这些算法在具有8 GB RAM且装有AMD Phenom™II X4 955 @ 3.214 MHz处理器的计算机上运行这些算法的时间（以毫秒为单位）。该计算机总共工作了几个月，并且在两个装有表的json文件中收集的数据的总大小几乎为400 KB。计时由运行次数的平均值给出；对于较小的尺寸，这些运行次数较大。以相当复杂的方式处理缓存会改变计算速度，因此获得的结果充其量只能算是近似值（我可以假设时序误差最多可以达到20％）。我相信，在适用于PC的最佳现代处理器上，其结果可以获得快2-3倍的速度，但是请记住，更多的现代处理器可以通过在不同频率之间切换以及由此获得的结果来工作，会更加接近。

此表和下表是交互式的。除了计时的绝对值外，您还可以查看它们相对于平均值，中位数，最小值和最大值的值。您可以更改字符的准确性。您还可以获得不同类型的填充和数据类型的时间关系。例如，后者可能表明对C字符串的排序明显比对C ++字符串更快。从排序方法中，您还可以选择和组合各种子集。当然，您可以按任何列设置排序。不幸的是，在该中心的文章中，我不知道如何使用Javascript，因此这些表仅供参考。对于imtqy.com超载的情况，我还提供了指向第一张和第二张表的备份链接。

时间以毫秒为单位，但是根据时间的定律，为了避免系数太小，给出了微秒的公式。因此，如果我们将值替换为公式中的N，则结果还必须除以1000，以得到与表中对应数字接近的数字。时间依赖性定律是根据获得的时序从两个结果的比较得出的（通常是极端的结果）。您可以使用相对于输出的实际值的相对偏差选项来检查派生定律的质量。

该表的结果有一些一般性结论：

• 对多达1000万个元素的数据进行最佳的shell排序可以超越timsort，甚至超过某些快速排序；
• timsort的速度qsort（clib）非常接近，有时超车，有时反之亦然。
• 堆排序（尤其是树排序）通常会明显放慢速度，但是在冒泡甚至选择的背景下，很明显，这些仍然是快速的方法。 有趣的是，这两种方法通常都具有非常相似的特性-它们都可以构建树。 可以很容易地注意到，尽管堆排序和树排序的依存关系虽然不是很明显是二次的，但显然不是N log N ，但是更糟糕的是-与Shell排序相比，Shell排序在数据量增加时的表现要好于heapsort或treesort，而她自己比N log N慢。 因此，堆和树排序的实际实现不符合其理论规范；
• 排序字符串上的数据表明，这里的时间依存规律与数字规律不同-排序后的字符串长度在某种程度上叠加在这些规律上。 不幸的是，我不知道用于已知排序的公式，这些公式在处理字符串时会给出确切的时间相关性定律。
• 有趣的是，实数运算的速度与整数运算的速度大致相同-这是由于以下事实的结果：在现代的x86架构中，进行了非常有效的优化来处理堆栈。
• hash_sort显示的结果相当中等，这是可能的，因为由于使用了额外的内存，处理器缓存的性能急剧下降。 在小的随机数据（少于十万个元素）上，哈希排序会取代最佳的快速排序。 您还可以注意到，由于缓存的存在，这种排序的某些结果还是很奇怪的，例如，使用部分有序填充时，对10 5，10 ⁶和10 ⁷ 32位整数进行大致相同的排序时间！ 某种近似量子效应。 :)我敢肯定，如果您进行搜索，还会发现其他难以解释的结果。

我将在一些特殊情况下添加更多结论：

• 某些类型的数据填充揭示了快速排序中的弱点。 然而，以复杂的方式选择支撑元件使得落入不良排序的可能性几乎为零。 您也可以通过不同的方式或随机选择每次通过的支撑元素。 也许他们在qsort（clib）中这样做。 所考虑的Hoare方法仅在特殊设计的序列上才能非常缓慢地运行，在实际工作中偶然遇到-这是一种概率为2 ^{N -3} / N ^N的情况 ，即几乎绝对不可能发生的事件。 尽管如果我们考虑序列中Hoar方法不能尽可能慢地运行，而仅在显着减慢的情况下，那么会有更多这样的情况，但是，尽管与它的区别非常令人讨厌，但仍然存在不可接受的缓慢数据处理案例的可能性实际上仍然不重要的可能性。零 根据二次定律，几乎不可能偶然获得通过两个控制点进行快速排序的数据将缓慢运行的数据。 Lomuto的快速排序选项在没有支持元素和没有支持元素的情况下，在几乎所有特定填充情况下的结果都非常差；
• 在某些特殊情况下，最慢的“气泡”排序会产生出色的结果，相反，某些最快，最快速的排序却非常糟糕；
• 散列排序对类型8和9的填充显示非常不好的结果，这是因为单调序列是从较小的开头的连续值中选取的，而随机数的1％是从较低值到最大值的范围中的数值，这将填充所有连续的99％的数据成为一个哈希元素。 这种情况很好地说明了使用这种排序或对未知数据的数组进行排序时可能出现的问题。
• 选择排序在所有类型的填充上都非常稳定，堆和树的排序也很稳定，没有明显的高峰和低谷。 当然，对于Shell排序以及标准库中的大多数其他快速方法，这都是正确的。

现在是时候讨论与排序算法一起使用的数据类型了：

1. 32位带符号整数（int32_t），但仅使用非负数。 其他数值数据也只取非负数-这不会降低结果的一般性，但是使某些算法更容易获得它们；
2. 整数，64位有符号（int64_t）;
3. 128位带符号整数（__int128-至少受GCC支持）；
4. 五个整数（int32_t）的结构，其中之一用作键（INT1P4）。 在对此类数据进行排序时，排列的数量开始对计算时间产生更大的影响；因此，排列较少的方法会获得一些优势；
5. 实数，例如双精度，双精度（浮点数）；
6. 短字符串C ++和C。采用从1到16的字符串（短字符串和c字符串短）；
7. 中等长度的字符串C和C ++，长度为1到256（字符串和c字符串）；
8. 长线C和C ++，其长度为1到2 ²⁰ （略大于一百万），并且选择这些线以使它们的平均长度不超过512，因此仅选择这些线用于随机填充，而在其他情况下，这些线只是简单地采用长度从1到512（字符串长和c字符串长）。

还有关于如何填充源数组进行排序的信息：

1. 偶然地
2. 严格上升（命令）；
3. 严格降序（逆序，逆序）；
4. 随机值，范围从0到99（小变化，低变化100）；
5. 0和1的随机序列（小变化，低变化2）；
6. 常数0（小点差，低偏差1）；
7. 导致qsort（Hoare）版本执行最慢的顺序。 奇怪的是，在所有长度为N的序列中，恰好有2 ^{N -3个}这样的序列；
8. 严格提升，插入1％随机数（部分排序）；
9. 严格降序，插入1％随机变量（部分反转）。

应该强调的是，随机数据是填充数组的最典型情况，所有其他方法极为罕见，甚至在特定对象的正常操作期间几乎是不可能的。

让我们看一下测试结果，其中排序与所有可能的数据序列一起工作。 此类序列的数量等于其长度的阶乘，因此，对于长度为12的序列，存在479'001'600个变体-好的现代PC将在不到一分钟的时间内计算出它们的数量。 如果我们采用长度为14的序列，那么经过数小时的计算机操作，我们已经获得了87'178'291'200个变体。 因此，下表显示了将所有排列最多排序到12个时的一次排序的平均时间（通过RDTSC指令获得的处理器周期）。在数据中，采用以前的数字类型和短字符串。 当然，可能会注意到没有考虑具有重复元素的序列。 但是，我敢于建议他们的出现不会从质量上改变结果，但是会大大减慢其接收速度。

如此小的数据的结果不是很具有代表性，尤其是对于复杂的排序方法而言，但是它们仍然补充了排序行为的概念。 据我所知，某些类型的数组在处理小型数组时会用另一种算法替换它们的主要算法-这些是散布排序，具有两个锚点和radix_msd的速度很快（最后两个使用插入）。 某些排序（flat_stable和radix）使用较小的表，但数据量很小，因此这些表比数据本身大得多，与其他方法相比，它们大大降低了这些方法的速度，并产生奇怪的结果。 通过其他按位排序以及哈希和数组排序也可获得奇怪的结果。 通过对小数据的这些方法进行排序之前的数据准备时间长于排序时间本身，这一事实很容易解释。 当然，在测量如此小的时间间隔（纳秒）时，各种误差对显示的定律的影响要比上表高得多。 因此，这些定律非常接近，经常“夸大其词”。 后者的部分解释是，在处理小数据时，排序时间本身变得与调用排序函数的时间和一些用于测量时间的必要辅助操作相当。 该程序尝试从输出中减去命名的开销，但是事实证明，这样做相当近似。 综上所述，我敢于假设，通过比较不同类型数据的结果并考虑所做的评论，您有时可能会做出不太准确的假设。

总之，另一张表显示了对额外的内存进行排序需要多少种不同的测试方法。 显然，该值取决于系统。 正如我已经写过的，在我的测试中，这是x86-64 GCC。 其中的字母T表示类型的大小（以字节为单位）（字符串的长度不包括在此大小中：对于C行，这是指针的大小，对于C ++行，这是描述符的大小，对于x86-64 GCC是32字节），字母L是中间类型的长度（以字节为单位）（数字是T，字符串是字符串的平均长度），字母A可以具有值1或0-这是与64位边界对齐，字母M是标准内存分配器的对齐（假定对齐到32个字节的边界）。 ^*符号表示仅在从/ proc / PID / status中读取VmRSS字段的分析的基础上获得了用于此类排序的数据（提到的字段是过程程序的大小）。


当然，还有其他分类方法，包括原始方法和快速方法。 Boost库具有并行算法，使您可以利用系统中其他处理器内核的优势。 您还可以使用自排序容器boost :: container :: flat_multiset代替std :: multiset，但是它的工作非常缓慢。

我借此机会总体上对Boost库发表一些评论。 我建议不要通过。 通常，甚至在boost中的标准库中的功能也可以更好地实现，有时（例如正则表达式）更好。 如果我们谈论容器，那么在提升时它们会明显变大，而那些与标准容器一致的容器有时会更快一些，并且通常会有很小但很好的改进。 Boost检查类型会更彻底，有时可以帮助检测通常难以表现出来的几乎难以捉摸的错误，但在某些情况下可能会意外激活。 boost的缺点包括无条件地完全不可读，以及关于该库中许多构造上的编译错误的大量消息-尽管在较小程度上适用于标准库。 现在该是C ++开发人员要做的事情了。

所有带有测试的文件以及其他一些相关的资料都可以从我的存储库中获取 。 如果有人对原始源数据感兴趣，则可以在此处获得它（1.4 MB）。 我将很高兴收到任何评论，批评和补充。