<TMU|<tuple|1.0.5|1.2.9.7>>

<style|<tuple|generic|chinese|goldfish|literate|reduced-margins>>

<\body>
  <\hide-preamble>
    <assign|r7rs|<flag|R7RS|dark cyan>>

    <assign|srfi|<flag|SRFI|dark red>>

    <assign|font|math=Latin Modern Math,cjk=Noto CJK SC,CMU>
  </hide-preamble>

  <chapter|(liii sort)>

  <section|许可证>

  <\goldfish-chunk|goldfish/liii/sort.scm|false|true>
    ;

    ; Copyright (C) 2024 The Goldfish Scheme Authors

    ;

    ; Licensed under the Apache License, Version 2.0 (the "License");

    ; you may not use this file except in compliance with the License.

    ; You may obtain a copy of the License at

    ;

    ; http://www.apache.org/licenses/LICENSE-2.0

    ;

    ; Unless required by applicable law or agreed to in writing, software

    ; distributed under the License is distributed on an "AS IS" BASIS, WITHOUT

    ; WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the

    ; License for the specific language governing permissions and limitations

    ; under the License.

    ;

    \;
  </goldfish-chunk>

  <\goldfish-chunk|goldfish/srfi/srfi-132.scm|false|true>
    ;

    ; Copyright (C) 2024 The Goldfish Scheme Authors

    ;

    ; Licensed under the Apache License, Version 2.0 (the "License");

    ; you may not use this file except in compliance with the License.

    ; You may obtain a copy of the License at

    ;

    ; http://www.apache.org/licenses/LICENSE-2.0

    ;

    ; Unless required by applicable law or agreed to in writing, software

    ; distributed under the License is distributed on an "AS IS" BASIS, WITHOUT

    ; WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the

    ; License for the specific language governing permissions and limitations

    ; under the License.

    ;

    \;
  </goldfish-chunk>

  <\goldfish-chunk|tests/goldfish/liii/sort-test.scm|false|true>
    ;

    ; Copyright (C) 2024 The Goldfish Scheme Authors

    ;

    ; Licensed under the Apache License, Version 2.0 (the "License");

    ; you may not use this file except in compliance with the License.

    ; You may obtain a copy of the License at

    ;

    ; http://www.apache.org/licenses/LICENSE-2.0

    ;

    ; Unless required by applicable law or agreed to in writing, software

    ; distributed under the License is distributed on an "AS IS" BASIS, WITHOUT

    ; WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the

    ; License for the specific language governing permissions and limitations

    ; under the License.

    ;

    \;
  </goldfish-chunk>

  <section|接口>

  <\goldfish-chunk|goldfish/liii/sort.scm|true|false>
    (define-library (liii sort)

    (export list-sorted? vector-sorted?

    \ \ \ \ \ \ \ \ list-merge \ list-sort \ list-stable-sort \ vector-merge \ vector-sort \ vector-stable-sort

    \ \ \ \ \ \ \ \ list-merge! list-sort! list-stable-sort! vector-merge! vector-sort! vector-stable-sort!)

    (import (srfi srfi-132)))

    \;
  </goldfish-chunk>

  <\goldfish-chunk|goldfish/srfi/srfi-132.scm|true|true>
    (define-library (srfi srfi-132)

    (export list-sorted? vector-sorted?

    \ \ \ \ \ \ \ \ list-merge \ list-sort \ list-stable-sort \ vector-merge \ vector-sort \ vector-stable-sort

    \ \ \ \ \ \ \ \ list-merge! list-sort! list-stable-sort! vector-merge! vector-sort! vector-stable-sort!)

    (import (liii list)

    \ \ \ \ \ \ \ \ (liii error)

    \ \ \ \ \ \ \ \ (scheme case-lambda))

    (begin

    \;
  </goldfish-chunk>

  <\section>
    实现
  </section>

  <subsection|list-sorted?, vector-sorted?>

  检查列表/向量是否按比较函数 less-p 排序。

  list-sorted?

  <\indent>
    检查列表 <code*|lis> 是否已按比较函数 <code*|less-p> 排序。如果列表已排序，返回 <code*|#t>，否则返回 <code*|#f>。
  </indent>

  vector-sorted?

  <\indent>
    检查向量 <code*|v> 是否已按比较函数 <code*|less-p> 排序。如果向量已排序，返回 <code*|#t>，否则返回 <code*|#f>。支持可选参数 <code*|start> 和 <code*|end>，用于指定检查的范围。
  </indent>

  <\scm-chunk|goldfish/srfi/srfi-132.scm|true|true>
    \;

    (define (list-sorted? less-p lis)

    \ \ (if (null? lis)

    \ \ \ \ #t

    \ \ \ \ (do ((first lis (cdr first))

    \ \ \ \ \ \ \ \ \ \ (second (cdr lis) (cdr second))

    \ \ \ \ \ \ \ \ \ \ (res #t (not (less-p (car second) (car first)))))

    \ \ \ \ \ \ ((or (null? second) (not res)) res))))

    \;

    (define vector-sorted?

    \ \ (case-lambda

    \ \ \ \ ((less-p v) (vector-sorted? less-p v 0 (vector-length v)))

    \ \ \ \ ((less-p v start) (vector-sorted? less-p v start (vector-length v)))

    \ \ \ \ ((less-p v start end)

    \ \ \ \ \ \ (if (or (\<less\> start 0) (\<gtr\> end (vector-length v)) (\<gtr\> start end))

    \ \ \ \ \ \ \ \ (raise "Invalid start or end parameters") ; 使用 raise 抛出错误

    \ \ \ \ \ \ \ \ (let loop ((i start))

    \ \ \ \ \ \ \ \ \ \ (if (\<gtr\>= i (- end 1))

    \ \ \ \ \ \ \ \ \ \ \ \ #t

    \ \ \ \ \ \ \ \ \ \ \ \ (if (less-p (vector-ref v (+ i 1)) (vector-ref v i))

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ #f

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ (loop (+ i 1)))))))))

    \;
  </scm-chunk>

  <subsection|list-merge, list-merge!, list-sort, list-stable-sort>

  归并排序。需要注意 <verbatim|list-sort!> 不必修改原 list，但 <verbatim|vector-sort!> 要保证修改原 vector。

  list-merge

  <\indent>
    非破坏性合并。合并两个已排序的列表，返回一个新的已排序列表。
  </indent>

  list-merge!

  <\indent>
    破坏性合并。合并两个已排序的列表，并直接修改 <code*|lis1> 和 <code*|lis2> 的 <code*|cdr> 指针，返回合并后的列表。使用 set-cdr! 进行原地操作，适用于内存敏感场景。
  </indent>

  list-stable-sort

  <\indent>
    非破坏性归并排序。对列表进行稳定排序（相等元素相对顺序保持不变），返回一个新的已排序列表。
  </indent>

  list-sort

  <\indent>
    非破坏性快速排序。对列表进行不稳定排序，返回一个新的一排序列表。速度快但是牺牲稳定性。
  </indent>

  list-sort!

  <\indent>
    破坏性快速排序。对列表进行不稳定排序，原地进行操作，返回排序后的列表。
  </indent>

  list-stable-sort!

  <\indent>
    破坏性归并排序。对列表进行稳定排序，原地进行操作，返回排序后的列表。
  </indent>

  <\scm-chunk|goldfish/srfi/srfi-132.scm|true|true>
    (define (list-merge less-p lis1 lis2)

    \ \ (let loop

    \ \ \ \ ((res '())

    \ \ \ \ \ \ (lis1 lis1)

    \ \ \ \ \ \ (lis2 lis2))

    \ \ \ \ (cond

    \ \ \ \ \ \ ((and (null? lis1) (null? lis2)) (reverse res))

    \ \ \ \ \ \ ((null? lis1) (loop (cons (car lis2) res) lis1 (cdr lis2)))

    \ \ \ \ \ \ ((null? lis2) (loop (cons (car lis1) res) lis2 (cdr lis1)))

    \ \ \ \ \ \ ((less-p (car lis2) (car lis1)) (loop (cons (car lis2) res) lis1 (cdr lis2)))

    \ \ \ \ \ \ (else (loop (cons (car lis1) res) (cdr lis1) lis2)))))

    \;

    (define list-merge!

    \ \ (lambda (less-p lis1 lis2)

    \ \ \ \ (define (merge! left right prev)

    \ \ \ \ \ \ (let loop ((left left) (right right) (prev prev))

    \ \ \ \ \ \ \ \ (cond

    \ \ \ \ \ \ \ \ \ \ ((null? left) (set-cdr! prev right))

    \ \ \ \ \ \ \ \ \ \ ((null? right) (set-cdr! prev left))

    \ \ \ \ \ \ \ \ \ \ ((less-p (car left) (car right))

    \ \ \ \ \ \ \ \ \ \ \ \ (set-cdr! prev left)

    \ \ \ \ \ \ \ \ \ \ \ \ (loop (cdr left) right left))

    \ \ \ \ \ \ \ \ \ \ (else

    \ \ \ \ \ \ \ \ \ \ \ \ (set-cdr! prev right)

    \ \ \ \ \ \ \ \ \ \ \ \ (loop left (cdr right) right)))))

    \ \ \ \ (let ((dummy (cons '() '())))

    \ \ \ \ \ \ (merge! lis1 lis2 dummy)

    \ \ \ \ \ \ (cdr dummy))))

    \;

    (define (list-stable-sort less-p lis)

    \ \ (define (sort l r)

    \ \ \ \ (cond

    \ \ \ \ \ \ ((= l r) '())

    \ \ \ \ \ \ ((= (+ l 1) r) (list (list-ref lis l)))

    \ \ \ \ \ \ (else

    \ \ \ \ \ \ \ \ (let* ((mid (quotient (+ l r) 2))

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (l-sorted (sort l mid))

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (r-sorted (sort mid r)))

    \ \ \ \ \ \ \ \ \ \ (list-merge less-p l-sorted r-sorted)))))

    \ \ (sort 0 (length lis)))

    \;

    (define (list-sort less-p lis)

    \ \ (if (or (null? lis) (null? (cdr lis)))

    \ \ \ \ \ \ lis

    \ \ \ \ \ \ (let ((pivot (car lis))

    \ \ \ \ \ \ \ \ \ \ \ \ (rest (cdr lis)))

    \ \ \ \ \ \ \ \ (let ((smaller (filter (lambda (x) (less-p x pivot)) rest))

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ (larger (filter (lambda (x) (not (less-p x pivot))) rest)))

    \ \ \ \ \ \ \ \ \ \ (append (list-sort less-p smaller)

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (list pivot)

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (list-sort less-p larger))))))

    \;

    (define (list-sort! less-p lst)

    \ \ ;; 辅助函数：返回列表的最后一个元素

    \ \ (define (last-pair lst)

    \ \ \ \ (if (null? (cdr lst))

    \ \ \ \ \ \ \ \ lst

    \ \ \ \ \ \ \ \ (last-pair (cdr lst))))

    \ \ ;; 辅助函数：将列表分成小于和大于 pivot 的部分

    \ \ (define (partition! lst pivot less-p)

    \ \ \ \ (let loop ((lst lst) (less '()) (greater '()))

    \ \ \ \ \ \ (cond

    \ \ \ \ \ \ \ \ ((null? lst) (values (reverse less) (reverse greater))) \ ;; 返回小于和大于部分

    \ \ \ \ \ \ \ \ ((less-p (car lst) pivot)

    \ \ \ \ \ \ \ \ \ \ (loop (cdr lst) (cons (car lst) less) greater))

    \ \ \ \ \ \ \ \ (else

    \ \ \ \ \ \ \ \ \ \ (loop (cdr lst) less (cons (car lst) greater))))))

    \ \ ;; 排序函数：原地排序

    \ \ (if (or (null? lst) (null? (cdr lst))) \ ;; 如果列表为空或只有一个元素，已经排序好

    \ \ \ \ \ \ lst

    \ \ \ \ \ \ (let* ((pivot (car lst)))

    \ \ \ \ \ \ \ \ (call-with-values\ 

    \ \ \ \ \ \ \ \ \ \ (lambda () (partition! (cdr lst) pivot less-p)) \ ;; 调用 partition 并返回小于和大于部分

    \ \ \ \ \ \ \ \ \ \ (lambda (less greater)

    \ \ \ \ \ \ \ \ \ \ \ \ ;; 对小于和大于部分递归排序

    \ \ \ \ \ \ \ \ \ \ \ \ (let ((sorted-less (list-sort! less-p less))

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (sorted-greater (list-sort! less-p greater)))

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ ;; 如果 sorted-less 是空，直接返回 sorted-greater

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ (if (null? sorted-less)

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ sorted-greater

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (begin

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ;; 原地连接两个部分和 pivot

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (set-cdr! (last-pair sorted-less) (cons pivot sorted-greater))

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ sorted-less)))))))) \ ;; 返回排序后的列表

    \;

    (define list-stable-sort!

    \ \ (lambda (less-p lis)

    \ \ \ \ (define (split! lis)

    \ \ \ \ \ \ (let loop ((slow lis) (fast (cdr lis)))

    \ \ \ \ \ \ \ \ (if (or (null? fast) (null? (cdr fast)))

    \ \ \ \ \ \ \ \ \ \ \ \ (let ((mid (cdr slow)))

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ (set-cdr! slow '())

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ (values lis mid))

    \ \ \ \ \ \ \ \ \ \ \ \ (loop (cdr slow) (cddr fast)))))

    \ \ \ \ (if (or (null? lis) (null? (cdr lis)))

    \ \ \ \ \ \ \ \ lis

    \ \ \ \ \ \ \ \ (let-values (((left right) (split! lis)))

    \ \ \ \ \ \ \ \ \ \ (list-merge! less-p

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (list-stable-sort! less-p left)

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (list-stable-sort! less-p right))))))

    \;
  </scm-chunk>

  <subsection|vector-merge, vector-sort, vector-stable-sort>

  无副作用时调用 list 相关函数实现。原地排序尚未实现。

  <\scm-chunk|goldfish/srfi/srfi-132.scm|true|true>
    (define vector-stable-sort

    \ \ (case-lambda

    \ \ \ \ ((less-p v)

    \ \ \ \ \ \ (list-\<gtr\>vector (list-stable-sort less-p (vector-\<gtr\>list v))))

    \ \ \ \ ((less-p v start)

    \ \ \ \ \ \ (list-\<gtr\>vector (list-stable-sort less-p (subvector-\<gtr\>list v start (vector-length v)))))

    \ \ \ \ ((less-p v start end)

    \ \ \ \ \ \ (list-\<gtr\>vector (list-stable-sort less-p (subvector-\<gtr\>list v start end))))))

    \;

    (define vector-sort vector-stable-sort)

    \;

    (define (vector-sort! . r) (???))

    \;

    (define (vector-stable-sort! . r) (???))

    \;

    (define (subvector-\<gtr\>list v start end)

    \ \ (do ((r '() (cons (vector-ref v p) r))

    \ \ \ \ \ \ \ \ (p start (+ 1 p)))

    \ \ \ \ ((\<gtr\>= p end) (reverse r))))

    \;

    (define vector-merge

    \ \ (case-lambda

    \ \ \ \ ((less-p v1 v2)

    \ \ \ \ \ \ (list-\<gtr\>vector (list-merge less-p (vector-\<gtr\>list v1) (vector-\<gtr\>list v2))))

    \ \ \ \ ((less-p v1 v2 start1)

    \ \ \ \ \ \ (list-\<gtr\>vector (list-merge less-p (subvector-\<gtr\>list v1 start1 (vector-length v1)) (vector-\<gtr\>list v2))))

    \ \ \ \ ((less-p v1 v2 start1 end1)

    \ \ \ \ \ \ (list-\<gtr\>vector (list-merge less-p (subvector-\<gtr\>list v1 start1 end1) (vector-\<gtr\>list v2))))

    \ \ \ \ ((less-p v1 v2 start1 end1 start2)

    \ \ \ \ \ \ (list-\<gtr\>vector (list-merge less-p (subvector-\<gtr\>list v1 start1 end1) (subvector-\<gtr\>list v2 start2 (vector-length v2)))))

    \ \ \ \ ((less-p v1 v2 start1 end1 start2 end2)

    \ \ \ \ \ \ (list-\<gtr\>vector (list-merge less-p (subvector-\<gtr\>list v1 start1 end1) (subvector-\<gtr\>list v2 start2 end2))))))

    \;

    (define (vector-merge! . r) (???))

    \;

    \;
  </scm-chunk>

  <section|测试>

  <\goldfish-chunk|tests/goldfish/liii/sort-test.scm|true|true>
    \;

    (import (liii check)

    \ \ \ \ \ \ \ \ (liii sort))

    \;

    (check-set-mode! 'report-failed)

    \;

    (define (pair-\<less\> x y)

    \ \ (\<less\> (car x) (car y)))

    \;

    (define (pair-full-\<less\> x y)

    \ \ (cond

    \ \ \ \ ((not (= (car x) (car y))) (\<less\> (car x) (car y)))

    \ \ \ \ (else (\<less\> (cdr y) (cdr x)))))

    \;

    (check-false (list-sorted? \<less\> '(1 5 1 0 -1 9 2 4 3)))

    (check-false (vector-sorted? \<less\> #(1 5 1 0 -1 9 2 4 3)))

    \;

    (check-true (list-sorted? \<less\> (list-sort \<less\> '(1 5 1 0 -1 9 2 4 3))))

    (check-true (list-sorted? \<less\> (list-stable-sort \<less\> '(1 5 1 0 -1 9 2 4 3))))

    (check-true (list-sorted? pair-\<less\> (list-merge pair-\<less\> '((1 . 1) (1 . 2) (3 . 1)) '((1 . 3) (2 . 1) (3 . 2) (4 . 1)))))

    (check (list-merge pair-\<less\> '((1 . 1) (1 . 2) (3 . 1)) '((1 . 3) (2 . 1) (3 . 2) (4 . 1)))

    \ \ \ \ \ \ \ =\<gtr\> '((1 . 1) (1 . 2) (1 . 3) (2 . 1) (3 . 1) (3 . 2) (4 . 1)))

    (check-true (list-sorted? pair-full-\<less\>

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (list-merge pair-full-\<less\> '((1 . 2) (1 . 1) (3 . 1)) '((1 . 3) (2 . 1) (3 . 2) (4 . 1)))))

    (check (list-merge pair-full-\<less\> '((1 . 2) (1 . 1) (3 . 1)) '((1 . 3) (2 . 1) (3 . 2) (4 . 1)))

    \ \ \ \ \ \ \ =\<gtr\> '((1 . 3) (1 . 2) (1 . 1) (2 . 1) (3 . 2) (3 . 1) (4 . 1)))

    \;

    (check-true (vector-sorted? \<less\> (vector-sort \<less\> #(1 5 1 0 -1 9 2 4 3))))

    (check-true (vector-sorted? \<less\> (vector-stable-sort \<less\> #(1 5 1 0 -1 9 2 4 3))))

    (check-true (vector-sorted? pair-\<less\>

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (vector-merge pair-\<less\> #((1 . 1) (1 . 2) (3 . 1)) #((1 . 3) (2 . 1) (3 . 2) (4 . 1)))))

    (check (vector-merge pair-\<less\> #((1 . 1) (1 . 2) (3 . 1)) #((1 . 3) (2 . 1) (3 . 2) (4 . 1)))

    \ \ \ \ \ \ \ =\<gtr\> #((1 . 1) (1 . 2) (1 . 3) (2 . 1) (3 . 1) (3 . 2) (4 . 1)))

    (check-true (vector-sorted? pair-full-\<less\>

    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (vector-merge pair-full-\<less\> #((1 . 2) (1 . 1) (3 . 1)) #((1 . 3) (2 . 1) (3 . 2) (4 . 1)))))

    (check (vector-merge pair-full-\<less\> #((1 . 2) (1 . 1) (3 . 1)) #((1 . 3) (2 . 1) (3 . 2) (4 . 1)))

    \ \ \ \ \ \ \ =\<gtr\> #((1 . 3) (1 . 2) (1 . 1) (2 . 1) (3 . 2) (3 . 1) (4 . 1)))

    \;
  </goldfish-chunk>

  vector-sorted?和list-merge!测试

  <\scm-chunk|tests/goldfish/liii/sort-test.scm|true|true>
    ;

    ;单元测试vector-sorted?新增支持可选参数功能、list-merge!实现原地合并功能

    ;

    (display "Testing vector-sorted?\\n")

    (check-true (vector-sorted? \<less\> #(1 2 3 4 5)))

    (check-false (vector-sorted? \<less\> #(1 3 2 4 5)))

    (check-true (vector-sorted? \<less\> #(5 1 2 3 4) 1))

    (check-false (vector-sorted? \<less\> #(5 1 3 2 4) 1))

    (check-true (vector-sorted? \<less\> #(5 1 2 3 4) 1 3))

    (check-false (vector-sorted? \<less\> #(5 1 3 2 4) 1 4))

    (check-catch "Invalid start or end parameters" (vector-sorted? \<less\> #(1 2 3 4 5) 3 2))

    \;

    (display "Testing list-merge!\\n")

    (define lis1 '(1 3 5))

    (define lis2 '(2 4 6))

    (test (list-merge! \<less\> lis1 lis2) '(1 2 3 4 5 6))

    \;

    (define lis3 '(1 1 3))

    (define lis4 '(1 2 4))

    (test (list-merge! \<less\> lis3 lis4) '(1 1 1 2 3 4))

    \;

    (define lis5 '())

    (define lis6 '(1 2 3))

    (test (list-merge! \<less\> lis5 lis6) '(1 2 3))

    (test (list-merge! \<less\> lis6 lis5) '(1 2 3))

    \;

    (define lis7 '())

    (define lis8 '())

    (test (list-merge! \<less\> lis7 lis8) '())

    \;
  </scm-chunk>

  list-sort、list-sort!、list-stable-sort!测试

  <\scm-chunk|tests/goldfish/liii/sort-test.scm|true|true>
    ;

    ;单元测试: 测试新增函数list-sort、list-sort!、list-stable-sort!

    ;

    ;; ================== 测试非破坏性快排 list-sort! ==================

    (display "Testing list-sort\\n")

    (define test-list '(3 1 4 1 5 9 2 6 5))

    (define sorted-list (list-sort \<less\> test-list))

    (check-true (list-sorted? \<less\> sorted-list))

    (check (length sorted-list) =\<gtr\> (length test-list))

    (check sorted-list =\<gtr\> '(1 1 2 3 4 5 5 6 9))

    (check (equal? test-list '(3 1 4 1 5 9 2 6 5)) =\<gtr\> #t) \ ; 确保原列表未被修改

    \;

    ;; ================== 测试破坏性快排 list-sort! ==================

    (display "Testing list-sort!\\n")

    (check-true (list-sorted? \<less\> (list-sort! \<less\> '(1 5 1 0 -1 9 2 4 3)))) \ ;; 测试原地排序后的结果

    (check-true (list-sorted? \<less\> (list-sort! \<less\> '(9 7 5 3 2 8 6 4 1)))) \ ;; 测试另一种顺序

    (check-false (list-sorted? \<less\> '(1 5 1 0 -1 9 2 4 3))) \ ;; 原始未排序的列表

    (check-true (list-sorted? \<less\> (list-sort! \<less\> '())))

    (check-true (list-sorted? \<less\> (list-sort! \<less\> '(42))))

    (check-true (list-sorted? \<less\> (list-sort! \<less\> '(1 2 3 4 5))))

    (check-true (list-sorted? \<less\> (list-sort! \<less\> '(3 1 4 1 5 9 2 6 5 3 5))))

    (check-true (list-sorted? \<less\> (list-sort! \<less\> '(0 -1 2 -2 3 1))))

    (check-true (list-sorted? \<less\> (list-sort! \<less\> '(5 -3 0 2 1 -1 4))))

    \;

    ; ================== 测试非稳定堆排序 list-stable-sort! ==================

    (display "Testing list-stable-sort!\\n")

    (display "Testing list-stable-sort!\\n")

    (check-true (list-sorted? \<less\> (list-stable-sort! \<less\> '(1 5 1 0 -1 1 5 1 0 1 1 5 9 2 4 3 4 9))))

    (check-true (list-sorted? \<less\> (list-stable-sort! \<less\> '(9 7 5 3 2 8 6 4 1 4 6 8 9 7 5 3 5 9 7 9))))

    (check-true (list-sorted? \<less\> (list-stable-sort! \<less\> '(3 1 4 1 5 9 2 6 5 3 5 5 9 2 6 9)))) \ ;; 验证排序是否正确

    (check-true (list-sorted? \<less\> (list-stable-sort! \<less\> '(0 -1 2 -2 0 -1 0 2 3 1 3)))) \ ;; 验证排序是否正确

    (check-true (list-sorted? \<less\> (list-stable-sort! \<less\> '(5 -3 0 2 1 -1 2 1 2 4 5 -3 0 5)))) \ ;; 验证排序是否正确

    \;
  </scm-chunk>

  <section|结尾>

  <\scm-chunk|tests/goldfish/liii/sort-test.scm|true|false>
    \;

    (check-report)
  </scm-chunk>

  <\scm-chunk|goldfish/srfi/srfi-132.scm|true|false>
    ) ; end of begin

    ) ; end of library

    \;
  </scm-chunk>
</body>

<\initial>
  <\collection>
    <associate|font-base-size|12>
    <associate|page-height|auto>
    <associate|page-orientation|landscape>
    <associate|page-screen-margin|false>
    <associate|page-type|a4>
    <associate|page-width|auto>
    <associate|preamble|false>
    <associate|save-aux|false>
  </collection>
</initial>