各种排序.cpp

对以下6种常用的内部比较排序算法进行比较

#include<iostream>
using namespace std;
#include <stdio.h>
template<class T>
bool compare(T a,T b)
{
	return (a<b);
}
template<class T>
void swap(T array[],int i,int j)
{
	T a=array[i];
	array[i]=array[j];
	array[j]=a;
}
template<class T>
void improvedinsertsorter(T array[],int n,int &c,int &k)//优化后的直接插入排序。
{
	T temprecord;
	for(int i=1;i<n;i++)
	{
		temprecord=array[i];
		k++;
		int j=i-1;
		while((j>=0)&&(compare(temprecord,array[j])))
		{
			c++;
			array[j+1]=array[j];
			k++;
			j--;
		}
		c++;
		array[j+1]=temprecord;
		k++;
	}
	
}
template<class T>
void improvedbubblesorter(T array[],int n)//优化后的冒泡排序。
{
	bool noswap;int c(0),k(0);
	for(int i=1;i<n;i++)
	{
		noswap=true;
		for(int j=n-1;j>=i;j--)
		{
			c++;
			if(compare(array[j],array[j-1]))
			{
				swap(array,j,j-1);
				k=k+3;
				noswap=false;
			}
		}
		if(noswap)
			break;
	}
	cout<<"利用冒泡排序后的数值顺序是：";
	for(int t=0;t<n;t++)
	{cout<<array[t]<<" ";}
	cout<<endl;
	cout<<"比较的次数为"<<c<<endl;
	cout<<"移动的次数为"<<k<<endl;
	cout<<endl;
}
template<class T>
void straightselectsorter(T array[],int n)//直接选择排序。
{
	int c(0),k(0);
	for(int i=0;i<n-1;i++)
	{
		int smallest=i;
		for(int j=i+1;j<n;j++)
		{
			c++;
			if(compare(array[j],array[smallest]))
				smallest=j;
		}
		swap(array,i,smallest);
		k+=3;
	}
	cout<<"利用直接选择排序后的数值顺序是：";
	for(int t=0;t<n;t++)
	{cout<<array[t]<<" ";}
	cout<<endl;
	cout<<"比较的次数为"<<c<<endl;
	cout<<"移动的次数为"<<k<<endl;
	cout<<endl;
}
template<class T>
void shellsorter(T array[],int n)//shell排序。
{
	int c(0),k(0);
	for(int delta=n/2;delta>0;delta/=2)
		for(int j=0;j<delta;j++)
			modifiedinsertsort(&array[j],n-j,delta,c,k);
	cout<<"利用shell排序后的数值顺序是：";
	for(int i=0;i<n;i++)
	{cout<<array[i]<<" ";}
	cout<<endl;
	cout<<"比较的次数为"<<c<<endl;
	cout<<"移动的次数为"<<k<<endl;
	cout<<endl;
}
template<class T>
void modifiedinsertsort(T array[],int n,int delta,int &c,int &k)
{
	for(int i=delta;i<n;i+=delta)
		for(int j=i;j>=delta;j-=delta)
		{
			c++;
			if(compare(array[j],array[j-delta]))
			{swap(array,j,j-delta);k+=3;}
			else
				break;
		}
}
template<class T>
void quicksorter(T array[],int left,int right)//快速排序，i、j分别为数组的两端。
{
	int c(0),k(0);
	dosort(array,left,right,c,k);
	improvedinsertsorter(array,right-left+1,c,k);//对整个队列直接排序。
	cout<<"利用快速排序后的数值顺序是：";
	for(int i=0;i<=right-left;i++)
	{cout<<array[i]<<" ";}
	cout<<endl;
	cout<<"比较的次数为"<<c<<endl;
	cout<<"移动的次数为"<<k<<endl;
	cout<<endl;
}
template<class T>
void dosort(T array[],int left,int right,int &c,int &k)
{
	if(right<=left)
		return ;
	if(right-left+1>16)
	{
		int pivot=selectpivot(left,right);//选择轴值。
		swap(array,pivot,right);k+=3;
		pivot=partition(array,left,right,c,k);//分割函数，分割后轴值已经到达正确位置。
		dosort(array,left,pivot-1,c,k);
		dosort(array,pivot+1,right,c,k);
	}
}
int selectpivot(int left,int right)
{
	return (left+right)/2;
}
template<class T>
int partition(T array[],int left,int right,int &c,int &k)
{
	T temprecord;
	int i=left;
	int j=right;
	temprecord=array[j];
	while(i!=j)
	{
		while(compare(array[i],temprecord)&&j>i)
		{c++;i++;}c++;
		if(i<j)
		{
			array[j]=array[i];k++;
			j--;
		}
		while(compare(array[j],temprecord)&&j>i)
		{c++;j--;} c++;
		if(i<j)
		{
			array[i]=array[j];k++;
			i++;
		}
	}
	array[i]=temprecord;k++;
	return i;
}
template<class T>
class maxheap//最大堆类定义。
{
private:
	T *heaparray;//存放数据的数组。
	int currentsize;//当前元素个数。
	int maxsize;
	void Swap(int  pos_x,int  pos_y)
	{
		int a=pos_x;
		pos_x=pos_y;
		pos_y=a;
		k+=3;
	}
	void buildheap()//建堆。
	{
		for(int i=currentsize/2-1;i>=0;i--)
			siftdown(i);
	}
public:int c;int k;
	maxheap(T array[],const int n)
	{
		if(n<=0)
			return;
		currentsize=n;
		maxsize=n;
		heaparray=new T[maxsize];
		for(int i=0;i<maxsize;i++)
		{heaparray[i]=array[i];}
		buildheap();c=k=0;
	}
	~maxheap()
	{delete[]heaparray;}
	bool isleaf(int pos)const
	{return (pos>=currentsize/2)&&(pos<currentsize);}
	int leftchild(int pos)const
	{return 2*pos+1;}
	int rightchild(int pos)const
	{return 2*pos+2;}
	int parent(int pos)const
	{return (pos-1)/2;}
	bool remove(int pos,T &node)//删除给定下标的元素。
	{
		if(pos<0||(pos>=currentsize))
			return false;
		T temp=heaparray[pos];k++;
		heaparray[pos]=heaparray[--currentsize];k++;
		siftup(pos);
		siftdown(pos);
		node=temp;
		return true;
	}
	bool insert(const T&newnode)//向堆中插入新元素newnode
	{
		if(currentsize==maxsize)
			return false;
		heaparray[currentsize]=newnode;
		siftup(currentsize);
		currentsize++;
	}
	T removemax()//从堆中删除最大值。
	{
		if(currentsize==0)
		{
			cout<<"Can't Delete"<<endl;
			return 0;
		}
		else
		{
			T temp=heaparray[0];					//取堆顶元素
			heaparray[0]=heaparray[currentsize-1];	//堆末元素上升至堆顶
			currentsize--;
			siftdown(0);							//从堆顶开始筛选
			return temp;
		}
	}
	void siftup(int position)//从position向上开始调整，使序列成为堆。
	{
		int temppos=position;
		T temp=heaparray[temppos];k++;
		while((temppos>0)&&(heaparray[parent(temppos)]<temp))
		{c++;
			heaparray[temppos]=heaparray[parent(temppos)];k++;
			temppos=parent(temppos);k++;
		}c++;
		heaparray[temppos]=temp;k++;
	}
	void siftdown(int left)//筛选法函数，left表示开始处理的数组下标。
	{
		int i=left;
		int j=leftchild(i);
		T temp=heaparray[i];k++;
		while(j<currentsize)
		{c++;
			if((j<currentsize-1)&&(heaparray[j]<heaparray[j+1]))
				j++;
			c++;
			if(temp<heaparray[j])
			{
				heaparray[i]=heaparray[j];k++;
				i=j;
				j=leftchild(j);
			}
			else
				break;
		}
		heaparray[i]=temp;k++;
	}
};
template<class T>
void heapsort(T array[],int n)
{
	maxheap<T> max_heap=maxheap<T>(array,n);	
	cout<<"利用堆排序后的数值顺序是：";
	T *b;b=new T[n];
	for(int j=n-1;j>=0;j--)
		b[j]=max_heap.removemax();
	for(int i=0;i<n;i++)
		cout<<b[i]<<" ";
	cout<<endl;
	cout<<"比较的次数为"<<max_heap.c<<endl;
	cout<<"移动的次数为"<<max_heap.k<<endl;
	cout<<endl;
}
void main()
{
	for(int t=0;t<6;t++)
	{	
		int m;cout<<"输入数组元素个数";
		cin>>m;
		int *a0,*a1,*a2,*a3,*a4,*a5;
		a0=new int[m];a1=new int[m];a2=new int[m];a3=new int[m];a4=new int[m];a5=new int[m];
		cout<<"原数组的数字是：";
		for(int i=0;i<m;i++)
		{
			a0[i]=a1[i]=a2[i]=a3[i]=a4[i]=a5[i]=rand()/10000;
			cout<<a0[i]<<" ";
		}cout<<endl;
		int c(0),k(0);
		improvedinsertsorter(a0,m, c,k);
		cout<<"利用直接插入排序后的数值顺序是：";
		for(int t=0;t<m;t++)
		{cout<<a0[t]<<" ";}
		cout<<endl;
		cout<<"比较的次数为"<<c<<endl;
		cout<<"移动的次数为"<<k<<endl;
		cout<<endl;
		improvedbubblesorter(a1,m);
		straightselectsorter(a2,m);
		shellsorter(a3,m);
		quicksorter(a4,0,m-1);
		heapsort(a5,m);
	}
}