4.cpp

（1）对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 （2）待排序表的表长不小于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同

#include<iostream>
using namespace std;
class elem
{ 
public: 
	int key;
	char other;   
};
//1、存储结构类定义与实现：
//自定义如下：
class seqlist
{
public:
	seqlist(int n1);
	void insertsort();//直接插入排序
	void bubblesort();
	void shellsort();
	int partition(int first, int end);
	void quicksort(int first, int end);
	void easysort();
	void print();
	int quicknum1;//计算快速排序移动数据次数
	int quicknum2;//计算快速排序比较数据次数
private:
	elem data[200];
	int n;
};
seqlist::seqlist(int n1)
{
	quicknum1=0;
	quicknum2=0;
	int temp;
	n=n1;
	int i=0;
	while(i<n1)
	{
		data[i+1].key=temp%123;
		temp=temp+temp*i;
		if(i%2==0)
			temp=temp+2000000;
		i++;
	}
}
void seqlist::print()
{
	for(int i=0;i<n;i++)
	{
		cout << data[i+1].key << " "  ;
	}
	cout << endl ;

} 
//2、起泡排序算法
void seqlist::bubblesort()
{
	int num1=0,num2=0;
	int i=n-1,j;
	for(;i>0;i--)
	{
		for(j=1;j<i+1;j++)
		{
			if(data[j].key<data[j+1].key && num2++)
			{
				int temp;
				temp=data[j].key;	num1++;
				data[j].key=data[j+1].key;	num1++;
				data[j+1].key=temp;	num1++;
			}
					
		}
			
	}
	cout << "移动次数为:" << num1 << endl ; 
	cout << "比较次数为:" << num2 << endl ; 
} 
//3、接直接插入排序算法
void seqlist::insertsort()
{
	int i,j;
	for(i=2;i<=n;i++)
	{
		data[0]=data[i];
		j=i-1;
		while(data[0].key<data[j].key) 
		{
			data[j+1]=data[j];
			j--;
		}
		data[j+1]=data[0];
	}
}
//4、简单选择排序算法
void seqlist::easysort()
{
	int num1=0,num2=0;
	cout << "easysort!!" << endl ;
	for(int i=1;i<n;i++)
	{
		int min=data[i].key;	num1++;
		for(int j=i;j<n+1;j++)
		{
			if(data[j].key>min && num2++)
			{
				min=data[j].key;	num1++;
				data[j].key=data[i].key;	num1++;
				data[i].key=min;	num1++;
			}
		}
	}
	cout << "移动次数为:" << num1 << endl ; 
	cout << "比较次数为:" << num1 << endl ; 
} 
//5、快速排序算法
int seqlist::partition(int first, int end)
{	
    int i(first),j(end);        
    while (i<j)	
    {
		while(i<j && data[i].key<data[j].key && quicknum2++)
			j--;
		if (i<j) 
		{ 
			elem temp;
			temp=data[i];	quicknum1++;
			data[i]=data[j];	quicknum1++;
			data[j]=temp;	quicknum1++;
		}
		while (i<j && data[i].key<= data[j].key && quicknum2++)
			i++;
		if (i<j)
		{
			elem temp;
			temp=data[i];	quicknum1++;
			data[i]=data[j];	quicknum1++;
			data[j]=temp;	quicknum1++;
			j--;
		}
    }
    return i;    
}
void seqlist::quicksort(int first,int end)
{
	
	int pivotpos;
	if (first < end)
	{					
          pivotpos = partition (first, end );    
          quicksort ( first, pivotpos-1);
          quicksort ( pivotpos+1, end );
	}
}
//6、希尔排序算法
void seqlist::shellsort()
{
	int num1=0,num2=0;
	int i,j;
	for(int d=n/2;d>=1;d=d/2)
	{
		for(i=d+1;i<=n;i++)
		{
			data[0]=data[i];	num1++;
			j=i-d;
			while(j>0 && data[0].key<data[j].key && num2++) 
			{
				data[j+d]=data[j];	num1++;
				j=j-d;
			}
			data[j+d]=data[0];	num1++;
		}
	}
	cout << "移动次数为:" << num1 << endl ; 
	cout << "比较次数为:" << num1 << endl ; 
}