cpp2.cpp

排序。。⑴直接插入排序； ⑵折半插入排序； ⑶冒泡排序； ⑷简单选择排序； ⑸快速排序； ⑹堆排序； ⑺归并排序。

#include<iostream.h>
#include<stdlib.h>
const int MaxSize=100;

template<class Type>class sortlist;               //排序表类声明

/******************************数据元素的类定义****************************/

template<class Type>                            //数据元素的类定义
class element
{
	friend class sortlist<Type>;                //排序表为友元类
	private:
		Type key;                              //关键字
	public:
		element()                       //构造函数
		{}
		element(Type &k)
		{
			key=k;
		}
		Type getKey()                   //取数据元素的关键字      
		{
			return key;
		}
		void setKey(const Type k)         //修改数据元素的关键字
		{
			key=k;
		}

};

/***********************排序表类定义******************************/

template<class Type>         //排序表类
class sortlist
{
	protected:
		element<Type> *Arr;       //排序表         
		int CurrentSize;             //数据表中数据元素的个数

	public:
		sortlist():CurrentSize(0)               //构造函数
		{
			Arr=new element<Type>[MaxSize];
		}
		         
		~sortlist()                             //析构函数
		{
			delete []Arr;
		}
		void Swap(element<Type> &x,element<Type> &y)                //交换元素的位置
		{
			element<Type> temp=x;
			x=y;
			y=temp;
		}

/********************************排序方法************************************/

		void InsertionSort(sortlist<Type> &table);    //直接插入排序
		void BinaryInsertSort(sortlist<Type> &table);    //折半插入排序
		void BubbleSort(sortlist<Type> &table);        //冒泡排序
		void SelectSort(sortlist<Type> &table);      //选择排序
		void QuickSort(sortlist<Type> &table);                    //快速排序
		void QuickSort(sortlist<Type> &table,int low,int high,int &count);    
		void HeapSort(sortlist<Type> &table);                 //堆排序
		void FilterDown(sortlist<Type> &table,const int start,const int end);
		void MergeSort(sortlist<Type> &table);                  //归并排序
		void merge(sortlist<Type> &sourceTable,sortlist<Type> &mergedTable,const int left,const int mid,const int right);
		void MergePass(sortlist<Type> &sourceTable,sortlist<Type> &mergedTable,const int len);

/******************************  输入 输出 插入  ****************************/ 

		void Input(sortlist<Type> &table);                //输入元素
		void Print(sortlist<Type> &table);                //输出元素
		void Insert(Type d);                    //插入元素  
		
};




 //直接插入排序
template<class Type>
void sortlist<Type>::InsertionSort(sortlist<Type> &table)
{
	cout<<"初始序列:"<<endl;
	Print(table);                                //输出初始序列
	element<Type> temp;
	int j;
	for(int i=1;i<table.CurrentSize;i++)         //从1开始每次插入1个元素
	{
		temp=table.Arr[i];
		j=i;
		while(j>0&&temp.getKey()<table.Arr[j-1].getKey())      
		{
			table.Arr[j]=table.Arr[j-1];
			j--;
		}
			table.Arr[j]=temp;
			cout<<"第"<<i<<"次排序结果："<<endl;       
			Print(table);                          //输出各次排序结果
	} 
}



//折半插入排序
template<class Type>
void sortlist<Type>::BinaryInsertSort(sortlist<Type> &table)
{
	cout<<"初始序列:"<<endl;
	Print(table);                              //输出初始序列
	element<Type> temp;
	int left,right;
	for(int i=1;i<table.CurrentSize;i++)    //从1开始每次插入1个元素       
	{
		left=0;
		right=i-1;
		temp=table.Arr[i];
		while(left<=right)                        // left<=right则循环     
		{
			int mid=(left+right)/2;
			if(temp.getKey()<table.Arr[mid].getKey())
				right=mid-1;
			else
				left=mid+1;
		}
		for(int k=i-1;k>=left;k--)              //移动元素   
			table.Arr[k+1]=table.Arr[k];
		table.Arr[left]=temp;                     //插入待插入元素
		cout<<"第"<<i<<"次排序结果："<<endl;
		Print(table);                         //输出各次排序结果
	}
}



