排序——堆排序

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

// 堆排序的内部方法
// i是堆中一项的下标
// 返回左儿子的下标
inline int leftChild(int i)
{
    return 2 * i + 1;
}

// 在deleteMax和bulidHeap中用到的堆排序的内部方法
// i是开始向下过滤的位置
// n是二叉堆的逻辑大小
template<class T>
void percolateDown(vector<T> &a, int i, int n)
{
    int child;
    T tmp;

    for(tmp = move(a[i]); leftChild(i) < n; i = child){
        child = leftChild(i);
        if(child != n - 1 && a[child] < a[child + 1])
            ++child;
        if(tmp < a[child])
            a[i] = move(a[child]);
        else
            break;
    }
    a[i] = move(tmp);
}

template<class T>
void heapSort(vector<T> &a)
{
    for(int i = a.size() / 2 - 1; i >= 0; --i){
        percolateDown(a, i, a.size());
    }

    for(int j = a.size() - 1; j > 0; --j){
        swap(a[0], a[j]);
        percolateDown(a, 0, j);
    }
}


int main()
{
    vector<int> a = {9,8,7,6,5,4,3,2,1};

    heapSort(a);

    for(int i = 0; i < a.size(); ++i)
        cout << a[i] << '\t' ;

    return 0;
}

//using STL
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void heapSort(vector<int> &v)
{
    priority_queue<int> pq;

    for (size_t i = 0; i < v.size(); ++i){
        pq.push(v[i]);
    }

    for (int i = v.size() - 1; i >= 0; --i){
        v[i] = pq.top();
        pq.pop();
    }
}

void writeVector(vector<int> &v)
{
    for (size_t i = 0; i < v.size(); ++i)
        cout << v[i] << " ";

    cout << endl;
}

int main()
{
    vector<int> v = {16, 29,14,32,18,14,87,50,64,35};
    writeVector(v);

    heapSort(v);
    writeVector(v);

    return 0;
}

# run result
16 29 14 32 18 14 87 50 64 35 
14 14 16 18 29 32 35 50 64 87