久しぶりに、プログラミング。
今日はいままで自分で書いたことなかったヒープソート。

<code>
<br>#ifndef __HEAPSORT_H__
<br>#define __HEAPSORT_H__
<br><br>template <typename t><br>void MaxHeapify( T* target, unsigned int index , unsigned int length) {
<br>	unsigned int l = index	unsigned int r = (index	unsigned int max = index;
<br>	if( l 		max = l;
<br>	}
<br>	if( r 		max = r;
<br>	}
<br>	if( index != max ){
<br>		T tmp = target[index];
<br>		target[index] = target[max];
<br>		target[max] = tmp;
<br>		MaxHeapify( target, max, length );	
<br>	}
<br><br>	return;
<br>}
<br><br>template <typename t><br>void BuildMaxHeap( T* target, unsigned int length ){
<br>	for( unsigned int i = (length-1)/2; true ; i-- ){
<br>		MaxHeapify( target, i, length );
<br>		if( 0 == i ){
<br>			break;
<br>		}
<br>	}
<br>}
<br><br><br>template <typename t><br>void HeapSort( T* target, unsigned int length){
<br>	BuildMaxHeap( target , length );
<br>	while(length != 0 ){
<br>		T tmp = target[length-1]; 
<br>		target[length-1] = target[0];
<br>		target[0] = tmp;
<br>		length--;
<br>		MaxHeapify(target, 0, length );
<br>	}
<br>}
<br><br>#endif
<br><br><br></typename></typename></typename></code>

includeしてから次ように使う。

<code>
<br>unsigned char buf[] = {5,7,10,8,11};
<br>HeapSort( buf, 5 );
<br>//ここでbuf内はソート済み。
<br></code>