本文主要是介绍8644 堆排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
8644 堆排序
时间限制:1000MS 代码长度限制:10KB
提交次数:1909 通过次数:1257题型: 编程题 语言: G++;GCC
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
对堆不熟悉的同学可以看一下这个视频堆排序(youtube)
主要注意初建堆时是从底(倒数第二层)往上建堆，而堆排序时是从上往下建堆。
所谓堆就是父节点大于俩个子结点的完全二叉树
完全二叉树规律(数组形式，从1开始)(根节点为1)
父节点序号设为s，则它的两个子结点分别为2s,2s+1。
#include <iostream>
#include <cstdio>
using namespace std;void Heapadjust(int A[],int s,int m)
{int t;t=A[s];for (int j=2*s; j<=m; j*=2){if (j<m&&A[j]<A[j+1]){j++;}if (t>A[j])//如果父结点大于俩个子结点中最大值{break;}else{A[s]=A[j];//否则父结点替换为子结点中最大值s=j;//记录替换的子结点位置}}A[s]=t;//插入,堆构建完成
}void CreatHeap(int A[],int n)//初建堆
{for (int i=n/2; i>0; i--)//先从子部倒数第二层开始建堆{Heapadjust(A,i,n);}for (int x=1; x<=n; x++){printf ("%d ",A[x]);}printf("\n");
}void Heapsort(int A[],int n)
{CreatHeap(A,n);int x;for (int i=n; i>1; i--){swap(A[1],A[i]);//将堆顶A[1]和当前序列最后一个结点A[i]Heapadjust(A,1,i-1);//将A[1~i-1]重新调整为大根堆for (x=1; x<=n; x++){printf ("%d ",A[x]);}printf("\n");}
}int main()
{int n;int A[1000];scanf("%d",&n);int i,j,x,k;for (i=1; i<=n; i++)//输入数据{scanf("%d",&A[i]);}Heapsort(A,n);return 0;
}这篇关于8644 堆排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
