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

Question

我不知道这个算法是堆排序还是快速排序.

假设我有一个没有源代码的算法--它是不稳定的，在大型数据集上性能很好，对于有序和无序的集合，运行时间类似。

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

Answer 1

我想说的是，从你的数据中判断出使用了什么算法是不可能的。

快速排序和堆排序都不稳定。此外，这两种方法都很好地处理大量输入( 常量并没有那么不同)。所以这两件事基本上没有告诉我们什么。

最后一项知识是关于分类输入的。快速排序是一种随机算法，因此排序输入在这里是不相关的。堆排序的运行时间也可用于两个方向的排序

HEAPSORT在已经按递增顺序排序的数组上的运行时间是Θ( even )，因为即使已经排序，它也将被转换回堆并排序。 HEAPSORT在按递减顺序排序的长度数组上的运行时间为Θ(n )。这是因为即使堆是在线性时间内构建的，每次删除元素并调用HEAPIFY时，它都可以覆盖树的全部高度。

我想猜测算法的唯一原因是利用快速排序的随机性。这意味着我将多次运行同一个数据集，并会看到执行时间的潜在波动(更糟糕的是O(n^2))。如果我没有发现任何显著的波动-这是堆排序，否则快速排序。

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

P.S.多亏了 Ixanezis和Mooing鸭子指出在现实世界中快速排序并不是真正的随机化。我不知道但这是真的

Answer 2

正确实现的快速排序在常量数组上以线性时间运行(即所有元素都相同的数组)。这是因为所有元素都将匹配支点，因此在将数组分成三个部分的旋转步骤之后：(< pivot)(= pivot)(> pivot)，左和右部分将为空，而且快速排序将立即终止。

Heapsort没有这个属性:它总是在O(n log )中运行。

因此，为了区分这两者，我尝试对不断增加的大小的常量数组进行排序，并希望看到堆排序实现出现比线性更大的减速。

这种方法还可以区分堆排序和实现得不好的快速排序实现！如果快速排序将数组分成三个部分( (<= pivot)(pivot)(> pivot) )，则快速排序将占用O(n^2)时间，因为右侧部分将为空，而左侧部分将包含n-1项。排序一个10,000,000项数组将区分这个坏的快速排序和堆排序--堆排序在现代机器上需要几秒钟的时间，但是实现不好的快速排序将需要很多分钟。