#include <iostream>
#define N 10
using namespace std;
int arr[N+1];
int count = 0;
void shiftUp(int k){
while(arr[k/2] < arr[k] && k > 1){
swap(arr[k/2], arr[k]);
k /= 2;
}
}
void insert(int v){
if(count + 1 > N) return;
arr[count + 1] = v;
count++;
shiftUp(count);
}
void shiftDown(int k){
while(2 * k <= count){
int j = 2 * k;
if(j + 1 <= count && arr[j + 1] > arr[j]){
j = j + 1;
}
if(arr[k] > arr[j]){
break;
}
swap(arr[j], arr[k]);
k = j;
}
}
int popMax(){
if (!count) return 0;
int v = arr[1];
swap(arr[1], arr[count]);
count--;
shiftDown(1);
return v;
}
void heapSort1(int a[], int n){
for (int i = 0; i < n; i++){
insert(a[i]);
}
for (int i = n - 1; i >= 0; i--){
a[i] = popMax();
}
}
void heapSort2(int a[], int n){
for (int i = 1; i <= n; i++){
arr[i] = a[i -1];
}
for(int i = n/2; i > 0; i--){
shiftDown(i);
}
count = n;
for (int i = n - 1; i >= 0; i--){
a[i] = popMax();
}
}
int main(){
int a[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
heapSort2(a, N);
for (int i = 0; i < N; i++){
cout << a[i] << " ";
}
return 0;
}
堆排序
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
