极度简化版 HeapSort

看了网上很多HeapSort版本实现都很复杂，其实HeapSort是完全可以只用一个循环在10行内解决的，先上代码：

void heapsort(int* array, int size) {
    int top = size;
    int bot = size;
    int cur;
    int nxt = size;

    while(cur = nxt, bot > 0) {
        if(cur * 2 + 1 < bot && array[nxt] < array[cur * 2 + 1]) nxt = cur * 2 + 1;
        if(cur * 2 + 2 < bot && array[nxt] < array[cur * 2 + 2]) nxt = cur * 2 + 2;
        if(cur < nxt) {
            std::swap(array[cur], array[nxt]);
        } else {
            nxt = top? --top : (std::swap(array[0], array[--bot]), 0);
        }
    }
    return;
}

 这个实现的原理就是初始让堆顶和堆底都在数组最末尾，然后堆顶首先向前扩展，途中不断做Heapify，在堆顶到达array[0]后整个堆就建好了（其实就是一趟自底向上的O(n)建堆过程）。然后堆底也向前移动，并完成取最大值和重建堆的操作，当堆底也到达array[0]时排序就结束了。

可见这是一个无删减的HeapSort实现，并且实测中与其它HeapSort相比也没有什么性能损失。