123.cpp

书中共介绍了四类排序函数：插入排序、起泡排序、选择排序、快速排序。我们需要建立一个无序随机序列

#include <iostream.h>//第四章
#include <assert.h>
#include "tou.h"
#include<string.h>
#include <ctime>
#include <stdlib.h> 
unsigned comparecount0=0,movecount0=0;
unsigned comparecount1=0,movecount1=0;
unsigned comparecount2=0,movecount2=0;
unsigned comparecount3=0,movecount3=0;
template <class T>
class vector
{
public:
		vector();
		vector(unsigned numElements);
		vector(unsigned numElements,T initValue);
		vector(const vector<T>&source);
		virtual~vector();
		//通过下标访问元素
		T& operator[](unsigned index)const;
		vector<T>& operator=(const vector<T>&);
		unsigned length()const;
		unsigned setSize(unsigned numOfElements);
		unsigned setSize(unsigned numOfElements,T initValue);
protected:
		T *data;
		unsigned size;
};
template<class T>vector<T>::vector(unsigned num)
:size(num)
{
	data=new T[size];
	assert(data!=0);
}
template<class T>vector<T>::vector(unsigned num,T v)
:size(num)
{
	data=new T[size];
	assert(data!=0);
	for(int i=0;i<size;i++)
		data[i]=v;
}
template<class T>vector<T>::vector(const vector<T>&s)
:size(s.size)
{
	data=new T[size];
	assert(data!=0);
	for(int i=0;i<size;i++)
		data[i]=s.data[i];
}
template<class T>vector<T>::vector()
:size(20)
{
	data=new T[size];
	data[i]='/o';
}
template<class T>vector<T>::~vector()
{
	delete[]data;
	data=0;
	size=0;
}
template<class T>T&vector<T>::operator [](unsigned index)const
{
	assert(index<size);
	return data[index];
}
template<class T>unsigned vector<T>::length()const
{
	return size;
}
template<class T>unsigned vector<T>::setSize(unsigned num)
{
	if(size!=num)
	{
		T*np=new T[num];
		assert(np!=0);
		unsigned n=num<=size?num:size;
		for(int i=0;i<n;i++)
			np[i]=data[i];
		delete []data;
		size=num;
		data=np;
	}
	return size;
}
template<class T>vector<T>&vector<T>::operator =(const vector<T>&right)
{
	if(size!=right.size)
	{
		T*np=new T[right.size];
		assert(np!=0);
		delete[]data;
		size=right.size;
		data=np;
	}
	for(int i=0;i<size;i++)
		data[i]=right.data[i];
	return *this;
}
void wordLengthFreq(vector<int>&counts)
{
	const int lengthmax=counts.length();
	int len;
	string word;
	while(cin>>word)
		if ((len=word.length())<lengthmax)
			counts[len]++;
		else 
			counts[0]++;
}//对不同长度的单词作计数
/////////////////////////////////////////////////////////////
template <class T>
class boundedVector:public vector<T>
{//定界向量
	public:
		boundedVector(int low,int high);
		boundedVector(int low,int high,T&initValue);
		boundedVector(const boundedVector<T>&source);
		T&operator[](int index)const;
		int lowerBound()const;
		int upperBound()const;
	protected:
		int lowbound;
};
template<class T>boundedVector<T>::boundedVector(int low,int high)
:lowbound(low),vector<T>(high-low+1)
{
	assert(low<=high);
}
template<class T>boundedVector<T>::boundedVector(int low,int high,T&init)
:lowbound(low),vector<T>(high-low+1,init)
{
	assert(low<=high);
}
template<class T>boundedVector<T>::boundedVector(const boundedVector<T>&source)
:lowbound(low),vector<T>(high-low+1,init)
{}
template<class T>T&boundedVector<T>::operator[](int index)const
{
	return vector<T>::operator[](index-lowbound);
}
template<class T>int boundedVector<T>::lowerBound()const
{
	return lowbound;
}
template<class T>int boundedVector<T>::upperBound()const
{
	return lowerbound+size-1;
}
/*void letOccurs(boundedVector<int>&counts,const string & text)
{
	assert(counts.lowerBound()=='a');
	assert(counts.upperBound()=='z');
	for(int i=0;text[i]!='/0';i++)
	{
		char c=text[i];
		if(isupper(c))c=tolower(c);
		if(islower(c))counts[c]++;
	}
}
void computeWordOccurrences()
{//建立计数器向量
	bouundedVector<int>counts('a','z',0);
	string word;
	//读入和计数
	while(cin>>word)
		letterOccurs(counts,word);
	//输出结果
	for (char c='a';c<='z';c++)
		cout<<"letter"<<c<<"occurrences"
		    <<counts[c]<<"times"<<'\n';
}*/
////////////////////////////////////////////////////////////////////////////////
template<class E,class T>
class enumVector:public vector<T>
{//枚举向量
public:
	//构造
	enumVector(E max);
	enumVector(const enumVector &v);
	//指标操作
	T&operator [](E index);
};
template<class E,class T>
enumVector<E,T>::enumVector(E max):vector<T>(1+int(max))
{}
template<class E,class T>
enumVector<E,T>::enumVector(const enumVector<E,T>&source)
:vector<T>(source)
{//复制构造函数
}
template <class E,class T>T&
enumVector<E,T>::operator [](E index)
{//简单的进行类型转换
	return vector<T>::operator[](int(index));
}
///////////////////////////////////////////////////////////////////////
template<class T>class orderedVector
{
public:
	orderedVector();
	orderedVector(const orderedVector<T>&v);
	T&operator[](unsigned int index)const;
	void add(T value);
	void deleteAllValues();
	int includes (T value)const;
	int isEmpty()const;
	void remove(T value);
	unsigned int binarySearch(T value);
private:
	vector<T> data;
};
template<class T>
void orderedVector<T>::deleteAllValues()
{
	data.setSize(0);
}
template<class T>int orderedVector<T>::isEmpty()const
{
	return data.length()==0;
}
template<class T>
unsigned int orderedVector<T>::binarySearch(T)
{
	unsigned int low=0;
	unsigned int high=data.length();
	while(low<high)
	{
		unsigned int mid=(low+high)/2;
		if(data[mid]==value)return mid;
		else if(data[mid]<value)
			low=mid+1;
		else high=mid;
	}
	return low;
}
template<class T>
int orderedVector<T>::includes(T value)const
{
	unsigned int index=binarySearch(value);
	//找到则返回1
	if ((index<data.length())&&(value==data[index]))
		return 1;
	return 0;
}
template<class T>
void orderedVector<T>::add(T value)
{
	unsigned int max=data.length;
	unsigned int index=binarySearch(value);
	data.setSize(max+1);
	for (unsigned int I=max;I>index;I--)
		data[I]=data[I-1];
	data[index]=value;
}
template <class T> void orderedVector<T>::remove(T value)
{
	unsigned int max=data.length();
	unsigned int index=binarySearch(value);
	
	for(unsigned int I=index;I<max;I++)
		data[I]=data[I+1];
	data.setSize(max-1);
}
/////////////////////////////////////////////////////////////////////////////////////
template <class T>class matrix
{
public:
	matrix(unsigned numberOfRows,unsigned numberOfColumns);
	matrix(unsigned numberOfRows,unsigned numberOfColumns,T initialValue);
	~matrix();
	vector<T>&operator[](unsigned index)const;
	int numberRows()const;
	int numberColumns()const;
private:
	vector<vector<T>*>rows;
};
template<class T>matrix<T>::matrix
(unsigned numOfRows,unsigned numOfCols):rows(numOfRows)
{
	for(unsigned i=0;i<numOfrows;i++)
	{
		rows[i]=new vector<T>(numOfCols);
		assert(rows[i]!=0);
	}
}
template<class T>matrix<T>::matrix
(unsigned numOfRows,unsigned numOfCols,T init):rows(numOfRows)
{
	for(unsigned i=0;i<numOfRows;i++)
	{
		rows[i]=new vector<T>(numOfCols,init);
		assert(rows[i]!=0);
	}
}
template<class T>matrix<T>::~matrix()
{
	unsigned max=rows.length(),i;
	vector<T>*p;
	for(i=0;i<max;i++)
	{
		p=rows[i];
		rows[i]=0;
		delete p;
	}
}
template<class T>int matrix<T>::numberRows()const
{
	return rows.lenth();
}
template<class T>int matrix<T>::numberColumns()const
{
	return rows[0]->length();
}
template<class T>vector<T>&matrix<T>::operator[]
(unsigned index)const
{
	return *rows[index];
}
template<class T>matrix<T>operator*
(const matrix<T>&left,const matrix<T>&right)
{
	int n=left.numberRows(),m=left.numberColumns(),p=right.numberColumns();
	int i,j,k;
	assert(m==right.numberRows());
	matrix<T>res(n,p);
	for(i=0;i<n;i++)
		for(j=0;j<p;j++)
		{
			for(k=0;k<m;k++)
				res[i][j]+=left[i][k]*right[k][j];
		}
		return res;
}
//////////////////////////////////////////////////////////////////////////////////////////
template<class T>class iterator
{
public:
	virtual int init()=0;
	virtual int operator!()=0;
	virtual T operator()()=0;
	virtual int operator++()=0;
	virtual void operator=(T newValue)=0;
};
template<class T>class vectorIterator:public iterator<T>
{
public:
	vectorIterator(vector<T>&);
	vectorIterator(const vectorIterator &);
	virtual int init();
	virtual T operator()();
	virtual int operator!();
	virtual int operator++();
	virtual void operator=(T newValue);
	int operator--();
	int key();
protected:
	unsigned currentKey;
	vector<T>& data;
};
template<class T>vectorIterator<T>::vectorIterator
(vector<T>&v):data(v)
{
	init();
}
template<class T>int vectorIterator<T>::init()
{
	currentKey=0;
	return operator!();
}
template<class T>vectorIterator<T>::vectorIterator(const vectorIterator<T>&x)
:data(x.data),currentKey(x.currentKey)
{}
template<class T>int vectorIterator<T>::operator !()
{
	return cuurentKey<data.length();
}
template<class T>int vectorIterator<T>::operator ++()
{
	currentKey++;
	return operator!();
}
template<class T>T vectorIterator<T>::operator ()()
{
	return data[currentKey];
}
template<class T>void vectorIterator<T>::operator =(T newValue)
{
	data[currentKey]=newValue;
}
template<class T>int vectorIterator<T>::operator --()
{
	if(currentKey>0)currentKey--;
	return operator!();
}
template<class T>int vectorIterator<T>::key()
{
	return currentKey;
}
////////////////////////////////////////////////////////////////////////////////
template<class T>class orderedVectorIterator:public vectorIterator<T>//排序向量遍历器
{
public:
	orderedVectorIterator(orderedVector<T>&x);
};
template<class T>orderedVectorIterator<T>::orderedVectorIterator(orderedVector<T>&x)
:vectorIterator<T>(x.data)
{}
//////////////////////////////////////////////////////////////////////////////////
///向量的排序
template<class T>void insertionSort(vector<T>& vec)//插入排序
{
	int n=vec.length(),j,next;
	T temp;
	for(next=1;next<n;next++)
	{
		comparecount0++;
		temp=vec[next];
		for(j=next-1;j>=0&&temp<vec[j];j--)
		{
			comparecount0=comparecount0+2;
			vec[j+1]=vec[j];
			movecount0++;
            vec[j+1]=temp;
			movecount0++;
		}
	}
}
template<class T>void swap(vector<T>& vec,int i,int j)//起泡排序
{
	T temp=vec[i];
	vec[i]=vec[j];
	vec[j]=temp;
}

