堆排序 //7-heap sort methodvoid build_heap( int *arr, int start, int n ){ if( (start+1)*2 > n ) return; if( (start+1)*2 == n ) { if( arr[start] < arr[(start+1)*2-1] ) { int tmp; tmp = arr[start]; arr[start]=arr[(start+1)*2-1]; arr[(start+1)*2-1]=tmp; } } else { int tmp; if( arr[start] < arr[(start+1)*2-1] ) { tmp = arr[start]; arr[start] = arr[(start+1)*2-1]; arr[(start+1)*2-1] = tmp; build_heap( arr, (start+1)*2-1, n ); } if( arr[start] < arr[(start+1)*2] ) { tmp = arr[start]; arr[start] = arr[(start+1)*2]; arr[(start+1)*2] = tmp; build_heap( arr, (start+1)*2, n ); } }}void init_heap( int *arr, int n ){ int offset; if( n%2==0 ) { if( arr[n/2-1] < arr[n-1] ) { int tmp = arr[n/2-1]; arr[n/2-1]=arr[n-1]; arr[n-1]=tmp; } offset = n-1; } else offset = n; for( ; offset>1; offset-=2 ) { if( arr[offset/2-1] < arr[offset-1] ) { int tmp; tmp = arr[offset/2-1]; arr[offset/2-1]=arr[offset-1]; arr[offset-1]=tmp; build_heap(arr,offset-1, n ); } if( arr[offset/2-1] < arr[offset-2] ) { int tmp; tmp = arr[offset/2-1]; arr[offset/2-1]=arr[offset-2]; arr[offset-2]=tmp; build_heap(arr,offset-2, n ); } }}void heap_sort( int *arr, int n ){ int offset=n; init_heap( arr, n ); for( ; offset>1; ) { --offset; int tmp=arr[offset]; arr[offset]=arr[0]; arr[0]=tmp; build_heap( arr, 0, offset ); }}