问题标签 [heapsort]

作为 Haskell 的一个练习，我正在尝试实现堆排序。堆通常在命令式语言中实现为数组，但这在纯函数式语言中效率非常低。因此，我查看了二进制堆，但到目前为止我发现的所有内容都从命令式的角度描述了它们，并且所呈现的算法很难转化为功能设置。如何用 Haskell 等纯函数式语言高效地实现堆？

编辑：高效我的意思是它仍然应该在 O(n*log n) 中，但它不必击败 C 程序。另外，我想使用纯函数式编程。在 Haskell 中这样做还有什么意义？

堆排序的最坏情况复杂度为 ，O(nlogn)而快速排序的复杂度为O(n^2). 但经验证据表明快速排序更胜一筹。这是为什么？

我需要 HeapSort 算法对数组的元素进行排序，这样数组的所有元素，即 [19 18 14 15 5 7 13 3 8] 都处于非递减顺序。

快速排序和堆排序都进行就地排序。哪个更好？哪些应用和案例是首选？

使用堆排序按降序排序并显示步骤或解释请在下面是树

下面是数组 79 - 33 - 57 - 8 - 25 - 48 ok 升序很容易，因为最大的元素在顶部，我们可以交换最后一个元素和第一个元素，然后使用 heapify 作为 wikipedia 中的示例代码描述它。

好的，让我澄清一下，堆是建立在我画的树上的。我知道升序的步骤，数组看起来像 8 - 25 - 33 - 48 - 57 - 79。但是降序的步骤是什么。这是一个非常直接的问题。只需解释按降序排列数组所需的步骤。

我一直在看这个几个小时，无法弄清楚。如果 heapify 函数中的比较更改为大于，则输出按应有的递增顺序排列。我希望我的列表按降序排序，但它没有使用以下代码给出正确的输出：

程序输出：

我需要用 C 编写一个排序程序，如果可以对文件进行排序以节省磁盘空间，那就太好了。数据很有价值，所以我需要确保如果进程被中断（ctrl-c）文件没有损坏。我可以保证机器上的电源线不会被拉扯。

额外细节：文件约为 40GB，记录为 128 位，机器为 64 位，操作系统为 POSIX

有关完成此操作的任何提示或一般注意事项？

谢谢！

澄清一下：我希望用户会想要 ctrl-c 这个过程。在这种情况下，我想优雅地退出并确保数据安全。所以这个问题是关于处理中断和选择一种可以在需要时快速结束的排序算法。

跟进（2 年后）：为了后代，我安装了 SIGINT 处理程序，它工作得很好。这并不能保护我免受电源故障的影响，但这是我可以处理的风险。代码位于https://code.google.com/p/pawnsbfs/source/browse/trunk/hsort.c和https://code.google.com/p/pawnsbfs/source/browse/trunk/qsort.c

我的程序有一个错误，我不知道为什么这个错误出现在 63 Line。

有人可以描述一种算法，该算法在最小堆的数组实现中找到所有小于 x 的键。我希望运行时间至少为 O(k)，其中 k 是报告的键数。

我一直在为此挠头。

我必须在 C# 中检查 HeapSort 算法时间，我的问题是我知道我必须使用 System.Timers ，因为我不知道如何测量算法时间。我必须检查包含 1000 ,10 000 , 100 000 和 1000 000 个整数的表的算法时间。

请帮助我的好人。

这是代码：

我在你的帮助下写了这个，好吗？

{ int i; //Boulding a heap for (i = (list.Length - 1) / 2;i >=0;i--) Adjust (list, i, list.Length - 1);

}