8644 堆排序

Description

用函数实现堆排序，并输出每趟排序的结果

输入格式

第一行：键盘输入待排序关键的个数n
第二行：输入n个待排序关键字，用空格分隔数据

输出格式

第一行：初始建堆后的结果
其后各行输出交换堆顶元素并调整堆的结果，数据之间用一个空格分隔

输入样例

10
5 4 8 0 9 3 2 6 7 1

输出样例

9 7 8 6 4 3 2 5 0 1
8 7 3 6 4 1 2 5 0 9
7 6 3 5 4 1 2 0 8 9
6 5 3 0 4 1 2 7 8 9
5 4 3 0 2 1 6 7 8 9
4 2 3 0 1 5 6 7 8 9
3 2 1 0 4 5 6 7 8 9
2 0 1 3 4 5 6 7 8 9
1 0 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9

堆排序，用一个数组储存，但在使用时其实将其看成是一个完全二叉树，用到了一个非常重要的性质，即完全二叉树i的左孩子为2*i右孩子为2*i+1.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int a[100005];
//cur是当前要调整的堆的根，n指数组大小
void adjust(int cur,int n)
{
		int i = cur;
		//这里一定要判断是否越界
		while ((2 * i <= n && a[i] < a[2 * i]) ||( 2 * i + 1 <=n&& a[i] < a[2 * i + 1]))
		{
			
			int h = i;
			//这里令h等于左右孩子的最大值的下标，让下一次从变动后的孩子开始
			//因为另一个孩子已经符合堆的要求了，不用理会
			if ((2 * i <= n && a[2 * i] >= a[2 * i + 1])|| 2 * i + 1 > n) h = 2 * i;
			else
			{
				h = 2 * i + 1;
			}
			//只有当a[i] ap[each])break;
//		ap[j] = ap[each];
//	}
//	ap[j] = tmp;
//}
int main()
{
	//freopen("in.txt", "r", stdin);
	int n = 0;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	//建堆
	for(int i=n/2;i>=1;i--)
	adjust(i,n);
	print(n);
	for (int i = n; i >= 2; i--)
	{
		swap(a[1], a[i]);
		adjust(1,i - 1);
		print(n);
	}
}

8644 堆排序

C/C++/C#相关栏目本月热门文章