插入排序方案

Question

受到我的合并排序方案的启发，我想我应该尝试实现其他排序算法，从简单的排序(比如插入排序)开始，然后继续前进。所以，我们开始：

(define (insertion-sort lst (lt? <))
  (fold-right (lambda (item sorted)
                (let-values (((lhs rhs) (span! (cut lt? <> item) sorted)))
                  (append! lhs (cons item rhs))))
              '() lst))

使用Racket和Guile测试；需要SRFIs 1、11和26。(如果要将其用于Guile，则需要调整用于可选参数的语法。)

我在找什么

我希望得到对我的代码的批评，以获得更好的风格(从经验丰富的阴谋家的角度来看)和性能，并理解如下：

1. 插入排序是O(n平方)最坏的情况，显然还有更可扩展的排序算法。
2. 我试图使这成为一个纯功能的实现，这样您就可以在不调用未定义的行为的情况下传递一个文字列表数据。
   • sorted列表中的所有节点最终都是使用cons创建的，因此我可以在排序节点上安全地使用span!和append!，而不需要定义未定义的行为。

的事情我考虑过

1. 我最初是用左折叠而不是右折叠来实现的。然而，SRFI 1解释说，当左折叠版本由于更好的缓存局部性而需要反转时，使用右折叠通常更好。
   • 左折叠实现需要按反向顺序构建排序列表，以维护“快速(如果大部分已排序)”属性。

更新: coredump询问输出列表是否可以在可能的情况下与输入列表共享反单元格。这里有一个可能的实现；代码比最初的实现要长一些，所以这里也欢迎任何改进建议：

(define (insertion-sort lst (lt? <))
  (pair-fold-right (lambda (pair sorted)
                     (define item (car pair))
                     (if (and (eq? (cdr pair) sorted)
                              (or (null? sorted)
                                  (not (lt? (car sorted) item))))
                         pair
                         (let-values (((lhs rhs) (span (cut lt? <> item) sorted)))
                           (append! lhs (cons item rhs)))))
                   '() lst))

Answer 1

我不是一个经验丰富的阴谋家，我认为你的代码看起来很棒。我只有一句话。

您正在以纯功能的方式对列表进行排序，以避免更改输入中给出的列表。但我不确定你的意图是什么。数据共享，这是纯功能数据结构的优点之一(也许你不想共享反单元格，我也能理解)。

目前，在我看来，您不能共享任何子列表。您确实有机会在中间列表之间共享子列表，这要感谢span!和append!。但是，如果输入列表是(6 5 7 8 9)和排序<，则生成的列表(5 6 7 8 9)无法共享相同的子列表，即(7 8 9)，因为您使用cons构建了来自新列表()的结果(对任何误解表示歉意)。

您的实现的一个可能的改进是开始查找已经排序的最长子列表，并在此子列表的基础上构建结果列表。我不认为这与插入排序的定义相矛盾。缺点是，突变也是共享的，但这是一个设计决策(这就是我没有看到您是否有意地避免共享数据的地方)。

Answer 2

很小的一点：

变量名lst是，嗯，丑陋。

对于列表，我更喜欢xs (然后您可以在list xs中讨论元素x )。如果您有两个列表xs和ys，并且有x和y元素，那么您就知道这些元素来自何处。

另一个选择就是“L”。

Answer 3

一般性意见：

插入排序更适合向量，可以在不分配任何临时数据结构的情况下交换元素。

您的基于列表的解决方案是否是O(n^2)，或者额外的分配是否使其成为O(n^3)，这将是很有趣的。