scheme - 有人使用 Dr 方案编程吗？如何使用列表排序？

Question

在 dr 方案中使用哪种数据结构对 n 个数字进行排序我不允许使用向量和结构..如果我使用列表，我无法编辑列表值。所以我如何对 n 个数字进行排序。我使用的语言是文本 mzscheme rsr5

Answer 1

如果您无法编辑列表值...返回一个新列表！:-)

Answer 2

插入排序解决方案在方案中非常简单（使用 N^2 的 BigO 性能很差，但仍然可以完成工作）

要对 n 个数字进行排序，您可以使用列表数据类型来保存值，而数字列表可以是；

• 空的，

• (cons number ListofNumber)

对于插入排序，您需要 2 个函数，以及将数字单次插入到已排序的数字列表中的 Inserter，以及将递归调用此插入的另一个函数。

插入函数的输入输出

;;insert: Number ListOfNumber(Sorted) -> ListOfNumber(Sorted)
(define (insert n lon)
    (cond
        [(empty? lon) (cons n lon)] 
        [(<= n (first lon)) (cons n lon)] 
        (else 
            (cons (first lon) (insert n (rest lon))) )))


;;insertion-sort: ListOfNumber -> ListOfNumber(Sorted)
(define (insertion-sort lon)
    (cond
        [(empty? lon) lon] ;;if the list is empty than the numbers are sorted
        (else
            (insert (first lon) (insertion-sort (rest lon))) )))

我希望这个答案适合你的问题

Answer 3

不确定您是否应该为家庭作业编写自己的冒泡排序，但否则这是内置的：

（排序（列表 1 2 4 3）<）（1 2 3 4）