recursion - 订购一对列表

Question

谁能给我一个写得很好的实现，说明如何使用辅助函数（基于每对汽车的价值）在方案中订购一对列表？例如，'((3 2) (1 2) (8 4) (0 6)) 应按 '((0 6) (1 2) (3 2) (8 4)) 排序。这似乎是一件很简单的事情，但出于某种原因，我画了一个空白。

Answer 1

好吧，首先你可以使用你最喜欢的内置sort例程，并指定它是按 排序的car，例如在 Common LISP 中

(sort ls #'< :key #'car)

如果您的方案缺乏指定的能力key，您可以通过比较过程来模拟这一点

(sort ls (lambda (a b) (< (car a) (car b))))

其次，如果你想重新实现它，你可以使用合并排序的方法：将你的列表分解成单调递增的部分，然后将它们成对合并，直到只剩下一个。在哈斯克尔，

mergesortBy f xs 
   | null xs       = []
   | [s] <- until (null.tail) (pairwise (mergeBy f)) (breakup xs) = s
pairwise g (a:b:t) = g a b : pairwise g t
pairwise _ t       = t
breakup xs         = [[x] | x <- xs] -- a list of (a list of x) for x in xs

由于这些部分是单调递增的（或至少是非递减的），mergeBy因此可以很容易地实现。

当然，“编写良好”的实现将用初始阶段替换breakup此处显示的基本实现，该初始阶段将尝试制作更长的块，在旅途中保留非减少和反转非增加块（Haskell 示例在这里） . pairwise并且mergeBy（甚至可能breakup）函数必须融合为一个，以使整体实现更加在线，因为 Scheme（通常）是一种严格（即非惰性）语言。您可以在要合并的内部列表中使用显式暂停，以便从排序列表中取出一些第一个元素是 O(n) 操作。