swust oj 1015 堆排序
堆排序算法<small class="ojcolor">(1015)</small>
Time limit(ms): 1000
Memory limit(kb): 10000
Submission: 4319
Accepted: 2650
Accepted
编写程序堆排序算法。按照非递减排序，测试数据为整数。
Description
第一行是待排序数据元素的个数； 第二行是待排序的数据元素。
Input
一趟堆排序的结果。
Output
| 1 2 3 | 10 50 36 41 19 23 4 20 18 12 22 |
Sample Input
| 1 | 4 12 20 18 22 41 50 36 19 23 |
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stack>
#include<string.h>
#include<queue>
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
int dui[1000];
int n;
void swap(int i, int j)
{
int temp = dui[i];
dui[i] = dui[j];
dui[j] = temp;
}
void sitdown(int i)
{
int t, flag=0;
while (i * 2 <= n && flag == 0)
{
if (dui[i] > dui[i * 2])
{
t = i * 2;
}
else { t = i; }
if (i * 2 + 1 <= n)
{
if (dui[t] > dui[i * 2 + 1])
{
t = i * 2 + 1;
}
}
if (t != i)
{
swap(t, i);
i = t;
}
else
{
flag = 1;
}
}
return;
}
int main()
{
while (cin >> n)
{
for (int i = 1; i <= n; i++)
{
cin >> dui[i];
}
for (int i = n / 2; i >= 1; i--)
{
sitdown(i);
}
for (int i = 1; i <= n; i++)
{
cout << dui[i] << ' ';
}
}
return 0;
}
