Fork me on GitHub

排序算法@c++描述-堆排序

3.堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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;
}
  • 运行结果:
    1
    2
    $ ./a.out
    1 20 56 190 430 435 504 834 923 934 5465 8954 23054