algorithm - 有没有办法使用 Foldr 或 Foldl 函数在 SML 中编写堆排序算法？

Question

我想知道是否有一种方法可以使用 SML 的 Foldr 或 Foldl 函数编写堆排序算法。我在网上找不到示例，我想知道是否有人可以就此事给我一些指导。我想使用具有最小递归的高阶函数来实现排序算法。但是我不知道从哪里开始。

Answer 1

维基百科文章描述的 Heapsort 分两个阶段工作。首先，它将数组重新排列成一个最大堆，其中最大的项位于位置 0，其余项排列形成一个有效堆。

下一步对堆进行排序，方法是连续交换最大的项与数组末尾的项，减少计数，然后将新项筛选回堆中。花时间观看维基百科页面上的动画 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 在这里如何帮助你。