19.cpp

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

#include <iostream>
#include <stack>
#include <ctime>
#include <algorithm>
using namespace std;
//*********************
template <class T>
class Sort {
public:
	Sort () {}
	~Sort () {}

	static void BubbleSort( T array[], long size );
	static void InsertSort( T array[], long size );
	static void QuickSort1( T array[], long llimit, long rlimit );
	static void QuickSort2( T array[], long left, long right);
	static void QuickSort_Stack1( T array[], long llimit, long rlimit );
	static void QuickSort_Stack2( T array[],  long left, long right );
	static void SelectSort( T array[], long size );
	static void ShellSort( T array[], long size );
	static void StaticSort ( T array[], long size );
	static void HeapSort ( T array[], long size );
  
	static void Swap ( T& ele1, T& ele2 );
	static void Show ( T& ele );

	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>::Show( T& ele ) {
	cout << ele << ' ';
} 
//------------------------------------------------------------


//冒泡法排序
template <class T>
void Sort<T>::BubbleSort( T array[], long size ) {
	
	T temp;
	long last = size - 1;
	bool sorted = true;

	do {
		sorted = true;
		for (long i = 0; i < last; i++) {

			if (array[i] > array[i + 1]) {	
				temp = array[i];
				array[i] = array[i + 1];
				array[i + 1] = temp;
				sorted = false;
			}

		}

		last--;
	} while (!sorted);

}

//插入法排序
template <class T>
void Sort<T>::InsertSort( T array[], long size ) {

	T cVal;		// current value being examined
	
	for (long i = 1; i < size; i++) {

		cVal = array[i];
		for (long n = i - 1; n >= 0 && cVal < array[n]; n--) {
			array[n + 1] = array[n];
		}

		array[n + 1] = cVal;

	}	

}

//快速排序
template <class T>
void Sort<T>::QuickSort1( T array[], long llimit, long rlimit ) {

	long left = llimit;
	long right = rlimit;
	long pivot = ( left + right ) / 2;	
	T median = array[pivot];


	do {
		while ((array[left] < median) && ( left < rlimit )) {
			left++;
		}
		while ((median < array[right]) && (right > llimit )) {
			right--;
		}
		if ( left <= right ) {
			Swap ( array[left], array[right] ); 
			left++;
			right--;
		}
	} while ( left <= right );


	if ( llimit < right ) {
		QuickSort1(array, llimit, right );
	}


	if ( left < rlimit ) {
		QuickSort1(array, left, rlimit );
	}

}
//*
template <class T>
void Sort<T>::QuickSort2( T array[], long left, long right ) {
	if ( left < right ) 
	{
		T pivot = array[left];
		long i = left, j = right;
		long pivotpos;
		
		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;
		pivotpos = i;
		
		QuickSort2( array, left, pivotpos - 1 );
		QuickSort2( array, pivotpos + 1, right );	
	}
}
//快速排序堆栈法
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>::SelectSort( T array[], long size ) {
	
	T temp;
	long min;
	
	for (long i = 0; i < size - 1; i++) {
		min = i;
		
		for (long n = i + 1; n < size; n++) {
			if (array[n] < array[min]) 
				min = n;
			
		}
		if (min != i)
			Swap( array[min], array[i] );
	}
}

//希尔排序的算法
template <class T> 
void Sort<T>::ShellSort ( T array[], long size ) {
    long gap = size / 2;
    /* gap 是子序列间隔*/			
    while ( gap ) {		        
		/*一趟直接插入排序*/
		for ( long i = gap; i < size; i++ ) {
			T temp = array[i];	
			long j = i;
			while ( j >= gap && temp < array[j-gap] ) {
				array[j] = array[j-gap];
				j -= gap;
			}
			array[j] = temp;				
		}
		gap /= 2;//修改
    }
}

template <class T> 
void Sort<T>::StaticSort ( T array[], long size ) {
	int* index = new int[size];
	for ( long i = 0; i < size; i++ ) 
		index[i] = i;

	//1.以选择排序为基本排序方法
	/*
	for ( i = 0; i < size - 1; i++ ) {
		long min = i;
		for ( long j = i + 1; j < size; j++ )
			if ( array[index[min]] > array[index[j]] )
				min = j; 
		if ( min != i )
			Swap( index[i], index[min] );
	}
	*/

	//2.以快速排序为基本排序方法

	//3.堆排
	/*从currentPos位置开始将数组转换成堆*/
	long currentPos = ( size - 2 ) / 2; 
	long EndofHeap = size - 1;
	for ( i = currentPos; i >= 0; i-- ) {
		long current = i; long child = 2 * i + 1;
		long tmp_index = index[i];
		while ( child <= EndofHeap ) {
			if (child < EndofHeap && array[index[child]] < array[index[child + 1]] ) 
				child++;
			if ( array[tmp_index] >= array[index[child]]) break;
			else {
				index[current] = index[child];
				current = child; child = 2 * child + 1;
			}
		}
		index[current] = tmp_index;
	}
	//堆顶最大顶点与堆最后元素交换并重新调整堆
	for ( i = size - 1; i > 0; i-- ) {
		//Swap ( index[0], index[i]);
		index[0] += index[i]; index[i] = index[0] - index[i]; index[0] -= index[i];
		EndofHeap--;

		long current = 0; long child = 1;
		long tmp_index = index[0];
		while ( child <= EndofHeap ) {
			if (child < EndofHeap && array[index[child]] < array[index[child + 1]] ) 
				child++;
			if (array[tmp_index] >= array[index[child]]) break;
			else {
				index[current] = index[child];
				current = child; child = 2 * child + 1;
			}
		}
		index[current] = tmp_index;
	}

	for ( i = 0; i < size; i++ )
		cout << array[index[i]] << ' ';
	delete []index;
}

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 size = 5;
int* A = new int [size];
void justin_rand() {
	srand(time(0));
	for (long  i = 0; i < size; i++ ) {
		A[i] = rand() % 100 + 100;
	}	
}

int main() {
	/*
	
	long  time1, time2;
	
	int n = 4;
	while (n) {
		switch ( n) {
		case 1:
			justin_rand();
			time (&time1);
			Sort<int>::ShellSort (  A, size ); 
			time (&time2);
			cout << "ShellSort " << time2 - time1 << endl;
			break;
		case 2:
			justin_rand();
			time (&time1);
			Sort<int>::QuickSort1 (A, 0, size - 1);
			time (&time2);
			cout << "QuickSort1 " << time2 - time1 << endl;
			break;
		case 3:
			justin_rand();
			time (&time1);
			Sort<int>::HeapSort ( A, size ); 
			time (&time2);
			cout << "HeapSort " << time2 - time1 << endl;
			break;
		case 4:
			
			justin_rand();
			time (&time1);
			Sort<int>::StaticSort ( A, size ); 
			time (&time2);
			cout << "StaticSort " << time2 - time1 << endl;
			
			break;
		}
		n--;
	}
	*/
	justin_rand();
	for (long  i = 0; i < size; i++ ) {
		cout << A[i] << ' ';
	}
	cout << endl; 
    Sort<int>::StaticSort (A, size);
	//for_each ( A, A + size, Sort<int>::Show ); 
	cout << endl;
	getchar();
	
	
	return 0;
}
/*
	Sort<int>::QuickSort1 (A, 0, size - 1);
	for_each ( A, A + size, Sort<int>::Show ); 
	cout << endl;

	Sort<int>::QuickSort2 (A, 0, size - 1);
	for_each ( A, A + size, Sort<int>::Show ); 
	cout << endl;

	Sort<int>::QuickSort_Stack1 ( A, 0, size - 1);
	for_each ( A, A + size, Sort<int>::Show ); 
	cout << endl;

	Sort<int>::QuickSort_Stack2 (  A, 0, size - 1);
	for_each ( A, A + size, Sort<int>::Show ); 
	cout << endl;

	Sort<int>::HeapSort ( A, size );
	for_each ( A, A + size, Sort<int>::Show ); 
	cout << endl;

	Sort<int>::ShellSort (  A, size );
	for_each ( A, A + size, Sort<int>::Show );
	cout << endl;

	Sort<int>::StaticSort ( A, size );
	cout << endl;

	Sort<int>::SelectSort( A, size );
	for_each ( A, A + size, Sort<int>::Show );
	cout << endl;

	Sort<int>::BubbleSort( A, size );
	for_each ( A, A + size, Sort<int>::Show );
	cout << endl;
	*/