Get best of the week

顺利排序


我们继续沉浸在各种各样的事物中。

今天，我们将分析一种优雅的排序方法，该方法使用基于Leonardo数的特殊堆。

许多人都听说过这种排序，但是很少有人确切地知道它是如何工作的。今天，我们将看到其中没有什么复杂的内容。 该方法由传奇的Edsger Dijkstra发明。除了算法理论上最杰出的成就外，他还是这样机智的声明的作者：“以前学习过Basic的学生，几乎不可能教好编程。作为潜在的程序员，他们经历了不可逆转的智力退化。” 我希望不要轻信文章中的动画是使用VBA创建的:-)







EDISON软件-网络开发
EDISON.

, Android iOS.

! ;-)

堆排序本身非常好，因为无论数据如何，堆时间复杂度均为O（n log n）。为了不表示数组，堆排序的复杂性永远不会降低到O（n 2），这可能发生在例如快速排序中。硬币的另一面是不能加快二进制堆的排序，也不能期望O（n）的复杂性（但是在某些条件下相同的快速排序可以实现此类指标）。

总的来说，议程上存在一个问题：是否可以进行设计，以便一方面使按堆排序的时间复杂度不低于O（n log n），但是在有利的情况下（特别是如果处理了几乎排序的数组）增加到O（n）？

Edsger Dijkstra亲自亲自解决了这个问题，他发现是的，有可能。

假定阅读本文的人通常了解按堆进行排序的方式，他们知道什么是分类树以及为什么需要进行筛选。如果某人在此知识上有不足之处，那么在继续阅读之前，建议您阅读上一篇文章。

二进制堆有什么问题


让我们看一下堆排序如何对几乎有序的数组进行排序，并了解为什么该算法不能更快地处理此类传入数据。


单击动画以转至文章“通过n金字塔排序”

，引起您注意的第一件事是，在筛选时，最大值会不断推入堆的根，这与数组的第一个元素相对应。如果输入数组几乎是有序的，那么对于算法来说，这只会增加一点工作。较小的元素仍然会首先从树上掉下来，即靠近数组的末尾，而不是数组的开始。

第二个减慢因素（不是很明显）是标准二进制堆本身始终是平衡树。对于最初订购的数据，这起着负面作用。如果原始数组中有随机数据，则它们将均匀地分布在平衡树中，并且多次筛选会以大约相同的次数遍历所有分支。对于几乎有序的数据，最好使用不平衡的树-在这种情况下，与树的较长分支相对应的数组部分数据的处理频率将比其他数据少。

莱昂纳多数


为了解决这两个问题，Dijkstra建议使用基于Leonardo数的特殊二进制堆。

莱昂纳多数几乎与斐波那契数类似，但只有更好。
递归给出一系列莱昂纳多数：

L 0 = 1
L 1 = 1
L n = L n-1 + L n-2 + 1

前20个莱昂纳多数：
1、1、3、5、9、15、25、41、67 ，109，177，287，465，753，1219，1973，3193，5167，8361，13529

绝对可以将任何整数表示为具有不同序列号的莱昂纳多数字之和。

在我们的案例中，这非常有用。n的数组元素不能总是表示为Leonardo的单个堆（如果n不是Leonardo数）。但是，然后，任何阵列都可以始终分为几个子阵列，分别对应于不同数量的莱昂纳多（Leonardo），即 成为不同顺序的堆。

这是第21个元素的数组的示例，该数组由三个Leonard堆组成。在每个堆中，节点数对应于任何数量的莱昂纳多。


重要注意事项：

  1. 每个Leonardov堆都是不平衡的二叉树。
  2. 每个堆的根是对应子数组的最后一个（而不是第一个，如常规二进制堆中的第一个）元素。
  3. 具有所有后代的任何节点也是较小顺序的伦纳德堆。

建造和拆除堆


在莱昂纳多数的递推公式中，

L n = L n-1 + L n-2 +1

对最后的单位非常满意。

这就是为什么。假设我们在数组中有两个相邻的子数组，它们对应于建立在两个相邻的莱昂纳多数上的堆。在这些子数组之后立即使用元素，可以将这些子数组组合为一个公共堆，该堆对应于下一个伦纳德数。



遍历数组中的元素，我们构建了一堆伦纳德堆。如果使用元素，则可以合并前面的两个堆（只有当两个前面的堆对应于两个连续的莱昂纳多数时才有可能），然后合并。如果不可能合并（前两个堆不对应于两个连续的莱昂纳多数），那么当前元素将简单地形成一个新堆，其中一个元素与第一个（或第二个，如果使用第一个）Leonardo数相对应。

在算法的第二阶段，发生反向过程-我们解析堆。如果我们删除堆中的根，则将得到两个较小的堆，它们对应于前面的两个莱昂纳多数。可以这样做是因为：

L n -1 = L n-1+ L n-2

在斐波那契数中没有这样的有用单位，因此我们不使用斐波那契堆。

平滑排序::平滑排序


最终算法：

  • I.从数组创建一堆伦纳德堆，每个堆都是一棵排序树。
    • I.1。从左到右遍历数组的元素。
    • II.1。我们检查是否可以使用当前元素来合并伦纳德堆的现有堆中最左边的两个堆：
      • II.1.a．如果是，则将最左边的两个堆合并为一个，当前元素成为该堆的根，对合并的堆进行筛选。
      • II.1.b. 如果不是，则将当前元素作为新堆（到目前为止，由一个节点组成）添加到Leonard堆的现有堆中。
  • II. , :
    • II.1. . , .
    • II.2. ( ) ( ).
    • II.3. , . .
    • II.4. ( ), .
    • II.5。将最大元素移到末尾后，数组的排序部分增加，而未排序部分减少。对数组的其余未排序部分重复步骤II.1-II.4。



