堆是适用以下条件的列表：

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

对于'0 <= i <len(list)`

我正在寻找就地排序。

解决方案

逐一读取堆顶部的项目。基本上，我们所拥有的就是堆排序。

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

如果我们觉得自己很勇敢，可以尝试实施Smoothsort，它比对几乎排序的数据进行堆排序要快。

就地对堆进行排序听起来像是"堆排序"的一项工作。

我认为内存有限，也许是嵌入式应用？

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

我们也可以使用它的堆，然后使用其他算法对其进行排序。然后，我们从排序列表中重新构建堆。 Quicksort是一个不错的选择，因为我们可以确定它不会以最坏情况的O(n2)顺序运行，因为堆已经被预先排序了。

如果比较功能很昂贵，那可能会更快。堆排序往往会经常评估比较功能。

既然我们已经有一个堆，我们是否不能只使用堆排序的第二阶段？它工作到位，应该很好并且有效。

对于就地分拣，遵循最快的方法。当心我的代码中的一次性错误。请注意，此方法给出了反向排序的列表，在最后一步中需要将其不反向。如果使用最大堆，此问题将消失。

总体思路很整洁：将最小的元素(索引为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--:
  }