O(nLogn)排序 ：堆

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void adjust_up(vector<int> &v, int index)
{
    int parent = 0;
    int hole = index;
    int temp = v.at(index);
    for(; (hole - 1) / 2 >= 0 && hole > 0; hole = parent)
    {
        parent = (hole - 1) / 2;
        if (temp > v.at(parent))
        {
            v.at(hole) = v.at(parent);
        }
        else
        {
            break;
        }
    }
    v.at(hole) = temp;
}

void adjust_down(vector<int> &v, int index, int length)
{
    int child = 0;
    int hole = index;
    int temp = v.at(index);
    for(; hole * 2 + 1 <= length; hole = child)
    {
        child = hole * 2 + 1;
        if((child + 1 <= length) && (v.at(child  + 1) > v.at(child)))
        {
            ++child;
        }
        if(v.at(child) > temp)
        {
            v.at(hole) = v.at(child);
        }
        else
        {
            break;
        }
    }
    v.at(hole) = temp;
}

void build_heap(vector<int> &v, int length)
{

    for (int i = (v.size() - 2) / 2; i >= 0; i--)
    {
        adjust_down(v, i, length);
    }
}

int main(int argc, const char **argv)
{
    auto put = [](vector<int > &v)
    {
        cout << "---" << endl;
        for (auto &n : v)
        {
            cout << n << endl;
        }
    };

    vector<int> v {23, 45, 3, 56, -3, 11};

    for(int i = v.size() - 1; i > 0; i--)
    {
        build_heap(v, i);
        std::swap(v.at(0), v.at(i));
    }

    put(v);

    return 0;
}

备份地址: 【O(nLogn)排序 ：堆】