template<class T>void bubbleSort(vector<T>& vec)
{
	int top,i;
	for(top=vec.length()-1;top>0;top--)
	{
		comparecount1++;
		for(i=0;i<top;i++)
		{
			comparecount1++;
			if(vec[i+1]<vec[i])
			{
				movecount1=movecount1+3;
				swap(vec,i+1,i);
			}
		}
	}
}


template<class T>void selectionSort(vector<T>& vec)//选择排序
{
	int largest,top,j;
	for(top=vec.length()-1;top>0;top--)
	{
		comparecount2++;
		for(largest=0,j=1;j<=top;j++)
		{
             comparecount2++;
			if(vec[largest]<vec[j])
			{
				comparecount2++;
				movecount2++;
				largest=j;
			}
		}
		if(top!=largest)
		{
			comparecount2++;
			movecount2=movecount2+3;
			swap(vec,top,largest);
		}
	}
}

template<class T>int partition(vector<T>& v,int low,int high)//快速排序法
{
	T pivot=v[low];
	while(low<high)
	{
		comparecount3++;
		while(low<high&&v[high]>=pivot)
		{
			high--;
			comparecount3=comparecount3+2;
		}
			if(low<high)
			{
				v[low]=v[high];
				movecount3++;
				comparecount3++;
				low++;
			}
		while(low<high && v[low]<=pivot)
		{
			low++;
			comparecount3=comparecount3+2;
		}
		if(low<high)
		{
			v[high]=v[low];
            movecount3++;
			comparecount3++;
			high--;
		}
	}
	v[high]=pivot;
	return high;
}
template<class T>void quickSort(vector<T>& v,int low,int high)
{
	if(low<high)
	{
		comparecount3++;
		int mindex=partition(v,low,high);
		quickSort(v,low,mindex-1);
        quickSort(v,mindex+1,high);
	}
}

