NOIP 提高组初赛 · NOIP 2007 提高组初赛试题 第 26 题

看程序写结果

#include "stdio.h"
char	ch[] = { 'q', 'A', 'S', 'O', 'R', 'T', 'E', 'X', 'A', 'M', 'P', 'L', 'E' };
int	n = 12;
void shift( int k, int n )
{
	char	v;
	int	j;
	v = ch[k]; j = k + k;
	while ( j <= n )
	{
		if ( (j < n) && (ch[j] < ch[j + 1]) )
			j++;
		if ( v < ch[j] )
		{
			ch[j / 2] = ch[j]; j *= 2;
		}else
			return;
		ch[j / 2] = v;
	}
}


void hpsrt( void )
{
	int	k;
	char	tmp;
	for ( k = n / 2; k > 0; k-- )
		shift( k, n );    /* 建堆*/
	printf( "No.1: " );
	for ( k = 1; k <= n; k++ )
		putchar( ch[k] );
	putchar( '\n' );
	for ( k = n; k > 0; k-- )
	{
		tmp = ch[1]; ch[1] = ch[k]; ch[k] = tmp;
		shift( 1, k - 1 );
	}
}


main()
{
	int k;
	hpsrt();
	printf( "No.2: " );
	for ( k = 1; k <= n; k++ )
		putchar( ch[k] );
	putchar( '\n' );
}

输出：________

堆排序：No.1 为建堆结果（大顶堆），No.2 为排序输出（升序）。

区分"建堆阶段"与"排序阶段"的输出。

堆排序

ch[1..12]={q,A,S,O,R,T,E,X,A,M,P,L,E}

建堆（大顶堆） → No.1: XTORSEAAMPLE 排序（升序）→ No.2: AAEELMOPRSTX

复杂度：O(n log n)