paixu.h

数据结构程序设计21

	}
		if(k!=i) Swap (list.Vector[i],list.Vector[k]);//交换
	return z;	
}



//二路归并的迭代的归并排序算法
template<class Type> int datalist<Type>::merge(datalist<Type> &initList,datalist<Type> &mergedList,const int l,const int m,const int n){
	//initList.Vector[l..m]与initList.Vector[m+1..n]是两个有序表,将这两个有序表归并成一个有序表mergedList.Vector[l..n]。
	int i=l,j=m+1,k=l;                        //i,j是两个表的检测指针,k是存放指针
    int z=0;                                  //z来计算每躺里两个有序发生的比较次数
	while(i<=m && j<=n)
	  {if(initList.Vector[i].getKey()<=initList.Vector[j].getKey())
	  {mergedList.Vector[k]=initList.Vector[i];i++;k++;}
	  else {mergedList.Vector[k]=initList.Vector[j];j++;k++;}
	  z++;
	  }
	 if(i<=m)
		 for(int n1=k,n2=i;n1<=n && n2<=m;n1++,n2++) mergedList.Vector[n1]=initList.Vector[n2];
	 else
		 for(int n1=k,n2=j;n1<=n && n2<=n;n1++,n2++) mergedList.Vector[n1]=initList.Vector[n2];
      
		 return z;

}


template<class Type> int datalist<Type>::MergePass(datalist<Type> &initList,datalist<Type> &mergedList,const int len){
	//一趟归并排序。将两个长度为len的有序子表(归并项)进行归并,结果放在表mergedList的相同位置.
	int i=0;
	int z=0,k=0,y=0,w=0;  //z来计算每躺里两个有序发生的比较次数,y来计算每躺里两个有序发生的比较次数
	                  //w为每趟的总的比较次数
	while(i+2*len<=initList.CurrentSize-1){
		z=merge(initList,mergedList,i,i+len-1,i+2*len-1);i+=2*len;
		k+=z;
	}     //对长度为len的子表两两归并,直到表中剩余元素不足2*len为止
	if(i+len<=initList.CurrentSize-1)
		y=merge(initList,mergedList,i,i+len-1,initList.CurrentSize-1);
	    //若仍有一个长度为len的子表,再做一次归并,后一子表的长度不足为len 
	else for(int j=i;j<=initList.CurrentSize-1;j++) mergedList.Vector[j]=initList.Vector[j];
         //若不能做归并,复制
	w=k+y;
	return w;
}

template<class Type> void datalist<Type>::MergeSort(datalist<Type> &list){
	int z,y=1;                                 //z来记录每躺比较次数
	ofstream out("迭代的归并排序.txt");
	datalist<Type> tempList(list.MaxSize);
	int len=1,j;
	tempList.CurrentSize=list.CurrentSize;
	while(len<list.CurrentSize){                  //归并排序
		
		z=MergePass(list,tempList,len);len*=2;     //一趟两路归并后归并项长度加倍
        cout<<"第"<<y<<"趟:";
		 out<<"第"<<y<<"趟:"; 
		 y++;
		for(j=0;j<tempList.CurrentSize;j++)                //输出每趟排序后的结果
		 {cout<<tempList.Vector[j].getKey()<<" ";
		  out<<tempList.Vector[j].getKey()<<" ";}         //把结果输入文本文件
		 cout<<"比较"<<z<<"次";
		 cout<<endl;
		 out<<"比较"<<z<<"次";
		 out<<endl;
		 
        z=MergePass(tempList,list,len); len*=2;
      	 cout<<"第"<<y<<"趟:";
		 out<<"第"<<y<<"趟:";
		 y++;
		 for(j=0;j<list.CurrentSize;j++)                    //输出每趟排序后的结果
		 {cout<<list.Vector[j].getKey()<<" ";
		   out<<list.Vector[j].getKey()<<" ";}              //把结果输入文本文件
		  cout<<"比较"<<z<<"次";
		 cout<<endl;
		 out<<"比较"<<z<<"次";
		 out<<endl;
	}

	//delete[] tempList;
}



//插入排序的折半插入排序
template<class Type> void datalist<Type>::BinaryInsertSort1(datalist<Type> &list){

	for(int i=1;i<list.CurrentSize;i++) {
	     BinaryInsert1(list,i); 
	}
}

template<class Type> void datalist<Type>::BinaryInsert1(datalist<Type> &list,int i){	
	int left=0,Right=i-1;Element<Type> temp=list.Vector[i];
	while(left<=Right){                               //利用折半查找插入位置
		int middle=(left+Right)/2;                     //取中点
		if(temp.getKey()<list.Vector[middle].getKey())  //插入值小于中点值
			Right=middle-1;                              //向左缩小区间
		else left=middle+1;                              //否则，向右缩小区间
	}
	for(int k=i-1;k>=left;k--) list.Vector[k+1]=list.Vector[k];    //成块移动空出插入位置
	list.Vector[left]=temp;                                        //插入
}


