functional-programming - DrScheme 中的快速排序

Question

我目前正在学习 Lisp 和 DrScheme 等函数式语言，但有人要求我在 DrScheme 中编写 Quicksort 算法的变体。但是，我有点不知道从哪里开始。

有人可以给我一些关于使用哪些函数和数据类型的指示吗？我显然知道列表、汽车、cdr 和 append 将在做什么方面发挥重要作用。

顺便说一句，我只是在寻找一般的想法来启动。我不一定想要完整的答案。有点毁了它的冒险和乐趣！

Answer 1

快速排序是以函数式风格实现的最简单的排序算法之一。使用此伪代码作为对数字列表进行升序排序的起点，注意您需要的唯一数据结构是标准 Lisp 列表：

quicksort(lst)
    if lst is empty
        return empty list
    return quicksort([all the elements < first element in lst])
           + [first element in lst] +
           quicksort([all the elements >= first element in lst])

“棘手”部分，即获取列表中小于（或大于或等于）第一个元素的所有元素，可以很容易地用filter过程来表示。如果您不被允许使用它，那么从头开始实现它的基本功能就很容易了。

另请注意，+我的伪代码中的运算符表示append三个列表中的一个：小于列表中第一个元素的元素列表、具有列表中第一个元素（枢轴）的单例列表以及大于或等于的元素列表到列表中的第一个元素。

在快速排序的实际实现中，在选择适当的枢轴元素时会更加小心，但对于这个简单的示例来说，就足以取第一个元素了。