sorting - 对堆进行排序的最快方法（至少在理论上）是什么？

Question

堆是一个列表，其中适用以下内容：

l[i] <= l[2*i] && l[i] <= [2*i+1]

为了0 <= i < len(list)

我正在寻找就地排序。

Answer 1

只需使用堆排序。它是就地的。那将是最自然的选择。

您也可以直接使用您的堆并使用其他算法对其进行排序。之后，您从排序列表中重新构建堆。快速排序是一个很好的选择，因为您可以确定它不会仅仅因为您的堆已经预先排序而以最坏的 O(n²) 顺序运行。

如果您的比较功能很昂贵，那可能会更快。堆排序倾向于经常评估比较函数。

Answer 2

好吧，通过将数据放在堆中，您已经完成了堆排序的一半。您只需要实现堆排序算法的第二部分。这应该比在堆数组上使用快速排序更快。

如果你有勇气，你可以尝试实现smoothsort，它比堆排序快于几乎排序的数据。

Answer 3

就地对堆进行排序听起来像是Heap Sort的工作。

我假设内存受到限制，也许是嵌入式应用程序？

Answer 4

既然你已经有一个堆，你不能只使用堆排序的第二阶段吗？它可以在适当的位置工作，并且应该很好且高效。

Answer 5

对于就地排序，最快的方法如下。当心我的代码中的一个错误。请注意，此方法提供了一个反向排序列表，该列表需要在最后一步中取消。如果你使用最大堆，这个问题就会消失。

总体思路很简洁：将最小元素（索引 0 处）与堆中的最后一个元素交换，将该元素向下冒泡直到堆属性恢复，然后将堆的大小缩小一并重复。

正如 David Mackay在这里演示的那样，这并不是非就地排序的绝对最快方法- 您可以通过将更可能是最小的元素放在堆顶部而不是底部行中的元素来做得更好。

时间复杂度是 T(n.log n) 最坏情况 - n 次迭代可能有 log n（堆的高度）通过 while 循环。

for (int k=len(l)-1;k>0;k--){
swap( l, 0, k );
while (i*2 < k)
  {
int left = i*2;
int right = l*2 + 1;
int swapidx = i;
if ( l[left] < l[right] )
  {
    if (l[i] > l[left])
      {
    swapidx = left;
      }
  }
else
  {
    if (l[i] > l[right])
      {
    swapidx = right;
      }
  }

if (swapidx == i)
  {
    // Found right place in the heap, break.
    break;
  }
swap( l, i, swapidx );
i = swapidx;
  }}

// Now reverse the list in linear time:
int s = 0; 
int e = len(l)-1;
while (e > s)
  {
    swap( l, s, e );
    s++; e--:
  }

Answer 6

逐一读取堆顶的项目。基本上你所拥有的是堆排序。