取一个反序数组，并
通过简单的inserts对其
进行排序 。
看看在正确的位置将下一个元素插入什么位置。 为此，您需要释放插入位置，因此必须移动所有先前插入的元素。
如果之前插入的元素之间有空白，那将会有多棒！ 这样一来，不必为了插入一个元素而拖动元素的行。
2004年，三位计算机科学专家-Michael Bender，Martin Farah-Colton和Miguel Mostiro-决定以这种方式用简单的插入内容修改排序。 他们建议形成阵列的有序部分，在插入的元素之间留出空隙。
图书管理员需要将这些书按字母顺序排列在一个长架子上：从字母“ A”的左侧开始，这些书彼此之间紧挨着“ I”。 如果图书馆收到一本与“ B”节有关的新书，则要将其放在正确的位置，您必须移动每本书，从“ B”节的中间到最后一个“ I”。 这是通过简单的插入排序。 但是，如果图书馆员在每个部分都保留了自由空间，那么他只需要移动几本书就可以为新书腾出空间。 这是图书馆分类的基本原则。
演算法
- 1.创建一个空的辅助数组，比主数组大几倍。
- 2.对于下一个元素，我们在辅助数组中寻找插入位置。
- 2.1。 如果找到要插入的位置，则转移物品并返回步骤2。
- 2.2。 如果没有插入的地方，请重新平衡辅助阵列并返回到点2。
- 3.处理完所有元素后，将它们传送回主数组。
乍一看，排序似乎很简单。 为了消除这种幻想，我们将更详细地考虑算法的关键点。
辅助阵列尺寸
尽管尚无定论，但辅助阵列应比主阵列大多少倍。
如果您占用过多空间，那么元素之间将有很多空间，但是，由于元素之间的距离较大，因此搜索插入位置和重新平衡会变慢。 重新平衡的频率会降低，但是他们将不得不在上面花费更多的资源。 如果花费太少，那么搜索和重新平衡会更便宜，但是您将不得不更频繁地重新格式化阵列。 通常，仍然需要使用不同的值进行测试，科学戳的方法可以确定最佳选择。
如果我们确定辅助数组比主数组大多少倍，那么确定其确切元素数量的公式如下所示：
NewSize =ε×（大小+ 1）-1NewSize-辅助数组中的元素数
ε-辅助数组比主数组大多少倍
大小-主数组中的元素数如果仅将
大小乘以一个因子：
NewSize = Size×ε ，则对于均匀分布，我们将没有足够的单元格
ε-1个 。 即，可以将它们均匀地布置，但是第一个填充的单元格或最后一个填充的单元格将靠近辅助阵列的边缘。 并且我们需要从各个方面保留填充单元中的空白位置-包括第一个元素之前和最后一个元素之后。
这似乎是一件小事，但实际上对于重新平衡很重要，要保证有自由的位置可以插入任何地方，包括在处理主数组的最后一个元素时。
搜索辅助数组中的插入位置
当然，这里需要二进制搜索。 但是，经典实现对我们不起作用。
首先，辅助数组主要由void组成。 因此，递归地将结构二分，我们将大部分遇到未填充的单元格。 在这种情况下，您需要向左或向右一点走到最近的非空单元格。 然后，在该段的末尾将有重要的元素，使您可以计算算术平均值并继续进行深度二值搜索。
其次，不要忘记边缘。 如果您需要插入最小或最大元素，那么在较早插入的元素中进行二进制搜索将不会有任何结果。 因此，有必要考虑边界情况-首先检查是否有必要将元素放置在数组的左边界或右边界附近，如果不需要，则使用二进制搜索。
第三，考虑到应用程序的细节，值得进行额外的修改以最大程度地减少阵列再平衡的次数。 如果插入的元素等于段末尾之一的值，那么也许您不应该将其插入段中间。 将与其值相等的元素放在旁边是更合乎逻辑的。 这将更有效地填充辅助数组的空白空间。
第四，第五等等。 搜索插入位置的质量直接影响分拣速度，因为选择不成功的插入位置会导致不必要的重新平衡。 例如，根据插入元素的值更接近于哪条边缘，可能不值得在中间精确地划分段，而是更接近段的左边缘或右边缘？
二进制搜索算法本身充满陷阱，考虑到上述额外的细微差别，它最终绝不是一项艰巨的任务。
阵列再平衡
在这种排序中，二进制搜索并不是最难实现的事情。 仍在重新平衡。
如果没有要插入的位置（找到了相似的元素，但是它们之间没有空闲单元），则需要摇晃辅助阵列，以便释放插入位置。 阵列的抖动正在重新平衡。
而且，重新平衡是
局部的或
完全的 。
本地再平衡
我们将根据需要移动任意数量的元素以释放插入点。 这种平衡的实现非常简单，您只需要从插入点找出最近的空单元格并使用它移动几个元素。
有细微差别。 例如，寻找最近空置地点的方法是什么？ 为了避免无法进行平移的情况（也就是说，如果在某些侧面上所有单元格都位于阵列的最边缘），可以将焦点放在插入点相对于阵列中间的位置。 如果需要在数组的左侧插入，则向右移动，如果在右侧-向左移动。 如果
ε≥2 ，则此方法消除了无法进行移位的情况（因为辅助阵列的一半有足够的空间容纳所有元素）。
在作者对该算法的解释中，暗示了局部重新平衡。
完全重新平衡
本地解决方案的一个有趣替代方法是完全重新平衡。 也就是说，在辅助数组中，移动所有可用元素，以使它们之间（几乎）有相同的空间。
我尝试了这两种方法，到目前为止，我发现通过局部重新平衡，该算法的工作速度比完整算法快1.5-2倍。 但是，仍然可以使用完全重新平衡。 例如，如果您必须过于频繁地进行局部重新平衡，则意味着在阵列中某些区域中积累了许多“血凝块”，从而阻碍了整个过程。 一次完整的重新平衡，可以让您一举摆脱所有本地拥堵。
让我们找出如何完全重新平衡。
首先，您需要计算可为辅助数组中的每个元素分配多少个最大单元。 应当记住，空单元格必须同时位于第一个和最后一个填充的单元格之前。 公式为：
M-可以分配给每个元素的像元数
NewSize-辅助数组的大小
Count-辅助数组中当前非空元素的数量该分数必须减小为整数值（即四舍五入）。 从公式中可以明显看出，已经有更多的元素转移到辅助数组中，我们可以为每个元素的邻域选择的单元越少。
知道了
M ，我们很容易获得辅助数组中每个非空元素在重新平衡完成后应位于的确切位置。
NewPos =数字×MNewPos-重新平衡后的新商品位置
Number-辅助数组中的非空元素是什么（1≤Number≤Count）
M-分配给每个元素的像元数新的职位是已知的，您能简单地将辅助数组中的非空元素分类出来并将它们转移到其他地方吗？ 哦，不，不要着急。 不仅需要转移元素，而且保持其顺序也很重要。 并且，由于二进制搜索和插入的结果，元素在重新平衡后可能位于应位于的位置的左侧和右侧。 在您要移动的地方，可能还有另一个元素也需要附加到某个地方。 此外，如果辅助阵列中的旧位置和新位置之间还有其他元素，则无法转移元素-否则这些元素会混合在一起，对于我们而言，不要混淆顺序非常重要。
因此，要重新平衡，仅经历通常的循环并仅将每个要素从一个口袋转移到另一个口袋是不够的。 仍然有必要使用递归。 如果某个元素无法移动到新位置（其他元素出现在其新旧位置之间），那么首先您需要（递归）找出这些不请自来的客人。 然后一切都会正确安排。
退化案例
对于大多数按插入排序的情况，最不利的情况是使用反向排序的数组。 ing，对图书馆员的分类也不例外。
元素趋向于辅助阵列的左边缘，结果空点很快用完。 您必须经常重新平衡阵列。
顺便说一下，如果我们采用几乎有序的数组（通过简单插入进行排序的最佳情况），那么我们会遇到相同的问题。 新到达的元素不会阻塞辅助阵列的左侧，但会阻塞右侧，这也会导致太频繁的重新平衡。
库排序可有效处理随机数据集。 部分排序（正向和反向）会损害速度性能。
算法复杂度
对于大量随机数据，该算法给出时间复杂度O（
n log
n ）。 一点都不差！
在正确选择系数
ε并成功实现二进制搜索的一组随机唯一（或大多数唯一）数据上，可以最小化甚至避免重新平衡的次数。 可以认为该算法具有最佳的时间复杂度O（
n ）。
大量重复的数据值以及有序（正序或逆序）子序列数组中的数据会导致辅助数组的频繁重新平衡，结果是在最不利的情况下时间复杂度降低到O
（n 2 ）。
当然，该算法的缺点是辅助数组需要O（
n ）个附加内存。
可能的改善方法
尽管该算法本身对随机数据具有指导意义和效率，但在过去的十五年中，很少有人对此感兴趣。
如果您通过请求“库排序”进行搜索，则会在英语Wikipedia上找到粗略的文章，作者的PDF（很少了解），并且很少重新发布这些微薄的信息。 另外，YouTube中有很好的可视化效果，主要是将主阵列和辅助阵列组合在一起的。 所有链接都在文章末尾。
搜索“库排序”更加有趣-在示例中，您将发现不同库中包含的不同排序，但是，这些算法与
真实的库排序无关。
还有一些需要改进的地方：
- 最佳系数ε的经验选择。
- 修改二进制搜索（考虑到通用算法的细节），以最有效地确定插入点。
- 最小化再平衡成本。
如果您对这些地方进行了润饰，那么也许图书馆的排序速度等于快速排序？
源代码
我没有准备用Python准备实现，PHP中有可用的版本。
基本算法function LibrarySort($arr) { global $arr_new;
我必须根据该方法的一般说明从头开始编写代码。 我没有看到接近快速排序的速度；我的库排序选项的排序速度比快速排序慢10到20倍。 但是，原因当然是我的实现过于粗糙，很多方面尚未考虑在内。
我想看看算法创建者的版本。 我今天写信给作者（并给他们链接到这个habrastatu的链接），他们会突然回答。 尽管...我记得，我曾尝试与Allen Beachich（
ABC排序 ）和Jason Morrison（
J排序 ）联系，但是结果和我在Sportloto中写的一样。
UPD Martin Farah-Colton回答我说他们从未执行过该实现：恐怕我们从未实现过该算法。
最主要的是想法：)算法特征
参考文献
图书馆排序
库排序算法可视化
插入排序为O（n log n）该算法的作者：
迈克尔·本德尔
马丁·法拉·科尔顿
米格尔·莫斯特罗（Miguel Mostiro）
系列文章：
排序已添加到AlgoLab。 因此，您可以尝试使用小型数据集。
在这种情况下，您可以确定辅助阵列比主阵列大多少倍。 要选择系数ε，您可以在带有“库排序”的单元格上单击鼠标右键，然后选择“更改注释”。 并在注释中，小心地将e的整数值设置为2到5。如果您输入其他值而不是这些数字，则将使用默认值= 2。
您也可以选择重新平衡的类型。 如果将local设置为1，则将使用本地重新平衡。 如果本地= 0-满。
并且，不要忘记在开始可视化之前为过程表设置最佳比例，否则辅助阵列将无法显示在屏幕上。