complexsort.h

该压缩文件夹内有诸多常用算法和数据结构的c++模板编程实现

#ifndef	COMPLEXSORT_H
#define COMPLEXSORT_H
#include<iostream.h>
#include"lQueue.h"
template<class T>
class complexSort
{
private:
	void swap(T& a,T& b)
	{
		T tmp=a;
		a=b;
		b=tmp;
	}
	void changeToHeap(T data[],int n)
	{
		if(n>1)
		{
			changeToHeap(data,n-1);
			for(int i=n;i>1;i=i/2)
				if(data[i-1]>data[i/2-1])
					swap(data[i-1],data[i/2-1]);
		}
	}
	void recoverHeap(T data[],int n)
	{
		T tmp;
		for(int i=1;2*i<=n;)
			if(data[i-1]<data[2*i-1] && (2*i==n || data[2*i-1]>=data[2*i]))
			{
				tmp=data[i-1];
				data[i-1]=data[2*i-1];
				data[2*i-1]=tmp;
				i=2*i;
			}
			else if(data[i-1]<data[2*i] && data[2*i-1]<=data[2*i])
			{
				tmp=data[i-1];
				data[i-1]=data[2*i];
				data[2*i]=tmp;
				i=2*i+1;
			}
			else	break;
	}
	void merge(T data[],int f1,int l1,int f2,int l2)
	{
		T tmp[10];
		int k,i,j;
		for(k=0,i=f1,j=f2;i<=l1&&j<=l2;k++)
			if(data[i]<=data[j])
			{
				tmp[k]=data[i];
				i++;
			}
			else
			{
				tmp[k]=data[j];
				j++;
			}
		for(1;i<=l1;i++,k++)
			tmp[k]=data[i];
		for(1;j<=l2;j++,k++)
			tmp[k]=data[j];
		for(i=0;i<k;i++,f1++)
			data[f1]=tmp[i];
	}
public:
	void ShellSort(T data[],int n)
	{
		int inc[20],h,i,hcnt,j,k;
		for(h=1,i=0;h<n;i++)
		{
			inc[i]=h;
			h=3*h+1;
		}
		for(i--;i>=0;i--)
		{
			h=inc[i];
			for(hcnt=0;hcnt<h;hcnt++)
				for(j=hcnt+h;j<n;j+=h)
				{
					T tmp=data[j];
					for(k=j-h;k>=0&&data[k]>tmp;k-=h)
						data[k+h]=data[k];
					data[k+h]=tmp;
				}
		}
	}
	void heapSort(T data[],int n)
	{
		changeToHeap(data,n);
		for(int i=n-1;i>=1;i--)
		{
			swap(data[i],data[0]);
			recoverHeap(data,i);
		}
	}
	void quickSort(T data[],int first,int last)
	{
		if(last>first)
		{
			int lower=first,upper=last+1;
			while(1)
			{
				for(lower++;lower<last&&data[lower]<=data[first];lower++);
				for(upper--;upper>first&&data[upper]>=data[first];upper--);
				if(upper>lower)
					swap(data[lower],data[upper]);
				else
				{
					swap(data[first],data[upper]);
					break;
				}
			}
			quickSort(data,first,upper-1);
			quickSort(data,upper+1,last);
		} 
	}
	void mergeSort(T data[],int first,int last)
	{
		if(last>first)
		{
			mergeSort(data,first,first+(last-first)/2);
			mergeSort(data,first+(last-first)/2+1,last);
			merge(data,first,first+(last-first)/2,first+(last-first)/2+1,last);
		}
	}
	void radixSort(T data[],int n)
	{
		lQueue<T> q[10];
		int i,j,k,m;
		for(i=10,j=1;1;i*=10,j*=10)
		{
			for(k=0;k<n;k++)
				q[data[k]%i/j].enqueue(data[k]);
			if(q[0].size()==n)
				break;
			for(m=k=0;k<10;k++)
				while(!q[k].isEmpty())
					data[m++]=q[k].dequeue();
		}
	}
	void printVector(T data[],int n)
	{
		for(int i=0;i<=n-1;i++)
			cout<<data[i]<<" ";
		cout<<endl;
	}
};
#endif