3.堆排序

#include <iostream>
#include <vector>

using namespace std;

inline int leftChild(int i)
{
    return 2 * i + 1;
}

template <typename T>
void percDown(vector<T> &a, int i, int n)
{
    int child;
    T tmp;
    for (tmp = 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] = a [child];
        else
            break;
    }
    a[i] = tmp;
}

template <typename T>
void heapSort(vector<T> &a)
{
    /*build heap*/
    for (int i = a.size() / 2 - 1; i >= 0; i--)
        percDown(a, i, a.size());
    /*delete max*/
    for (int j = a.size() - 1; j > 0; j--) {
        swap(a[0], a[j]);
        percDown(a, 0, j);
    }
}

int main()
{
    vector<int> test = {190, 435, 834, 8954, 923, 56, 20 ,1, 934, 5465, 504, 23054, 430};
    heapSort(test);
    for (auto i : test)
        cout << i << " ";
    cout << endl;
    return 0;
}

• 运行结果：

$ ./a.out
1 20 56 190 430 435 504 834 923 934 5465 8954 23054

• 我的个人主页：http://www.techping.cn/
• 我的个人站点博客：http://blog.techping.cn/
• 我的CSDN博客：http://blog.csdn.net/techping
• 我的简书：http://www.jianshu.com/users/b2a36e431d5e/timeline
• 我的GitHub：https://github.com/techping