按数字和字符对列表进行排序

Question

我有 LISP 中的列表：

((1 b) (1 a) (2 D) (1 z) (1 t) (2 a) (3 n))

我必须先按数字排序，如果字符的字典序相同，输出应该是：

((1 a) (1 b) (1 t) (1 z) (2 a) (2 d) (3 n))

我试过对一个参数进行排序，然后对另一个参数进行排序，我该如何组合这两个函数？

;;(sort '((1 b) (1 a) (2 D) (1 z) (1 t) (2 a) (3 n)) #'< :key #'car )
;;(sort '((1 b) (1 a) (2 D) (1 z) (1 t) (2 a) (3 n)) #'string< :key #'second )

有没有更简单的方法？

谢谢

Answer 1

你基本上有两个选择：

定义两个元素(x0 y0)和(x1 y1)的比较函数，即returns T if:
- x0 < x1，或
- x0 和 x1 等价于 [*] 和 y0 <' y1.
您还可以通过定义接受测试和关键参数列表的高阶函数并将它们组合起来创建一个将它们全部应用于两个值的比较函数来概括此解决方案。

[*] 在一般情况下，当 < 是用户提供的比较时，等价被定义为既不是 a < b 也不是 b < a功能。
对列表进行一次排序以比较条目的各个第二个字段，然后对结果调用 stable-sort 以根据第一个字段排序：您必须从最不重要的字段开始（改变排序的应用顺序会改变结果）。例如：
```
((1 c) (2 b) (0 a) (1 b))
```
按第二个字段排序#'string<
```
((0 a) (1 b) (2 b) (1 c))
```
然后按第一个字段稳定排序#'<
```
((0 a) (1 b) (1 c) (2 b))    #### RES 1
```
先按第一个字段排序结果如下:
```
((0 a) (1 c) (1 b) (2 b))
```
然后（稳定地）到第二个：
```
((0 a) (1 b) (2 b) (1 c))    #### RES 2
```
通过调用stable-sort，当两个元素的第一个字段相等时，排序的稳定性保证它们将继续按第二个字段排序。如果要比较的字段较多，可以多次申请stable-sort。

小心，在 Common Lisp 中 sort 会改变输入。

Answer 2

正如 coredump 所说，因为您确实需要一个列表比较函数，所以一个不错的方法是做元事情：不要写一个，而是写一个函数来生成比较列表的函数。这是这样一个函数：

(defun make-list-comparator (&rest predicates)
  (labels ((tails< (l1t l2t pt)
             (let ((< (first pt))
                   (e1 (first l1t))
                   (e2 (first l2t)))
               (cond
                ((funcall < e1 e2) t)
                ((funcall < e2 e1) nil)
                ((and (null l1t) (null l2t) (null pt)) nil)
                ((or (null l1t) (null l2t) (null pt))
                 (error "crashed into the end"))
                (t (tails< (rest l1t) (rest l2t) (rest pt)))))))
    (lambda (l1 l2)
      (tails< l1 l2 predicates))))

现在

> (sort (copy-list '((1 b) (1 a) (2 D) (1 z) (1 t) (2 a) (1)))
        (make-list-comparator
         #'<
         (lambda (s1 s2)
           (string< (string s1) (string s2)))))
((1 a) (1 b) (1 t) (1 z) (2 a) (2 d) (3 n))

按数字和字符对列表进行排序

Sort a list by number and char

lisp

sorting

list

common-lisp