-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHeapSort.cpp
More file actions
45 lines (39 loc) · 775 Bytes
/
HeapSort.cpp
File metadata and controls
45 lines (39 loc) · 775 Bytes
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
#include <iostream>
using namespace std;
void adjustDown(int* list, int i, int len) {
int tmp = list[i];
while(i*2 + 1 < len) {
int k = i*2 + 1;
if(k + 1 < len && list[k] > list[k + 1]) {
k = k + 1;
}
if(tmp > list[k]) {
list[i] = list[k];
i = k;
}else {
break;
}
}
list[i] = tmp;
}
void heapSort(int* list, int len) {
//build heap, o(n)
for(int i = len/2 -1; i >= 0; i--) {
adjustDown(list, i, len);
}
//o(nlogn)
for(int i = len -1; i > 0; i--) {
int tmp = list[i];
list[i] = list[0];
list[0] = tmp;
adjustDown(list, 0, i);
}
}
int main() {
int list[] = {8, 5, 0, 3, 7, 1, 2};
heapSort(list, 7);
for(int i = 0; i < 7; i++) {
cout << list[i] << endl;
}
return 0;
}