排序算法 堆排序

堆排序使用最大堆。堆排序：将初始序列构造成最大堆； 第一趟排序，将堆顶元素 A[0] 和堆底元素 A[n-1]进行交换，然后调用AdjustDown对堆顶元素进行向下调整，使剩余的前n-1个元素还是堆。然后使堆顶元素与A[n-2]交换，在进行向下调整。直到最后只剩下堆顶元素。

template <class T>
void AdjustDown(T heap[],int r,int j){
	T temp = heap[r];
	int child = 2 * r + 1;
	while(child < j ){
		child = heap[child] < heap[child+1] ? (child+1) : child;
		if(temp < heap[child]){
			heap[r] = heap[child];
			heap[child] = temp;
			r = child ;
			child = 2 * r + 1;
			temp = heap[r];
		}else
			break;
	}
}
template <class T>
void CreateHeap(T heap[],int n){
	for(int i = n/2 - 1;i>-1;i--)
		AdjustDown(heap,i,n-1);
}
template <class T>
void swap(T &a, T &b){
	T temp = a;
	a = b;
	b = temp;
}
template <class T>
void HeapSort(T A[],int n){
	CreateHeap(A,n);
	for(int i = n-1 ;i > 0 ; i--){
		swap(A[0],A[i]);
		AdjustDown(A,0,i-1);
	}
}

int main()
{
	int A[7] = {99,36,68,72,12,48,02};
	HeapSort(A,7);
	return 0;
}