quicksort.h

各种排序算法BubbleSort、DichotomySort、HeapSort、InsertSort、MergeSort、QuickSort、ShellSort、

#ifndef QUICKSORT_H
#define QUICKSORT_H
#include<iostream.h>

template<class Elem>
class QuickSort:public sort<Elem>
{
	public:
		QuickSort(){compareNum = 0 ; moveNum = 0 ;};
		virtual void Sorts(Elem Array[], int left , int right , int n);////
		void print_q(Elem Array[], int n);
	private:
		int compareNum;/////比较次数
		int moveNum;/////移动次数
		int selectPivot(int left , int right);/////选择轴值，返回轴值下标
		int partition(Elem Array[], int left, int right,int n);////分割，返回轴值位置
		///int doSort(Elem Array[] , int left , int right);
};
template<class Elem>
void QuickSort<Elem>::Sorts(Elem Array[], int left, int right , int n)
{
	if (right <= left)
		return;		
	int pivot = selectPivot(left, right);
	swap(Array, pivot, right);
	moveNum+=3;
	pivot=partition(Array, left, right, n);
	Sorts(Array, left, pivot-1,n);
	Sorts(Array, pivot+1, right,n);
}
template <class Elem>
int QuickSort<Elem>::selectPivot(int left , int right)
{
	return (left + right) / 2;
}
template <class Elem>
int QuickSort<Elem>::partition(Elem Array[], int left, int right,int n)
{
	Elem temp;
	int i = left;
	int j = right;
	temp = Array[j];			
	while (i != j)
	{
		
		while ( (compare(Array[i], temp) == -1) && j > i )
		{	
			i++;
			compareNum++;
		}
		compareNum++;		

		if (i < j)
		{
			Array[j] = Array[i];
			j--;
			moveNum++;
		}		
		
		while ( (compare(Array[j], temp) == 1) && j > i )
		{
			j--;
	     	compareNum++;
		}
		compareNum++;
		if (i < j)
		{
			Array[i] = Array[j];
			i++;
			moveNum++;
		}
	}
	Array[i] = temp;
	moveNum++;
	return i; 
}
template<class Elem>
void QuickSort<Elem>::print_q(Elem Array[], int n)
{
	cout<<"         优化快速排序法         "<<endl;
	cout<<"++++++++++++++++++++++++++++++++"<<endl;
	cout<<"比较次数："<<compareNum<<endl;
	cout<<"移动次数："<<moveNum<<endl;
	//print(Array , n);
}
#endif