LISP - 字符串排序

Lisp - 字符串和序列排序

Common Lisp 提供了一个强大的 sort 函数用于对序列进行排序。这个函数非常灵活，可以根据提供的谓词（predicate）函数对各种序列类型（如列表和向量）进行排序。在本章中，我们将深入探讨如何有效地对字符串进行排序。

sort 和 stable-sort 函数

主要的排序函数是 sort。它接收两个主要参数：要排序的 sequence（序列）和一个用于确定顺序的 predicate（谓词）函数。

重要提示： sort 是一个破坏性函数。它会就地修改原始序列。如果你需要保留原始序列，则必须对其副本进行排序。

;; 若要非破坏性地对列表进行排序，请对其副本进行排序。
(sort (copy-list original-list) #'<)

;; 若要非破坏性地对任何序列进行排序，请使用 copy-seq。
(sort (copy-seq original-sequence) #'<)

Common Lisp 还提供了 stable-sort 函数，其工作方式与 sort 相同，但它保证了被谓词视为相等的元素的相对顺序得以保留。

示例：不区分大小写的字符串排序

若要在不考虑大小写的情况下对字符串进行排序，可以使用 string-lessp 谓词。它会按字典序比较两个字符串，忽略大小写差异。

main.lisp

;; 定义一个要排序的字符串列表。
(defvar *fruits* '("banana" "Apple" "Orange" "cherry"))

;; 不区分大小写地对列表副本进行排序。
(let ((sorted-fruits (sort (copy-list *fruits*) #'string-lessp)))
  (format t "Original: ~a~%" *fruits*)
  (format t "Sorted (case-insensitive): ~a~%" sorted-fruits))

输出

执行代码后，将返回以下结果：

Original: ("banana" "Apple" "Orange" "cherry")
Sorted (case-insensitive): ("Apple" "banana" "cherry" "Orange")

示例：区分大小写的字符串排序

对于区分大小写的排序，请使用 string< 谓词。使用此谓词时，大写字母通常被视为“小于”小写字母。

main.lisp

;; 使用相同的蔬菜列表。
(defvar *fruits* '("banana" "Apple" "Orange" "cherry"))

;; 区分大小写地对副本进行排序。
(let ((sorted-fruits (sort (copy-list *fruits*) #'string<)))
  (format t "Case-Sensitive Sort: ~a~%" sorted-fruits))

;; 我们也来试试向量。
;; 请注意，输出将是一个向量：#(...)
(let ((fruit-vector (vector "banana" "Apple" "Orange" "cherry")))
    (format t "Sorted Vector: ~a~%" (sort fruit-vector #'string<)))

输出

执行代码后，输出将反映区分大小写的顺序：

Case-Sensitive Sort: ("Apple" "Orange" "banana" "cherry")
Sorted Vector: #("Apple" "Orange" "banana" "cherry")

排序的最佳实践

• 注意破坏性操作：始终注意 sort 会修改其参数。如果原始数据很重要，那么 (sort (copy-seq ...)) 将是你的好帮手。
• 选择正确的谓词：对于面向用户的不区分大小写的排序，请使用 string-lessp 和 string-greaterp。对于严格的、区分大小写的字典序排序，请使用 string< 和 string>。
• 考虑稳定性：如果相等项的原始相对顺序很重要，请使用 stable-sort 而不是 sort。