以函數式語言實現快速排序

我需要在SML中實現快速排序來完成家庭作業，而且我迷路了。我之前並不熟悉quicksort是如何實現的，所以我讀到了這一點，但是我讀到的每一個實現都是非常重要的。這些看起來並不難，但我不知道如何在功能上實現快速排序。以函數式語言實現快速排序

維基百科碰巧在Standard ML（這是我的任務所需的語言）中有quicksort代碼，但我不明白它是如何工作的。

維基百科代碼：

val filt = List.filter 
fun quicksort << xs = let 
fun qs [] = [] 
| qs [x] = [x] 
| qs (p::xs) = let 
    val lessThanP = (fn x => << (x, p)) 
    in 
     qs (filt lessThanP xs) @ p :: (qs (filt (not o lessThanP) xs)) 
    end 
in 
    qs xs 
end

特別是，我不明白這行：qs (filt lessThanP xs) @ p :: (qs (filt (not o lessThanP) xs))。假設函數<（x，p）函數返回true，則過濾器將返回x小於p *的所有內容的列表，該列表與p相連，並與p相鏈接，該列表包含所有內容> = p。*

* x < p。當然，它不一定是那樣。

實際上，輸入這些信息有助於我理解發生了什麼。無論如何，我試圖將SML函數與後面的wiki的quicksort僞代碼進行比較。

功能快速排序當分區被定義爲

// left is the index of the leftmost element of the array 
// right is the index of the rightmost element of the array (inclusive) 
// number of elements in subarray = right-left+1 
function partition(array, 'left', 'right', 'pivotIndex') 
    'pivotValue' := array['pivotIndex'] 
    swap array['pivotIndex'] and array['right'] // Move pivot to end 
    'storeIndex' := 'left' 
    for 'i' from 'left' to 'right' - 1 // left ≤ i < right 
     if array['i'] < 'pivotValue' 
      swap array['i'] and array['storeIndex'] 
      'storeIndex' := 'storeIndex' + 1 
    swap array['storeIndex'] and array['right'] // Move pivot to its final place 
    return 'storeIndex'

那麼，到底其中分隔發生（數組， '左'， '右'）

// If the list has 2 or more items 
    if 'left' < 'right' 

     // See "Choice of pivot" section below for possible choices 
     choose any 'pivotIndex' such that 'left' ≤ 'pivotIndex' ≤ 'right' 

     // Get lists of bigger and smaller items and final position of pivot 
     'pivotNewIndex' := partition(array, 'left', 'right', 'pivotIndex') 

     // Recursively sort elements smaller than the pivot 
     quicksort(array, 'left', 'pivotNewIndex' - 1) 

     // Recursively sort elements at least as big as the pivot 
     quicksort(array, 'pivotNewIndex' + 1, 'right')

？還是我錯誤地思考SMLs quicksort？

來源

2011-10-31 Nate

那麼，究竟在哪裏進行分區呢？還是我錯誤地思考SMLs quicksort？

快速排序的純功能實現通過輸入列表上的結構遞歸工作（IMO，這是值得一提的）。此外，如您所見，兩次調用「filt」允許您將輸入列表分爲兩個子列表（比如A和B），然後可以單獨處理。在這裏重要之處在於：

A的所有元素都小於或等於所述樞轉元件（在代碼「P」）
B的所有元素都大於樞軸元件更大

一個必要的實現通過交換相同數組中的元素就地工作。在您提供的僞代碼中，「分區」函數的後不變性是您有兩個子數組，一個從輸入數組的「左」開始（以「pivotIndex」結尾），另一個從「pivotIndex」 '並以'右'結尾。這裏重要的是這兩個子數組可以被看作是子列表A和B的表示。

我認爲到現在爲止，您已經知道分區步驟正在發生的位置（或者相反，命令和功能有關係）。

來源

2011-10-31 07:44:58

你說的這個：

FILT將XS返回所有項的列表比P *，這是連接在一起P，這是禁忌版到家居> = P值*

這不太準確。 filt將返回x小於p的所有內容的列表，但該新列表不會立即與p連接。新列表實際上已遞交給qs（遞歸），並且無論qs返回與p連接。

在僞代碼版本中，分區發生在array變量中。這就是爲什麼你在partition循環中看到swap。進行分區就地性能比製作副本要好得多。

來源

2011-10-31 02:58:36

感謝您澄清我的誤解。此外，我很困惑在SML代碼中發生分區的位置，而不是僞代碼。對不起，如果不明確。 – Nate

@rob，@nate：「... filt將返回x小於p *的所有內容的列表，它與p相連，它包含在所有內容> = p。*中」這實際上並不完全正確。隱式括號如下所示：qs（filt lessThanP xs）@'（'p ::（qs（filt（not o lessThanP）xs））'）'。你不能列表列表，只有單個元素。列表被相互追加（@）。 –

以函數式語言實現快速排序

回答

相關問題