33.cpp

算法与数据结构里面关于数据的排序 内部排序法

#include<iostream.h>
#include<stdlib.h>
#include<iomanip.h>
#include<string.h>
int compCount;
int shiftCount;
void copy(int a[],int Array[],int n)
{
	for(int i=0;i<n;i++)
		a[i]=Array[i];
}
void output(int Array[],int n)
{

	for(int i=0;i<n;i++)
		cout<<setw(4)<<Array[i];
	cout<<endl;
	cout<<"关键字比较次数:"<<compCount<<endl;
	cout<<"关键字移动次数:"<<shiftCount<<endl;	
		cout<<endl;
}

void BeforeSort()
{
	compCount=0;
	shiftCount=0;
}
bool comp(int x,int y)
{
	compCount++;
	return x<y;//x<y时实现交换
}

void swap(int i,int j,int Array[])
{
	int temp;
	temp=Array[i];
	Array[i]=Array[j];
	Array[j]=temp;
	shiftCount=shiftCount+3;
}
void StraightInsertSorter(int Array[],int n)//直接插入排序
{
	BeforeSort();
	for(int i=1;i<n;i++)
	{
		//依次与前面的纪录进行比较 如果发现比它小的纪录，就交换
		for(int j=i;j>0;j--)
			if(comp(Array[j],Array[j-1]))
				swap(j,j-1,Array);
			else 
				break;
	}
	cout<<"调用了直接插入排序:\n";
	output(Array,n);
}
void BubbleSort(int Array[],int n)//起泡排序
{
	BeforeSort();
	for(int i=1;i<n;i++)
		for(int j=n-1;j>=i;j--)
			if(comp(Array[j],Array[j-1]))
				swap(j,j-1,Array);	
		cout<<"调用了起泡排序排序:\n";
output(Array,n);
}
void SelectSort(int Array[],int n)//简单选择排序
{
	for(int i=0;i<n-1;i++)
	{
		int smallest=i;
		for(int j=i+1;j<n;j++)
			if(comp(Array[j],Array[smallest]))
				smallest=j;
			swap(i,smallest,Array);
	}
		cout<<"调用了简单选择排序:\n";
	output(Array,n);
}

//快速排序
int Partition(int Array[],int left,int right)
{
	int temp;//存放临时变量
	int i=left;
	int j=right;
	temp=Array[j];
	while(i!=j)
	{
		while(comp(Array[i],temp)&&(j>i))
			i++;
		if(i<j)
		{
			Array[j]=Array[i];
			j--;
			shiftCount++;
		}
		while(comp(temp,Array[j])&&(j>i))
			j--;
		if(i<j)
		{
	    	Array[i]=Array[j];
			i++;
			shiftCount++;
		}
	}
	Array[i]=temp;

	return i;
}
void QuickSort(int Array[],int left,int right)
{
//	BeforeSort();
    if(right<=left)
		return;
	int pivot=(left+right)/2;//选择轴值
	swap(pivot,right,Array);
	pivot=Partition(Array,left,right);//对剩余纪录进行分割
	QuickSort(Array,left,pivot-1);
	QuickSort(Array,pivot+1,right);
		
}
void QSort(int Array[],int left,int right)
{
	QuickSort(Array,left,right);
	cout<<"调用了快速排序:\n";	
    output(Array,right+1);
}
//希尔排序
void ModifiedInsertSort(int Array[],int n,int delta)
{
	for(int i=delta;i<n;i+=delta)
		for(int j=i;j>=delta;j-=delta)
		{
			if(comp(Array[j],Array[j-delta]))
				swap(j,j-delta,Array);
			else 
				break;
		}
}
void ShellSort(int Array[],int n)
{
	BeforeSort();
	for(int delta=n/2;delta>0;delta/=2)
		for(int j=0;j<delta;j++)
			ModifiedInsertSort(& Array[j],n-j,delta);
		cout<<"调用了希尔排序:\n";	output(Array,n);
}	
//堆排序
void shift(int i,int j,int Array[])
{
	Array[j]=Array[i];
	shiftCount++;
}
void sift(int left,int right,int Array[],int n)
{
	int i=left;
	int j=2*i;
	shift(left,0,Array);
	bool finished=false;
	shift(left,n+1,Array);
	while(j<=right&&!finished)
	{
		if(j<right&&comp(Array[j+1],Array[j]))
			j=j+1;
		if(!comp(Array[j],Array[0]))
			finished=true;
	    else
		{
			shift(j,i,Array);
			i=j;
			j=2*i;
		}
	}
		shift(n+1,i,Array);
}
void HeapSort(int Array[],int n)
{
	BeforeSort();
	for(int left=n/2;left>=1;left--)
		sift(left,n,Array,n);
	for(int right=n;right>=2;right--)
	{
		swap(1,right,Array);
		sift(1,right-1,Array,n);
	}
	int temp;
	for(int i=0;i<n/2;i++)
	{
		temp=Array[i];
		Array[i]=Array[n-i-1];
		Array[n-i-1]=temp;
	}
	cout<<"调用了堆排序:\n";
	output(Array,n);
}
	


void main()
{
	int n;
	cout<<"请输入要排序序列的个数：";
	cin>>n;
	int *Array=new int [n];	int *a=new int [n];
	int i,j;
	for(i=0;i<n;i++)
		Array[i]=rand()%100+1;
	copy(a,Array,n);
	cout<<"排序之前：";
	for(i=0;i<n;i++)
		cout<<setw(4)<<Array[i];
	cout<<endl;
	StraightInsertSorter( Array, n);
	copy(Array,a,n);
	BubbleSort( Array, n);
	copy(Array,a,n);
	SelectSort( Array, n);
	copy(Array,a,n);
	ShellSort( Array, n);
	copy(Array,a,n);	QSort( Array, 0,n-1);	
	copy(Array,a,n);	HeapSort( Array, n);
}