用冒泡，选择，插入，折半快排，希尔方法实现排序.cpp

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

#include <iostream>
#include <stack>
#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 SelectSort( T array[], long size );
	static void ShellSort( T array[], long size );

	static void Swap ( T& ele1, T& ele2 );
};
//-----------------------------------------------------------
template <class T>
void Sort<T>::Swap ( T& ele1, T& ele2 ) {
	T tmp = ele1;
	ele1 = ele2;
	ele2 = tmp;
}


//冒泡法排序
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;		 
	
	for (long i = 1; i < size; i++) {

		cVal = array[i];

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

		array[j+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++;
		}

		while ( median < array[right] ) {
			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>::SelectSort( T array[], long size ) {
	
	long min;
	for (long i = 0; i < size - 2; i++) {
		min = i;
		
		for (long j = i + 1; j < size; j++) {

			if (array[j] < array[min]) 
				min = j;
		}

		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;  //修改
    }
}

//******************************************************
int main() {

	Sort<int> func;

    cout<<"using BubbleSort()..."<<endl;
	int a[5] = {2,5,3,4,1};
	for (int i = 0; i < 5; i++) cout<<a[i]<<"   ";
	cout<<endl; 
	func.BubbleSort(a,5);
	for ( i = 0; i < 5; i++) cout<<a[i]<<"   ";
	cout<<endl; 

	cout<<"using InsertSort()..."<<endl;
	int b[5] = {2,5,3,4,1};
	for ( i = 0; i < 5; i++) cout<<b[i]<<"   ";
	cout<<endl; 
	func.InsertSort(b,5);
	for ( i = 0; i < 5; i++) cout<<b[i]<<"   ";
	cout<<endl;

    cout<<"using QuickSort1()..."<<endl;
	int c[5] = {2,5,3,4,1};
	for ( i = 0; i < 5; i++) cout<<c[i]<<"   ";
	cout<<endl; 
	func.QuickSort1(c,0,4);
	for ( i = 0; i < 5; i++) cout<<c[i]<<"   ";
	cout<<endl;

    cout<<"using QuickSort2()..."<<endl;
	int d[5] = {2,5,3,4,1};
	for ( i = 0; i < 5; i++) cout<<d[i]<<"   ";
	cout<<endl; 
	func.QuickSort2(a,0,4);
	for ( i = 0; i < 5; i++) cout<<d[i]<<"   ";
	cout<<endl;
	
    cout<<"using SelectSort()..."<<endl;
	int e[5] = {2,5,3,4,1};
	for ( i = 0; i < 5; i++) cout<<e[i]<<"   ";
	cout<<endl; 
	func.SelectSort(e,5);
	for ( i = 0; i < 5; i++) cout<<e[i]<<"   ";
	cout<<endl;

	cout<<"using ShellSort()..."<<endl;
	int f[5] = {2,5,3,4,1};
	for ( i = 0; i < 5; i++) cout<<f[i]<<"   ";
	cout<<endl; 
	func.ShellSort(f,5);
	for ( i = 0; i < 5; i++) cout<<f[i]<<"   ";
	cout<<endl;
	 

	return 0;
}