LISP - 排序序列

现代 Lisp：序列排序

排序是编程中一项基本操作。Common Lisp 提供了一个强大且多功能的 sort 函数，它可以对任何序列（sequence，包括列表list和向量vector）进行操作。理解如何有效使用 sort 对于编写高效、整洁的 Lisp 代码至关重要。

The sort 和 stable-sort 函数

重要提示：破坏性操作

关于 sort 最重要的一点是它是破坏性的（destructive）。它会就地修改原始序列以节省内存。如果你需要保留原始序列，则必须对一个副本进行排序。

;; 要非破坏性地排序列表，请使用 COPY-LIST
(sort (copy-list original-list) #'<)

;; 要非破坏性地排序任何序列（列表或向量），请使用 COPY-SEQ
(sort (copy-seq original-sequence) #'<)

语法

(sort sequence predicate &key key)

• sequence：要排序的列表或向量。
• predicate：一个接受两个参数的函数，如果第一个参数“小于”第二个参数，则返回真。常用的谓词有用于数字的 < 和用于字符串的 string<。
• :key (可选)：一个接受一个参数的函数，在传递给谓词之前应用于每个元素。这用于根据特定属性对复杂对象进行排序。

示例 1：排序简单的数字列表

这里，我们以升序排序一个数字列表。请注意，我们使用 copy-list 来保持原始列表不变。

main.lisp

(defparameter *numbers* '(4 3 7 2 1 8 3))

;; 排序列表的副本，保持 *numbers* 不变。
(defparameter *sorted-numbers* (sort (copy-list *numbers*) #'<))

(format t "Original: ~a~%" *numbers*)
(format t "Sorted:   ~a~%" *sorted-numbers*)

输出

原始: (4 3 7 2 1 8 3)
排序后:   (1 2 3 3 4 7 8)

示例 2：使用 stable-sort 排序字符串向量

stable-sort 类似于 sort，但它保证了被谓词视为相等的元素的相对顺序得以保留。这在某些算法中可能很重要。这里我们使用 string-lessp 进行不区分大小写的比较。

main.lisp

(defparameter *strings* #("Lisp" "Python" "lisp" "Java"))

;; 使用 string-lessp 进行不区分大小写的排序。
(defparameter *sorted-strings*
  (stable-sort (copy-seq *strings*) #'string-lessp))

(format t "Original: ~a~%" *strings*)
(format t "Sorted:   ~a~%" *sorted-strings*)
;; 注意：输出中 "Lisp" 出现在 "lisp" 之前，因为 stable-sort
;; 保留了它们原始的相对顺序。

输出

原始: #("Lisp" "Python" "lisp" "Java")
排序后:   #("Java" "Lisp" "lisp" "Python")

示例 3：使用 :key 排序对象列表

:key 参数非常强大。让我们根据年龄（第二个元素）对一个子列表（表示人物及其年龄）进行排序。

main.lisp

(defparameter *data* '(("Alice" 30) ("Bob" 25) ("Charlie" 35)))

;; :key #'second 告诉 sort 在使用 < 进行比较之前，提取每个子列表的第二个元素。
(defparameter *sorted-data* (sort (copy-list *data*) #'< :key #'second))

(format t "Sorted by age: ~a~%" *sorted-data*)

输出

按年龄排序: (("Bob" 25) ("Alice" 30) ("Charlie" 35))

常见陷阱与最佳实践

• 修改字面量： 切勿尝试排序带引号的字面量，例如 (sort '(3 2 1) #'<)。这会尝试修改常量数据并导致未定义行为，从而可能使程序崩溃。始终对新鲜或复制的序列进行排序。
• 性能： 由于更好的内存局部性，排序向量通常比排序列表更快。如果性能至关重要，请考虑在排序前将列表转换为向量：(coerce my-list 'vector)。