堆排序算法（C & Java 实现）

C语言版

#include <stdio.h>

#define SWAP( a, i, j ) { t = a[i]; a[i] = a[j]; a[j] = t; }
#define LESS( a, b )    ( a < b ) 

void disp_array( int a[], int n )
{
	int i;
	for( i = 0; i < n; ++i )
		printf( "%d ", a[i] );
	printf( "\n" );
}

void heap_adjust( int a[], int s, int m )
{
	int i, key = a[s];
	for( i = 2 * s + 1; i <= m; i <<= 1 )
	{
		if( i < m && LESS( a[i], a[i + 1] ) ) ++i;
		if( ! LESS( key, a[i] ) ) break;
		a[s] = a[i]; s = i;
	}
	a[s] = key;
}

void heap_sort( int a[], int n )
{
	int i, t;
	// adjust a[0...n-1] into a max heap
	for( i = ( n - 2 ) / 2; i >= 0; --i )
		heap_adjust( a, i, n - 1 );

	printf( "Heap: " );
	disp_array( a, n );

	for( i = n - 1; i > 0; --i )
	{
		SWAP( a, 0, i );
		heap_adjust( a, 0, i - 1 );
	}
}

int main()
{
	//int a[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
	int a[] = { 100, 49, 38, 65, 97, 76, 13, 27, 49 };
	int n = 9;

	printf( "Before sorting: " );
	disp_array( a, n );

	heap_sort( a, n );

	printf( "After sorting: " );
	disp_array( a, n );

	return 0;
}#include <stdio.h>

#define SWAP( a, i,