Python实现示例


import random

def smoothsort(lst):

    #    
    leo_nums = leonardo_numbers(len(lst))


    #       
    heap = []

    #   
    #       
    #       
    for i in range(len(lst)):
        if len(heap) >= 2 and heap[-2] == heap[-1] + 1:
            heap.pop()
            heap[-1] += 1
        else:
            if len(heap) >= 1 and heap[-1] == 1:
                heap.append(0)
            else:
                heap.append(1)
        restore_heap(lst, i, heap, leo_nums)

    #  
    for i in reversed(range(len(lst))):
        if heap[-1] < 2:
            heap.pop()
        else:
            k = heap.pop()
            t_r, k_r, t_l, k_l = get_child_trees(i, k, leo_nums)
            heap.append(k_l)
            restore_heap(lst, t_l, heap, leo_nums)
            heap.append(k_r)
            restore_heap(lst, t_r, heap, leo_nums)

#   ,     
def leonardo_numbers(hi):

    a, b = 1, 1
    numbers = []
    while a <= hi:
        numbers.append(a)
        a, b = b, a + b + 1
    return numbers

#        
def restore_heap(lst, i, heap, leo_nums):
    
    #      
    
    current = len(heap) - 1
    k = heap[current]

    while current > 0:
        j = i - leo_nums[k]
        if (lst[j] > lst[i] and
            (k < 2 or lst[j] > lst[i-1] and lst[j] > lst[i-2])):
            lst[i], lst[j] = lst[j], lst[i]
            i = j
            current -= 1
            k = heap[current]
        else:
            break

    # 
    
    while k >= 2:
        t_r, k_r, t_l, k_l = get_child_trees(i, k, leo_nums)
        if lst[i] < lst[t_r] or lst[i] < lst[t_l]:
            if lst[t_r] > lst[t_l]:
                lst[i], lst[t_r] = lst[t_r], lst[i]
                i, k = t_r, k_r
            else:
                lst[i], lst[t_l] = lst[t_l], lst[i]
                i, k = t_l, k_l
        else:
            break

#         ,
#     
def get_child_trees(i, k, leo_nums):

    t_r, k_r = i - 1, k - 2
    t_l, k_l = t_r - leo_nums[k_r], k - 1
    return t_r, k_r, t_l, k_l

#  
def main(n):
    lst = list(range(n))
    random.shuffle(lst)
    print(lst)
    smoothsort(lst)
    print(lst)

时间复杂度


如果我们将几乎有序的数组作为输入，那么可视化效果将说明为什么处理这样一个数组要快得多的原因。



节省仅是由于筛分。在几乎有序的数据中，筛分沉入了树的浅层，包括在第二阶段逐渐解散堆之后。在最初的随机数据中，筛选更为昂贵，因为筛选通常会将其堆放到最后一层。

让我们估算总时间复杂度。

在第一阶段，我们遍历n个元素，将其添加到左侧已经存在的堆中。在O（1）中绕过添加到堆本身，但是对于堆，您需要进行筛选。在有序数据中，对于添加到堆中的一个元素，浅层筛选的成本通常为O（1）。在无序数据中，每个加法的筛分成本为O（log n），由于随机性的结果，筛选必须经常遍历树的最底层。

因此，在第一阶段，最佳时间复杂度是：
对于几乎有序的数据-O（n），
对于随机数据-O（n log n）。

对于第二阶段，情况类似。交换下一个最大值时，您再次需要在堆的根部筛选堆。而且有序和无序数据的筛选指标将有所不同。

在第二阶段，最佳时间复杂度与第一阶段相同：
对于几乎有序的数据-O（n），
对于随机数据-O（n log n）。

在第一和第二阶段增加时间复杂度：
对于几乎有序的数据-O（2 n）= O（n），
对于随机数据-O（2 n log n）= O（n log n）。

通常，平滑排序的最差时间和平均时间复杂度为O（n log n）。
Dijkstra在他的计算中（我不会让您感到厌烦）证明，与输入数据的排序顺序相比，最佳复杂度平滑地趋于O（n）。因此，名称-平滑排序。

额外的内存复杂性


要将数据分解为一堆伦纳德堆，您只需要确切记住每一步涉及哪些伦纳多数即可。知道了这些数字，堆本身就按照算法进行了对齐。这个数列增长非常快，因此即使对于大型数组，您也将需要很少的伦纳德数集。

二项式堆排序::二项式堆排序


有一个与我们整理出来的树结构非常相似的树结构- 二项式堆。这也是一堆大小不同的堆，每个堆中的节点数是2的幂。可以将任何数量的元素的任何数组扩展到此堆中，因为任何自然数都可以分解为不同程度的二之和。

原则上，您可以基于二项式进行平滑排序：



会更快吗？几乎不。二项式堆不是二进制的，在上一篇文章中我们发现增加后代的数量并不会加速，但会降低屏幕速度。此外，您会注意到二项式堆具有更长的分支，这就是为什么数组的相邻有序区域相互连接的速度会稍微慢一些的原因。

不知道Dijkstra二项式堆是否通常被认为是其算法的可能基础。尽管如此，Leonardov堆可能更理想。

下一个系列预告片


但是，即使二项式堆不是平滑排序的最佳选择，也不应完全丢弃它。

如果对二项式树稍加修改，并使用完全不同的（非常大胆的）想法来绕过它，我们将得到一个具有其优势的原始有效算法。下次我们要谈什么？


单击动画以转到具有下一个按堆排序的文章。

参考文献


光滑 / 光滑

莱昂纳多数，二项式堆 / 二项式堆

系列文章：



今天的平滑排序已添加到AlgoLab应用中。以及奖金-并按二项式排序。所以谁想亲自驱动堆上的数据-用宏更新excel文件。

More articles:


All Articles