//插入排序的直接插入排序
template<class Type> void datalist<Type>::InsertionSort1(datalist<Type> &list){
	for(int i=1;i<list.CurrentSize;i++) 
	{ Insert1(list,i);

	}
}
template<class Type> void datalist<Type>::Insert1(datalist<Type> &list,int i){
	Element<Type> temp=list.Vector[i];int j=i;
	while(j>0 && temp.getKey()<list.Vector[j-1].getKey()){
		list.Vector[j]=list.Vector[j-1];j--;
	}
	list.Vector[j]=temp;
}


//插入排序的希尔排序
template<class Type> void datalist<Type>::Shellsort1(datalist<Type> &list){
   int gap=list.CurrentSize/2;               //增量的初始值
   while(gap){                              //循环条件是gap>=1
    ShellInsert(list,gap);                 //按增量gap划分子序列，分别进行插入排序
    gap=gap==2?1:(int)(gap/2);              //缩小增量gap
   }
}


template<class Type> void datalist<Type>::ShellInsert1(datalist<Type> &list,const int gap){
     for(int i=gap;i<list.CurrentSize;i++){            //各子序列轮流执行插入排序
        Element<Type> temp=list.Vector[i]; int j=i;       //暂存待插入对象
        while(j>=gap && temp.getKey()<list.Vector[j-gap].getKey()){
                               //当前元素比位于j-gap的元素小，则位于j-gap的元素后移
          list.Vector[j]=list.Vector[j-gap];j-=gap;      //后移到第j个位置,j指标前指
         }
         list.Vector[j]=temp;              //插入
      }
 }




//交换排序的起泡排序
template <class Type> void datalist<Type>::BubbleSort1(datalist <Type> &list){
	//对表list.Vector[0]到list.Vector[n-1]逐趟进行比较,遇到逆序即交换。n是表当前长度
	int pass=1;int exchange=1;    //当exchange为0则停止排序
	while(pass<list.CurrentSize && exchange){     //起泡排序趟数不超过n-1
	  BubbleExchange1(list,pass,exchange);
	  pass++;
	}
}

template <class Type> void datalist<Type>::BubbleExchange1(datalist <Type> &list,const int i,int &exchange){
	exchange=0;    //假定元素未交换
	for(int j=list.CurrentSize-1;j>=i;j--)
	{if(list.Vector[j-1].getKey()>list.Vector[j].getKey()){        //发生逆序
		 Swap(list.Vector[j-1],list.Vector[j]);exchange=1;}         //交换,做"发生了交换"标志
	} 

}


//选择排序的直接排序
template <class Type> void datalist<Type>::SelectSort1(datalist<Type> & list){
	//对表 list.vector[0]到 list.vector[n-1]进行排序，n表示当前长度。
	for (int i=0;i<list.CurrentSize-1;i++) 
	{SelectExchange1(list,i);
	}
}

template <class Type> void datalist<Type>::SelectExchange1(datalist<Type> & list,const int i){
	int k=i;  //在list.vector[i].key到list.vector[n-1].key中找具有最小关键码的对象
	for(int j=i+1;j<list.CurrentSize;j++)
	{if(list.Vector[j].getKey()<list.Vector[k].getKey()) k = j;//当前具最小关键码的对象
	}
		if(k!=i) Swap (list.Vector[i],list.Vector[k]);//交换
	
}



//二路归并的迭代的归并排序算法
template<class Type> void datalist<Type>::merge1(datalist<Type> &initList,datalist<Type> &mergedList,const int l,const int m,const int n){
	//initList.Vector[l..m]与initList.Vector[m+1..n]是两个有序表,将这两个有序表归并成一个有序表mergedList.Vector[l..n]。
	int i=l,j=m+1,k=l;     //i,j是两个表的检测指针,k是存放指针
 
	while(i<=m && j<=n)
	  {if(initList.Vector[i].getKey()<=initList.Vector[j].getKey())
	  {mergedList.Vector[k]=initList.Vector[i];i++;k++;}
	  else {mergedList.Vector[k]=initList.Vector[j];j++;k++;}
	  }
	 if(i<=m)
		 for(int n1=k,n2=i;n1<=n && n2<=m;n1++,n2++) mergedList.Vector[n1]=initList.Vector[n2];
	 else
		 for(int n1=k,n2=j;n1<=n && n2<=n;n1++,n2++) mergedList.Vector[n1]=initList.Vector[n2];
}


template<class Type> void datalist<Type>::MergePass1(datalist<Type> &initList,datalist<Type> &mergedList,const int len){
	//一趟归并排序。将两个长度为len的有序子表(归并项)进行归并,结果放在表mergedList的相同位置.
	int i=0;
	
	while(i+2*len<=initList.CurrentSize-1){
		 merge1(initList,mergedList,i,i+len-1,i+2*len-1);i+=2*len;
		
	}     //对长度为len的子表两两归并,直到表中剩余元素不足2*len为止
	if(i+len<=initList.CurrentSize-1)
		 merge1(initList,mergedList,i,i+len-1,initList.CurrentSize-1);
	 //若仍有一个长度为len的子表,再做一次归并,后一子表的长度不足为len 
	else for(int j=i;j<=initList.CurrentSize-1;j++) mergedList.Vector[j]=initList.Vector[j];
	//若不能做归并,复制
}     

