对列表进行排序的方案

Question

好吧，我正在尝试获取一个列表并将其从最大到最小排序。

Example:
> (maxheap (list 5 6 2 1 18 7))
;output:
> (18 7 6 5 2 1)

到目前为止，这就是我得到的结果：

(define (mkmaxheap heaplist)
  (let ((max (mymax(heaplist))))
  ;mymax is a func that returns max number, it works

    (let (( head (car heaplist)) (tail (cdr heaplist)))
      (if (null? tail)
         newlist))))

这就是我能编译的所有内容，我编写的所有其他代码都失败了。任何有关解决此问题的帮助将不胜感激。

Answer 1

您应该仔细阐明要用于生成排序列表的策略。是这样的吗？

• 找出列表中的最大数字。
• 获取列表中除最大值之外的其余部分。
• 对列表的其余部分进行排序，并将最大值放在前面。

这不是一种非常快的排序方法，但它应该有效。代码的下一步将是编写一个函数来获取列表中除最大值之外的其余部分（如果列表有重复项，请注意正确处理它。）

一旦编写完成，您应该能够编写Scheme代码看起来或多或少类似于上面的轮廓。

Answer 2

这是 Common Lisp 中的合并排序算法。它大致接近于在方案中实现相同的排序。

(defun merge-sort( input )
  (labels ((right-half ( input )
             (last input (ceiling (/ (length input) 2))))
           (left-half ( input )
             (ldiff input (right-half input ))))
    (if (or (null input) (null (cdr input))) 
        input 
        (merge 'list (merge-sort (left-half input)) (merge-sort (right-half input)) #'<))))

Answer 3

您需要决定使用什么来对列表进行排序。我最近一直在修改方案，通过 SICP 和“Schemer”系列，我发现在方案中实现冒泡排序、合并排序和快速排序非常容易。

Answer 4

您没有指定您正在使用的实现。但它可以实现 r6rs list-排序或srfi-95排序或任何其他内置- 排序中。查看您的实施文档。