DrScheme中的快速排序

Question

我目前正在學習函數式語言（如Lisp和DrScheme）的過程，但我被要求在DrScheme中編寫Quicksort算法的方差。但是，從哪裏開始，我有點無知。

有人可以給我一些指針，使用哪些函數和數據類型？我顯然知道名單，汽車，司機，和追加將發揮什麼要做的很大一部分。

順便說一句，我只是真的在尋找從一開始的一般想法。我不一定需要完整的答案。那種破壞它的冒險和樂趣！

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：小於在列表中的第一個元素的元素列表，所述單列表與列表中（樞轉）的第一元件和所述列表元素大於或等於列表中的第一個元素。

在Quicksort的實際實現中，在選擇適當的主元素時要更加小心，但對於這個簡單的例子來說，就足夠了第一個元素。