算法描述——是堆排序还是快速排序？

Question

我很难判断这个算法是堆排序还是快速排序...

假设我有一个我没有源代码的算法 - 它不稳定，在大型数据集上性能良好，并且在有序和无序集上的运行时间相似。

在没有更多信息的情况下，是否可以判断这个算法是堆排序还是快速排序？

Answer 1

我要说的是，从您拥有的数据中判断出使用了哪种算法几乎是不可能的。

---

快速排序和堆排序都是不稳定的。此外，两者都可以很好地处理大输入(constants are not that different)。所以这两件事几乎没有告诉我们什么。

最后一条知识是关于排序输入的。快速排序是一种随机算法，因此排序后的输入在这里无关紧要。堆排序的运行时间也为both directions of sort。 :

The running time of HEAPSORT on an array of length that is alreadysorted in increasing order is Θ(n lgn), because even though it isalready sorted, it will be transformed back into a heap and sorted.

The running time of HEAPSORT on an array of length that is sorted indecreasing order will be Θ(n lgn). This occurs because even though theheap will be built in linear time, every time the element is removedand HEAPIFY is called, it could cover the full height of the tree.

---

我尝试猜测算法的唯一原因是利用快速排序的随机性。我的意思是我会多次运行相同的数据集，并且会看到执行时间的潜在波动(最坏的情况是 O(n^2))。如果我没有发现任何明显的波动 - 这是堆排序，否则是快速排序。

---

如果你能分析它使用的内存，你可能会更幸运。堆排序需要 O(1)，而好的快速排序需要 O(logn) 额外的内存，而简单的需要 O(n)。但是您没有这些信息可供您使用。

附言感谢 Ixanezis 和 Mooingduck 指出现实世界中的快速排序并不是真正随机的。我不知道but it is true