//冒泡排序
template<class Type>
void sortlist<Type>::BubbleSort(sortlist<Type> &table)
{
	cout<<"初始序列:"<<endl;
	Print(table);                              //输出初始序列
	int i=1;
	int finish=0;
	while(i<table.CurrentSize&&!finish)
	{
		finish=1;                                 //交换标志置为1，假定未交换
		for(int j=0;j<table.CurrentSize-i;j++)
			if(table.Arr[j].getKey()>table.Arr[j+1].getKey())           
			{                                             //逆序
				Swap(table.Arr[j],table.Arr[j+1]);        //相邻元素交换位置
				finish=0;                             //交换标志置为0，表示有交换
			}
		cout<<"第"<<i<<"次排序结果："<<endl;
		Print(table);                         //输出各次排序结果
		i++;
	}
}


//选择排序
template<class Type>
void sortlist<Type>::SelectSort(sortlist<Type> &table)
{
	cout<<"初始序列:"<<endl;
	Print(table);                              //输出初始序列
	int k;
	int m=1;
	for(int i=0;i<table.CurrentSize-1;i++)
	{
		k=i;
		for(int j=i+1;j<table.CurrentSize;j++)
		{
			if(table.Arr[j].getKey()<table.Arr[k].getKey())
				k=j;                         //当前具有最小关键字的数据位置
		}
		if(k!=i)                             //最小关键字的数据元素位置不等于i
			Swap(table.Arr[i],table.Arr[k]);
		cout<<"第"<<m<<"次排序结果："<<endl;
		Print(table);                         //输出各次排序结果
		m++;
	}
}


//快速排序
template<class Type>
void sortlist<Type>::QuickSort(sortlist<Type> &table)
{
	cout<<"初始序列:"<<endl;
	Print(table);                              //输出初始序列
	int m=0;
	QuickSort(table,0,table.CurrentSize-1,m);
}


template<class Type>
void sortlist<Type>::QuickSort(sortlist<Type> &table,int low,int high,int &count)
{                                //在待排序区间[low,high]上，递归地进行快速排序
	int i=low,j=high;
	element<Type> temp=table.Arr[low];   //取区间第一个位置为基准位置
	if(i<j)
	{
		while(i<j)
		{
			while(i<j&&temp.getKey()<table.Arr[j].getKey())
				j--;
			if(i<j)
			{
				table.Arr[i]=table.Arr[j];
				i++;
			}
			while(i<j&&temp.getKey()>=table.Arr[j].getKey())
				i++;
			if(i<j)
			{
				table.Arr[j]=table.Arr[i];
				j--;
			}
		}
		table.Arr[i]=temp;                      //将基准元素就位
		count++;
		cout<<"第"<<count<<"次排序结果："<<endl;
		Print(table);                         //输出各次排序结果
		QuickSort(table,low,i-1,count);        //在左子区间递归进行快速排序
		QuickSort(table,i+1,high,count);        //在右子区间递归进行快速排序
	}
}




//堆排序
template<class Type>                        //调整堆
void sortlist<Type>::FilterDown(sortlist<Type> &table,const int start,const int end)
{                               //向下调整使从start到end为止的子表成为最大堆
	int i=start,j=2*i+1;           //j为i的左孩子
	element<Type> temp=table.Arr[i];
	while(j<=end)
	{
		if(j<end&&table.Arr[j].getKey()<table.Arr[j+1].getKey())
			j++;                             //在两个孩子中选关键字较大者
		if(temp.getKey()>=table.Arr[j].getKey())
			break;
		else
		{
			table.Arr[i]=table.Arr[j];
			i=j;
			j=2*j+1;
		}
	}
	table.Arr[i]=temp;
	
}

template<class Type>                          //堆排序
void sortlist<Type>::HeapSort(sortlist<Type> &table)
{                                //对排序表table进行排序，使得表中各个数据元素按其关键字非递减有序
	cout<<"初始序列:"<<endl;
	Print(table);                              //输出初始序列
	int tablesize=table.CurrentSize;
	for(int i=(table.CurrentSize-2)/2;i>=0;i--)
		FilterDown(table,i,table.CurrentSize-1);           //初始建堆
	for(i=tablesize-1;i>=1;i--)
	{
		Swap(table.Arr[0],table.Arr[i]);               //堆顶元素与最后一个元素交换台
		tablesize--;
		FilterDown(table,0,i-1);                         //重建最大堆
		cout<<"第"<<table.CurrentSize-i<<"次排序结果："<<endl;
	    Print(table);                         //输出各次排序结果
	}
}