template<class T>void quickSort(vector<T>& v)
{
    	quickSort(v,0,v.length()-1);
}
//////////////////////////////////////////////////////////////////
//clock
clock_t clock( void );
///////////////////////////////////////////////////////////////////
void main()
{

	//随机数产生
	char le[20];
	long length;
	for(int zz=0;;zz++)
	{
		cout<<"请输入所要建立的向量的长度length:(不小于1000)"<<'\n';
	    cin>>le;
		length=atoi(le);
		if(!(length>=1000))
		{}
		else
		{
			cout<<"运行中，请稍等……"<<endl;
			break;
		}

	}
	srand( (unsigned)time( NULL ) );
	vector<int>    v(length),v1(length),v2(length),v3(length),v4(length);  
	for (int k=0;k<length;k++)
	{v[k]=rand();}
	 v1=v;	 v2=v;	 v3=v;	 v4=v;
	
    clock_t start, finish;
    double duration;
//插入排序
    start=clock();
    insertionSort(v1);
    finish=clock();   
    duration=(double)(finish-start) / CLOCKS_PER_SEC;  
    cout<<"插入排序的赋值次数、比较次数分别为:"<<movecount0<<";"<<comparecount0<<'\n';
    cout<<"插入排序所用的时间为:"<<duration<<'\n';
//起泡排序
    start=clock();
    bubbleSort(v2);
    finish=clock();
    duration=(double)(finish-start) / CLOCKS_PER_SEC;
    cout<<"起泡排序的赋值次数、比较次数分别为:"<<movecount1<<";"<<comparecount1<<'\n';
	cout<<"起泡排序所用的时间为:"<<duration<<'\n';	
//选择排序	
    start= clock();
    selectionSort(v3);
    finish= clock();
    duration= (double)(finish- start) / CLOCKS_PER_SEC; 
	cout<<"选择排序的赋值次数、比较次数分别为:"<<movecount2<<";"<<comparecount2<<'\n';
	cout<<"选择排序所用的时间为:"<<duration<<'\n';
//快速排序
    start=clock();
    quickSort(v4);
    finish=clock();
    duration=(double)(finish-start) / CLOCKS_PER_SEC; 	
    cout<<"快速排序的赋值次数、比较次数分别为:"<<movecount3<<";"<<comparecount3<<'\n';
	cout<<"快速排序所用的时间为:"<<duration<<'\n';
}