LISP - 列表排序

Lisp - 序列排序

Common Lisp 提供了强大且通用的函数，用于对列表（list）和向量（vector）等序列进行排序。主要函数是 sort 和 stable-sort。理解它们的行为，特别是它们的破坏性（destructive）特性，是正确使用它们的关键。

sort 和 stable-sort：破坏性排序器

无论是 sort 还是 stable-sort，都会直接修改传递给它们的序列。这被称为破坏性操作。它之所以高效，是因为避免了分配新的序列，但这也意味着您的原始数据将被更改。

语法是：(sort sequence predicate &key key)

• sequence：要排序的列表或向量。
• predicate：一个接受两个参数的函数，如果第一个参数应该排在第二个参数之前，则返回真（true）。常用谓词包括数字的 #< 和字符串的 string<。
• stable-sort vs sort：stable-sort 保证谓词认为相等的元素的相对顺序得以保留。sort 不提供此类保证。

示例：破坏性排序

(let ((numbers '(4 3 7 2 1 8 3)))
  (print (format nil "Original list: ~a" numbers))

  ;; 就地排序列表。
  (sort numbers #'<)

  (print (format nil "List after sort: ~a" numbers)))

;; 输出：
;; "Original list: (4 3 7 2 1 8 3)"
;; "List after sort: (1 2 3 3 4 7 8)"

非破坏性排序

要在不修改原始序列的情况下对其进行排序，您必须首先创建一个副本。通用的方法是使用 copy-seq。

(let ((original-data '("Apple" "Coconut" "Banana" "Orange")))

  ;; 创建一个已排序的副本，保持原始数据不变。
  (let ((sorted-data (sort (copy-seq original-data) #'string<)))
    (print (format nil "Original: ~a" original-data))
    (print (format nil "Sorted Copy: ~a" sorted-data)))
)

;; 输出：
;; "Original: (\"Apple\" \"Coconut\" \"Banana\" \"Orange\")"
;; "Sorted Copy: (\"Apple\" \"Banana\" \"Coconut\" \"Orange\")"

使用 :key 进行高级排序

:key 参数允许您指定一个函数，该函数会在每个元素传递给谓词之前对其进行调用。这对于排序复杂数据结构至关重要。

示例：排序对象列表

让我们定义一个简单的产品结构，并按价格对产品列表进行排序。

;; 定义一个简单的产品结构
(defstruct product name price)

(let ((inventory (list (make-product :name "Laptop" :price 1200)
                     (make-product :name "Mouse" :price 25)
                     (make-product :name "Keyboard" :price 75))))

  ;; 按价格排序（从低到高）
  (let ((sorted-inventory (sort (copy-list inventory) #'< :key #'product-price)))
    (loop for p in sorted-inventory
          do (format t "~a: $~a~%" (product-name p) (product-price p)))))

;; 输出：
;; Mouse: $25
;; Keyboard: $75
;; Laptop: $1200

按多重条件排序

要按主键排序，然后对于主键相同的项按次要键排序，您应该使用 stable-sort。技巧是首先按最不重要的键进行排序，然后按最重要的键进行排序。

示例：先按年龄，再按姓名排序

(defstruct person name age)

(let ((people (list (make-person :name "Bob" :age 30)
                  (make-person :name "Alice" :age 25)
                  (make-person :name "Charlie" :age 30))))

  ;; 要先按年龄（主键）再按姓名（次键）排序，我们执行两次稳定排序：

  ;; 1. 首先按次要键（姓名）排序。
  (setf people (stable-sort people #'string< :key #'person-name))
  ;; -> people is now ((#S(PERSON :NAME "Alice" :AGE 25)) (#S(PERSON :NAME "Bob" :AGE 30)) (#S(PERSON :NAME "Charlie" :AGE 30)))

  ;; 2. 按主键（年龄）对结果进行排序。
  ;; 因为 stable-sort 保留了相等元素的原始相对顺序，
  ;; 所以 Bob 和 Charlie（都 30 岁）将保持其字母顺序。
  (setf people (stable-sort people #'< :key #'person-age))

  (loop for p in people do (print p)))

;; 最终输出：
;; #S(PERSON :NAME "Alice" :AGE 25)
;; #S(PERSON :NAME "Bob" :AGE 30)
;; #S(PERSON :NAME "Charlie" :AGE 30)