有沒有辦法使用Foldr或Foldl函數在SML中編寫堆排序算法？

我想知道是否有編寫使用SML的FOLDR或與foldl函數堆排序算法的一種方式。我在網上找不到一個例子，我想知道是否有人可以給我一些關於這個問題的指導。我想使用遞歸最小的高階函數來實現排序算法。不過，我不知道從哪裏開始。有沒有辦法使用Foldr或Foldl函數在SML中編寫堆排序算法？

來源

2014-03-12 Rootkit32

這是沒有意義的。摺疊是爲了在迭代列表時累積一個值。現在，這是多少工作。在heapsort中，你把所有的元素都拿出來，堆起來，然後從堆中一個一個地抽取元素。 – newacct

一旦你創建了堆，你可以對堆中的數據進行排序，這就是堆排序。這裏是維基百科頁面：http：//en.wikipedia.org/wiki/Heapsort。所以我的問題是，你將如何採取堆並應用排序算法堆到排序呢？ – Rootkit32

對。但是你在這裏迭代了哪些列表？你正在堆積一堆，並反覆從它中取出一個元素來形成一個列表，所以這是一個展開的過程。 – newacct

的堆排序是維基百科的文章介紹了兩個階段的作品。首先它將數組重新排列成一個Max-heap，最大的項目位置爲0，其餘的項目排列成一個有效的堆。

下一步依次交換最大的項目與該項目在數組的末尾，減少次數和篩選新項目回落到堆排序堆。花時間觀看Wikipedia頁面上的動畫GIF示例。

的排序階段是這樣的：

last_item = array.Length - 1 
while (last_item > 0) 
{ 
    // move largest item to the end of the array 
    // and replace with the item that was at the end 
    swap(0, last_item) 

    // decrease the count, 
    // and sift the item down to its proper place 
    --last_item 
    sift_down(0, last_item) 
}

如果這樣做了，該陣列是按升序排列。

我看不出foldl或foldr可以幫助你在這裏。

來源

2014-03-13 02:00:20

好吧，你幾乎不能使用與foldl或FOLDR寫在SML一個「篩下」的算法。非常感謝你。 – Rootkit32

有沒有辦法使用Foldr或Foldl函數在SML中編寫堆排序算法？

回答

相關問題