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
