#include<stdlib.h>
#include<assert.h>
#include"Vector.h"
#include"Iterator.h"
#include"VectorIterator.h"
#include"orderdVector.h"
#include"orderedVectorIterator.h"
int cf,mf,bcf,bmf;

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)
{   cf=0;
    mf=0;
	int top,i;
	for (top=vec.length()-1;top>0;top--)
	{
		for(i=0;i<top;i++)
		{   cf++;
			if(vec[i+1]<vec[i])
			{
				swap(vec,i+1,i);
				mf=mf+3;
			}
		}
	}
}
template <class T>void insertionSort(vector<T>&vec)
{  
	cf=0;
    mf=0;
	int n=vec.length(),j,next;
	T temp;
	for (next =1;next<n;next++)
	{
		temp=vec[next];
		for(j=next-1;j>=0&&temp<vec[j];j--)		    
		{
			vec[j+1]=vec[j];
			cf++;
			mf++;
		}
		 vec[j+1]=temp;
		 mf++;
	}
}
template<class T>void selectionSort(vector<T>&vec)
{
	cf=0;
    mf=0;
	int largest,top,j;
	for(top=vec.length()-1;top>0;top--)
	{
		for(largest=0, j=1;j<=top;j++)
		{
			if(vec[largest]<vec[j])
			{
				largest=j;
				cf++;
			}
		}
		if(top!=largest)
		{
			swap(vec,top,largest);
			mf=mf+3;
		}
	}
}
template<class T>
int partition(vector<T>&v,int low,int high)
{    
	bcf=0;
    bmf=0;
	T pivot=v[low];
	while(low<high){
		while(low<high&&v[high]>=pivot)
		{
			bcf=bcf+2;
			high--;
		}
		if(low<high){
			bcf++;
			v[low]=v[high];
			bmf++;
			low++;
		}
		while(low<high&&v[low]<=pivot)
		{
			bcf=bcf+2;
			low++;
		}
		if (low<high){
			bcf++;
			v[high]=v[low];
			bmf++;
			high--;
	}
}
v[high]=pivot;
bmf++;
return high;
}
template<class T>void quickSort(vector<T>&v,int low,int high)
{   
	if (low>=high)
	{
		cf++;
		mf=mf;
		return;
	}
		cf++;
		mf=mf;
	int mIndex=partition(v,low,high);
	cf=cf+bcf;
	mf=mf+bmf;
	quickSort(v,low,mIndex-1);
	quickSort(v,mIndex+1,high);
}
    template<class T>void quickSort(vector<T>&v)
	{
		quickSort(v,0,v.length()-1);
	}
void main()
{   int kf=1,hfh=1;
	int geshu=0;
	int xff;
	char ckf,hkf;
	cout<<"你好，這里是插入、起泡、選擇、快速排序等算法的執(zhí)行效率比較。"<<endl;
	while(kf==1){
	do{

	cout<<"請(qǐng)確認(rèn)所要排序的隨機(jī)數(shù)的個(gè)數(shù)：";
	cin>>geshu;
	}while (geshu<=0);
	srand((unsigned)geshu);
	vector<int> fv(geshu);
	for(int i=0;i<geshu;i++)
		fv[i]=rand();
    cout<<"排序前的向量為："<<endl;
	for(unsigned j=0;j<fv.length();j++)
	{	if(j==0)cout<<"("<<j+1<<")"<<fv[j]<<"  ";	
	else if((j%6)==0)cout<<"("<<j+1<<")"<<fv[j]<<endl;
	 else cout<<"("<<j+1<<")"<<fv[j]<<"  ";

	}
	cout<<endl;
	hfh=1;
	while(hfh==1){

	do{
	cout<<"請(qǐng)選擇排序方法："<<endl;
	cout<<"1------------------------------插入排序"<<endl;
	cout<<"2------------------------------起泡排序"<<endl;
	cout<<"3------------------------------選擇排序"<<endl;
	cout<<"4------------------------------快速排序"<<endl;
	cin>>xff;
	}while (!(xff==1||xff==2||xff==3||xff==4));
	vector<int> cfv((unsigned)geshu);
	cfv=fv;
	if(xff==1){
		insertionSort(cfv);
		cout<<"插入排序后的結(jié)果："<<endl;
	for(unsigned j=0;j<cfv.length();j++)
	{	if(j==0)cout<<"("<<j+1<<")"<<cfv[j]<<"  ";	
	else if(((j%6)==0)||(j==cfv.length()-1))cout<<"("<<j+1<<")"<<cfv[j]<<endl;
	 else cout<<"("<<j+1<<")"<<cfv[j]<<"  ";

	}
		cout<<"插入排序的比較次數(shù)為："<<cf<<endl;
		cout<<"插入排序的移動(dòng)次數(shù)為："<<mf<<endl;
	}
	else if(xff==2)
	{   
		cfv=fv;
		bubbleSort(cfv);
				cout<<"起泡排序后的結(jié)果："<<endl;
	for(unsigned j=0;j<cfv.length();j++)
	{	if(j==0)cout<<"("<<j+1<<")"<<cfv[j]<<"  ";	
	else if(((j%6)==0)||(j==cfv.length()-1))cout<<"("<<j+1<<")"<<cfv[j]<<endl;
	 else cout<<"("<<j+1<<")"<<cfv[j]<<"  ";

	}

		cout<<"起泡排序的比較次數(shù)為："<<cf<<endl;
		cout<<"起泡排序的移動(dòng)次數(shù)為："<<mf<<endl;
	}
	else if(xff==3)
	{   
		cfv=fv;
		 selectionSort(cfv);
				cout<<"選擇排序后的結(jié)果："<<endl;
	for(unsigned j=0;j<cfv.length();j++)
	{	if(j==0)cout<<"("<<j+1<<")"<<cfv[j]<<"  ";	
	else if(((j%6)==0)||(j==cfv.length()-1))cout<<"("<<j+1<<")"<<cfv[j]<<endl;
	 else cout<<"("<<j+1<<")"<<cfv[j]<<"  ";

	}
	
		cout<<"選擇排序的比較次數(shù)為："<<cf<<endl;
		cout<<"選擇排序的移動(dòng)次數(shù)為："<<mf<<endl;
	}
	else if(xff==4)
	{
       	cfv=fv;
		 quickSort(cfv);
		
		cout<<"快速排序后的結(jié)果："<<endl;
	for(unsigned j=0;j<cfv.length();j++)
	{	if(j==0)cout<<"("<<j+1<<")"<<cfv[j]<<"  ";	
	else if(((j%6)==0)||(j==cfv.length()-1))cout<<"("<<j+1<<")"<<cfv[j]<<endl;
	 else cout<<"("<<j+1<<")"<<cfv[j]<<"  ";

	}
		cout<<"快速排序的比較次數(shù)為："<<cf<<endl;
		cout<<"快速排序的移動(dòng)次數(shù)為："<<mf<<endl;
		 cf=mf=0;
	}
       cout<<"你用其他的排序方法嗎？（Y/N）?";
	   cin>>hkf;
     if(hkf=='y'||hkf=='Y')hfh=1;
      else hfh=0;

	}
cout<<"你要再來(lái)新的數(shù)據(jù)比較？（Y/N）?";
cin>>ckf;
if(ckf=='y'||ckf=='Y')kf=1;
else kf=0;
}
}