#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#define max_size 100
using namespace std;
void BuidHeap(int *a,int size);
void HeapAdjust(int i,int *a,int size);
void HeapSort(int *a , int size);
void BuidHeap(int *a,int size){
int i;
for (i = size/2;i >= 1;i--){
HeapAdjust(i,a,size);
}
}
void HeapAdjust(int i,int *a,int size){
int lchild = 2 * i;
int rchild = 2 * i + 1;
int max = i;
if (i <= size/2){
if(lchild <= size && a[lchild] > a[max]){
max = lchild;
}
if(rchild <= size && a[rchild] > a[max]){
max = rchild;
}
if(max != i){
swap(a[i],a[max]);
HeapAdjust(max,a,size);
}
}
}
void HeapSort(int *a , int size){
int i;
BuidHeap(a,size);
for (i = size; i >= 1 ; i--)
{
swap(a[1],a[i]);
HeapAdjust(1,a,i-1);
}
}
int main(){
int size;
int a[max_size];
while(scanf("%d",&size) == 1&& size>0){
for (int i = 1; i <= size; ++i){
cin>>a[i];
}
HeapSort(a,size);
for (int i = 1; i <= size; i++){
cout<<a[i]<<" ";
}
cout<<endl;
}
return 0;
}
排序——堆排序
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 一般来说，这三者的时间复杂度O(NlogN)，空间复杂度O(n)优化后，空间复杂度均可为O(1)，如下文中的快排和...
- －希尔排序 克服插入排序每次只能交换一对元素的缺点5-间隔的排序，3-间隔的排序，1-间隔排序（最后必须是1-间隔...