//归并排序
template<class Type>
void sortlist<Type>::merge(sortlist<Type> &sourceTable,sortlist<Type> &mergedTable,const int left,const int mid,const int right)
{        
	int i=left,j=mid+1,k=left;                      //指针初始化
	while(i<=mid&&j<=right)
	{
		if(sourceTable.Arr[i].getKey()<=sourceTable.Arr[j].getKey())
		{
			mergedTable.Arr[k]=sourceTable.Arr[i];
			i++;
			k++;
		}
		else
		{
			mergedTable.Arr[k]=sourceTable.Arr[j];
			j++;
			k++;
		}
	}
	if(i<=mid)
	{
		for(int p=k,q=i;q<=mid;p++,q++)
			mergedTable.Arr[p]=sourceTable.Arr[q];
	}
	else
	{
		for(int p=k,q=j;q<=right;p++,q++)
			mergedTable.Arr[p]=sourceTable.Arr[q];
	}
	
}


template<class Type>
void sortlist<Type>::MergePass(sortlist<Type> &sourceTable,sortlist<Type> &mergedTable,const int len)
{
	int i=0;
	while(i+2*len<=CurrentSize-1)
	{
		merge(sourceTable,mergedTable,i,i+len-1,i+2*len-1);
		i+=2*len;
	}
	if(i+len<=CurrentSize-1)
		merge(sourceTable,mergedTable,i,i+len-1,CurrentSize-1);
	else
	{
		for(int j=i;j<=CurrentSize-1;j++)
			mergedTable.Arr[j]=sourceTable.Arr[j];
	}


}


template<class Type>
void sortlist<Type>::MergeSort(sortlist<Type> &table)
{                                            //按数据元素关键字非递减的顺序对排序表table进行归并排序
	cout<<"初始序列:"<<endl;
	Print(table);                              //输出初始序列
	sortlist<Type> tempTable;
	tempTable.CurrentSize=table.CurrentSize;
	int len=1;
	int m=0;
	while(len<table.CurrentSize)
	{
		MergePass(table,tempTable,len);
		m++;
		cout<<"第"<<m<<"次排序结果："<<endl;
	    Print(tempTable);                         //输出各次排序结果
		len*=2;
	    MergePass(tempTable,table,len);
		m++;
		cout<<"第"<<m<<"次排序结果："<<endl;
	    Print(table);                         //输出各次排序结果
		len*=2;
		
	}
}

//输入元素
template<class Type>                          
void sortlist<Type>::Input(sortlist<Type> &table)
{
	cout<<"请输入要排序的元素：(以-1结束)"<<endl;
	Type n;
	cin>>n;
	while(n!=-1)                //输入元素，(以-1结束)
	{
		table.Insert(n);
		cin>>n;
	}
}

//插入元素 
template<class Type>                           
void sortlist<Type>::Insert(Type d)
{
	if(CurrentSize==MaxSize)
		return;
	CurrentSize++;                      //插入元素 
	Arr[CurrentSize-1].setKey(d);	
}


//输出元素
template<class Type>
void sortlist<Type>::Print(sortlist<Type> &table)
{
	cout<<"             ";
	for(int i=0;i<table.CurrentSize;i++)
		cout<<table.Arr[i].getKey()<<'\t';
	cout<<endl;
}




//主函数

void main()                         
{
	while(1)
	{
		cout<<"*******************排序算法**********************"<<endl;
	    cout<<"1.>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>直接插入排序;"<<endl;
	    cout<<"2.>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>折半插入排序;"<<endl;
	    cout<<"3.>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>    冒泡排序;"<<endl;
	    cout<<"4.>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>简单选择排序;"<<endl;
	    cout<<"5.>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>    快速排序;"<<endl;
	    cout<<"6.>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>      堆排序;"<<endl;
	    cout<<"7.>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>    归并排序;"<<endl;
	    cout<<"0.>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>    退出程序;"<<endl;
	    cout<<"请选择要进行的排序方法："<<endl;
	    int n;
	    cin>>n;
	    sortlist<int> list;
	    switch(n)
		{
			case 1:
				{
			        list.Input(list);
			        list.InsertionSort(list);                     //直接插入排序
				};break;
		
	        case 2:
				{
			       list.Input(list);
	               list.BinaryInsertSort(list);                   //折半插入排序
				};break;
	        case 3:
				{
			       list.Input(list);
			       list.BubbleSort(list);                         //冒泡排序
				};break;
	        case 4:
				{
			       list.Input(list);
			       list.SelectSort(list);                         //简单选择排序
				};break;
	        case 5:
				{
			       list.Input(list);
			       list.QuickSort(list);                         //快速排序
				};break;
	        case 6:
				{
			       list.Input(list);
			       list.HeapSort(list);                         //堆排序
				};break;
	        case 7:
				{
			       list.Input(list);
			       list.MergeSort(list);                  //归并排序
				};break;
	        case 0:
		           exit(1);break;                    //退出程序
			default:break;
		}
	}
}