合併排序：使用混合元素排序列表

Question

我在Scheme中編寫合併排序。我有一個合併排序定義，拆分列表的拆分器和合並列表的合併。

(define mymergesort 
    (lambda (alist) 
    (if (null? (cdr alist)) alist 
     (let ((splits (splitter alist))) 
      (merge (mymergesort (car splits)) (mymergesort (cadr splits))))))) 

(define splitter 
    (λ (alist) (splitter-helper alist()()))) 

(define splitter-helper 
    (λ (alist list_a list_b) 
    (cond ((null? alist) (cons (reverse list_a) (cons list_b()))) 
      ((null? (cdr alist)) (cons (reverse (cons (car alist) list_a)) (cons list_b()))) 
      (else (splitter-helper (reverse (cdr (reverse (cdr alist)))) (cons (car alist) list_a) (cons (car (reverse (cdr alist))) list_b)))))) 

(define merge 
    (λ (list_a list_b) 
    (cond ((null? list_a) list_b) 
      ((null? list_b) list_a) 
      ((<= (car list_a) (car list_b)) (cons (car list_a) (merge (cdr list_a) list_b))) 
      ((<= (car list_b) (car list_a)) (cons (car list_b) (merge list_a (cdr list_b))))))) 

這個實現似乎很適合排序數字列表。但我想能夠排序混合元素的列表。

例如： 「（I可以 「走」 4 「約」 123汽水Kα）

任何建議/解決方案？我也試圖避免使用大多數程序，比如「欺騙」遞歸解決方案。

Answer 1

您需要一個「啓發式」來對這些項目進行排序。例如，「去」在「關於」之前出現嗎？那麼4呢？所以你可以編寫一個函數來確定你想要排序的元素是'< ='到另一個元素。此外，

(<= (car list_a) (car list_b))然後(<= (car list_b) (car list_a))是一種多餘的。如果a不是< = b，那麼我們知道a> b。