用递归和非递归的方法实现堆排序.cpp

这个是我的大学作业哦 里面有些很经典的代码 出自清华大学的数据结构课本

#include <iostream>
#include <stack>
#include <ctime>
#include <algorithm>
using namespace std;
//*********************
template <class T>
class Sort {

public:
	Sort () {}
	~Sort () {}
	
	static void QuickSort_Stack1( T array[], long llimit, long rlimit );
	static void QuickSort_Stack2( T array[],  long left, long right );
	
	static void HeapSort ( T array[], long size );
	
	static void Swap ( T& ele1, T& ele2 );
	
	static void FileDown ( T array[], long i , long EndofHeap);
};
//------------------------------------------------------------------
template <class T>
void Sort<T>::Swap ( T& ele1, T& ele2 ) {
	T tmp = ele1;
	ele1 = ele2;
	ele2 = tmp;
}

//------------------------------------------------------------

template <class T>
void Sort<T>::QuickSort_Stack1( T array[], long llimit, long rlimit ) {
	typedef pair<long, long> stackNode;
	typedef stack<stackNode> Stack;
	
	Stack st;  
	T pivot;
	long bottom, top; 
	
	st.push(stackNode( llimit, rlimit ));
	
	while (!st.empty()) {
		bottom = st.top().first;
		top = st.top().second;
		st.pop();

		pivot = array[( bottom + top) / 2];

		long i = bottom, j = top;
		do {
			while ((array[i] < pivot) && ( i < top )) 
				i++;
			while ((pivot< array[j]) && (j > bottom )) 
				j--;


			if ( i <= j ){
				Swap ( array[i], array[j] );
				i++; j--;
			}
		} while ( i <= j );
	//*	
		if ( bottom < j) {
			st.push(stackNode( bottom, j));
		}
		
		if ( i < top ) {
			st.push(stackNode(i, top));
		}
	}
}


//*
template <class T>
void Sort<T>::QuickSort_Stack2 ( T array[], long left, long right ) {
	typedef pair <long , long> stackNode;
	typedef stack<stackNode> Stack;
	
	Stack st;
	st.push ( stackNode ( left, right ) );
	
	long bottom, top, i, j;
	T pivot;
//*	
	while ( !st.empty () ) {
		bottom = st.top().first;
		top = st.top().second;
		st.pop();
		
		pivot = array[bottom];
		i = bottom; j = top;
		while ( i < j ) {
			while ( ( i < j ) && ( array[j] >= pivot ))
				j--;
			if ( array[j] < pivot ) { array[i] = array[j]; i++; }
			//*
			while ( ( i < j ) && ( array[i] < pivot ))
				i++;
			if ( array[i] > pivot ) { array[j] = array[i]; j--; }
			
		}
  
		array[i] = pivot;
	                                              	/*先将元素多的半边压栈*/
		if ( ( i - 1 ) - bottom > top - ( i + 1 ) ) {
			if ( i - bottom > 1 )
				st.push ( stackNode( bottom, i - 1) );
			if ( top - i > 1 )
				st.push ( stackNode( i + 1, top) );
		}
		//-----------
		else {
			if ( top - i > 1 )
				st.push ( stackNode( i + 1, top) );
			if ( i - bottom > 1 )
				st.push ( stackNode( bottom, i - 1) );
		}
	}
}

//----------------------------------------------------------------------
template <class T> 
void Sort<T>::FileDown ( T array[], long i , long EndofHeap ) {
	long current = i;           long child = 2 * i + 1;
	T tmp = array[i];
	while ( child <= EndofHeap ) {
		if (child < EndofHeap && array[child] < array[child + 1] ) 
			child++;
		if (tmp >= array[child]) break;

		else {
			array[current] = array[child];
			current = child; child = 2 * child + 1;
		}
	}
	array[current] = tmp;
}
//*
template <class T> 
void Sort<T>::HeapSort ( T array[], long size ) {
	long currentPos = ( size - 2 ) / 2; 
	                                 /*从currentPos位置开始将数组转换成堆*/
	for ( long i = currentPos; i >= 0; i-- )
		FileDown (array, i, size - 1);
                                           //*
	for ( i = size - 1; i > 0; i--) {
		Swap ( array[0], array[i]);
		FileDown ( array, 0, i - 1);
	}

	
}

//********************************************************
int main() {
	Sort<int> func;
	
	int a[5] = {2,5,3,4,1};
	
	for (int i = 0; i < 5; i++) cout<<a[i]<<"   ";
	cout<<endl; 
	
	func.HeapSort(a,5);
	
	for ( i = 0; i < 5; i++) cout<<a[i]<<"   ";
	
	cout<<endl; 
	
	return 0;
	
}