template<class Type> void datalist<Type>::MergeSort1(datalist<Type> &list){
	datalist<Type> tempList(list.MaxSize);
	int len=1;
	tempList.CurrentSize=list.CurrentSize;
	while(len<list.CurrentSize){               //归并排序
        MergePass1(list,tempList,len);len*=2;       //一趟两路归并后归并项长度加倍
        MergePass1(tempList,list,len); len*=2;
	}

	//delete[] tempList;
}



//堆排序
template <class Type> int datalist<Type>::FilterDown (const int i,const int EndOfHeap,datalist<Type> &list){
	int z=0;
	int current=i;int child=2*i+1;                       //child是current的左子女位置
	int temp=list.Vector[i].getKey();                     //暂存子树根结点
	//cout<<"i="<<i<<" ";cout<<"child="<<child<<" ";cout<<"EndOfHeap="<<EndOfHeap<<" ";
	while(child<=EndOfHeap){
		if(child<EndOfHeap && list.Vector[child].getKey()<list.Vector[child+1].getKey())
		{child=child+1;                                    //让child指向两子女中的大者
          z++;
		}
		if(child<EndOfHeap && list.Vector[child].getKey()>=list.Vector[child+1].getKey())
		{z++;
		}
		if(temp>=list.Vector[child].getKey())                 //temp的关键码大则不做调整
		{   z++;
			break;
		}
		else {
			list.Vector[current]=list.Vector[child];             //current下降到子女位置
			current=child;child=2*child+1;
			z++;
		}
		
	}
	list.Vector[current].setKey(temp);                            //temp中暂存的元素放到合适位置
	return z;
}

template <class Type> void datalist<Type>::HeapSort (datalist<Type> & list) {
	ofstream out("堆排序.txt");int z,k=0;
	int j;
	for(int i=(list.CurrentSize-2)/2;i>=0;i--)
	{z=FilterDown (i,list.CurrentSize-1,list);                   //将表转换成堆
      for(j=0;j<list.CurrentSize;j++)        //输出每趟排序后的结果
	  {cout<<list.Vector[j].getKey()<<" ";
	   out<<list.Vector[j].getKey()<<" ";}
	    cout<<"比较"<<z<<"次";
	   out<<"比较"<<z<<"次";
		cout<<endl;
		out<<endl;
	}

	for(i=list.CurrentSize-1;i>=1;i--) {                          //对表排序
		
		Swap (list.Vector[0],list.Vector[i]);                      //交换
	    for(j=0;j<list.CurrentSize;j++)        //输出每趟排序后的结果
		 {cout<<list.Vector[j].getKey()<<" ";
		out<<list.Vector[j].getKey()<<" ";}
		   cout<<"交换"<<0<<"与"<<i<<"号元素";
		   out<<"交换"<<0<<"与"<<i<<"号元素";
		cout<<endl;
		out<<endl;
		z=FilterDown (0,i-1,list);                                //重建最大堆
        for(j=0;j<list.CurrentSize;j++)        //输出每趟排序后的结果
		 {cout<<list.Vector[j].getKey()<<" ";
		  out<<list.Vector[j].getKey()<<" ";}
		  cout<<"比较"<<z<<"次";
		  out<<"比较"<<z<<"次";
		cout<<endl;
		out<<endl;
	}
}




//堆排序
template <class Type> void datalist<Type>::FilterDown1(const int i,const int EndOfHeap,datalist<Type> &list){
	int current=i;int child=2*i+1;                               //child是current的左子女位置
	int temp=list.Vector[i].getKey();                            //暂存子树根结点
	while(child<=EndOfHeap){                                     //检查是否到最后位置
		if(child<EndOfHeap && list.Vector[child].getKey()<list.Vector[child+1].getKey())      
			child=child+1;                                         //让child指向两子女中的大者
		if(temp>=list.Vector[child].getKey()) break;               //temp的关键码大则不做调整
		else { 
			list.Vector[current]=list.Vector[child];
			current=child;child=2*child+1;                         //current下降到子女位置
		}
	}
	list.Vector[current].setKey(temp);                             //temp中暂存的元素放到合适位置
}

template <class Type> void datalist<Type>::HeapSort1(datalist<Type> & list) {
	for(int i=(list.CurrentSize-2)/2;i>=0;i--) FilterDown1(i,list.CurrentSize-1,list);       //将表转换成堆
	for(i=list.CurrentSize-1;i>=1;i--) {                                                    //对表排序
		Swap (list.Vector[0],list.Vector[i]);                                               //交换
		FilterDown1(0,i-1,list);                                                            //重建最大堆
	}
}