paixu.cpp

数据结构里的经典算法的模拟

#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
int swap1=0,swap2=0,swap3=0,swap4=0,swap5=0,swap6=0;//交换的次数
int move1=0,move2=0,move3=0,move4=0,move5=0,move6=0;//记录移动的次数
template<class T>
void ImprovedInsertSorter(T *array,int len)  //优化的插入排序算法
{
	T temp;
	for(int i=1;i<len;i++)
	{
		temp=array[i];
		move1++;
		int j=i-1;
		while((j>=0)&&(temp<array[j]))
		{
			swap1++;
			array[j+1]=array[j];
			move1++;
			j=j-1;
		}
		array[j+1]=temp;
		move1++;
	}
	for(int k=0;k<len;k++)
		cout<<array[k]<<setw(3);
	cout<<endl;
	cout<<"交换次数为："<<swap1<<endl;
	cout<<"移动次数为："<<move1<<endl;
}

template<class T>
void ImprovedBubbleSorter(T *array,int len)  //优化的冒泡排序算法
{
	bool noswap;                             //发生交换的标志
	for(int m=1;m<len;m++)
	{
		noswap=true;		
		for(int n=len-1;n>=m;n--)
		{
			if(array[n-1]>array[n])
			{
				swap2++;
				T temp=array[n];
				array[n]=array[n-1];
				array[n-1]=temp;
				move2+=3;
				noswap=false;		
			}
		}
		if(noswap)
			return;
	}
	
}
template<class T>
void StraightSelectSorter(T *array,int len)   //直接选择排序
{
	for(int i=0;i<len-1;i++)
	{
		int smallest=i;
		for(int j=i+1;j<len;j++)
			if(array[j]<array[smallest])
			{
				smallest=j;
				swap3++;
			}
			T temp=array[i];
			array[i]=array[smallest];
			array[smallest]=temp;
			move3+=3;
	}
	for(int k=0;k<len;k++)
		cout<<array[k]<<setw(3);
	cout<<endl;
	cout<<"交换次数为："<<swap3<<endl;
	cout<<"移动次数为："<<move3<<endl;
}
template<class T>
int Partition(T *array,int left,int right)    //返回轴数值
{
	T temp;
	int i=left;
	int j=right;
	temp=array[j];
	move4++;
	while(i!=j)
	{
		while((array[i]<temp)&&(j>i))
		{
			i++;
			swap4++;
		}
		if(i<j)
		{
			array[j]=array[i];
			move4++;
			j--;
		}
		while((array[j]>temp)&&(j>i))
		{
			j--;
			swap4++;
		}
		if(i<j)
		{
			array[i]=array[j];
			move4++;
			i++;
		}
	}
	array[i]=temp;
	move4++;
	return i;
}
template<class T>
void DoSort(T *array,int left,int right)     //递归的对序列进行排序
{
	if(right<=left) return;
	if(right-left+1>16)
	{
		int pivot=(left+right)/2;
		T temp=array[pivot];
		array[pivot]=array[right];
		array[right]=array[pivot];   //放在末端
		move4+=3;
		pivot=Partition(array,left,right);  //对剩余的记录分割
		DoSort(array,left,pivot-1);
		DoSort(array,pivot+1,right);     //递归快速排序
	}
}
template<class T>
void ImprovedQuickSorter(T *array,int left,int right) //优化的快速排序
{
	DoSort(array,left,right);    
	ImprovedInsertSorter(array,right-left+1);
}

template<class T>
void ModefiedInsertSort(T *array,int n,int delta)
{
	T temp;
	for(int i=delta;i<n;i+=delta)
		for(int j=i;j>=delta;j-=delta)
		{
			if(array[j]<array[j-delta])
			{
				swap5++;
				temp=array[j];
				array[j]=array[j-delta];
				array[j-delta]=temp;
				move5++;
			}
			else break;
		}
}
template<class T>                              //希尔排序
void ShellSorter(T *array,int n)
{
	for(int delta=n/2;delta>0;delta/=2)
		for(int j=0;j<delta;j++)
			ModefiedInsertSort(&array[j],n-j,delta);
	
	for(int k=0;k<n;k++)
		cout<<array[k]<<setw(3);
	cout<<endl;
	cout<<"交换次数为："<<swap5<<endl;
	cout<<"移动次数为："<<move5<<endl;
}
template <class T>
class MaxHeap  
{
private:
	T* heapArray;							//存放堆数据的数组
	int CurrentSize;						//当前堆中元素数目
	int MaxSize;							//堆所能容纳的最大元素数目
public:
	MaxHeap(T* array,int num,int max);
	virtual ~MaxHeap(){};					//析构函数
	void BuildHeap();
	void SiftDown(int left);				//筛选法函数，参数left表示开始处理的数组下标
	bool Insert(const T& newNode);			//向堆中插入新元素newNode
	void MoveMax();							//从堆顶移动最大值到尾部
	int moveNum;
	int cmpNum;
};

template<class T>
MaxHeap<T>::MaxHeap(T* array,int num,int max)
{
	heapArray=array;
	CurrentSize=num;
	MaxSize=max;
	BuildHeap();
	moveNum=0;
	cmpNum=0;
}

template<class T>
void MaxHeap<T>::BuildHeap()
{
	for (int i=CurrentSize/2-1; i>=0; i--) 
		SiftDown(i); 
}
template<class T>
void MaxHeap<T>::SiftDown(int left)
{
	//准备
	int i=left;							//标识父结点
	int j=2*i+1;						//标识关键值较小的子结点		
	T	temp=heapArray[i];				//保存父结点
	//过筛
	while(j<CurrentSize)
	{
		if(j<CurrentSize)
		{
			if(heapArray[j]<heapArray[j+1])
				j++;						//j指向右子结点
			swap6++;
		}
		if(temp<heapArray[j])
		{
			heapArray[i]=heapArray[j];
			move6++;
			i=j;
			j=2*j+1;					//向下继续
			swap6++;
		}
		else
		{
			swap6++;
			break;
		}
	}
	heapArray[i]=temp;
}
template<class T>
void MaxHeap<T>::MoveMax()
{
	if(CurrentSize==0){return;}					//堆为空
	else
	{
		T temp=heapArray[0];					//取堆顶元素
		heapArray[0]=heapArray[CurrentSize-1];	//堆末元素上升至堆顶
			move6++;
		CurrentSize--;
		SiftDown(0);							//从堆顶开始筛选
		heapArray[CurrentSize]=temp;
	}
}
template<class T>
void HeapSorter(T *array,int n)
{
	MaxHeap<T> max_heap=MaxHeap<T>(array,n,n);
	for(int i=0;i<n;i++)
		max_heap.MoveMax();	
	for(int k=0;k<n;k++)
		cout<<array[k]<<setw(3);
	cout<<endl;	
	cout<<"交换次数为："<<swap6<<endl;
	cout<<"移动次数为："<<move6<<endl;	
	cout<<endl;
}

void main()
{
	int n;
	int *array1,*array2;
	cout<<"排序算法实现："<<endl;
	cout<<"    1.优化插入排序"<<endl;
	cout<<"    2.优化冒泡排序"<<endl;
	cout<<"    3.直接选择排序"<<endl;
	cout<<"    4.优化快速排序"<<endl;
	cout<<"    5.希尔排序"<<endl;
	cout<<"    6.堆排序"<<endl;

	cout<<"请输入数组元素个数：";
	cin>>n;
	array1=new int[n];
	array2=new int[n];
	for(int i=0;i<n;i++)
		array1[i]=rand()%100;
	for(i=0;i<n;i++)
		array2[i]=array1[i];
	cout<<"优化插入排序："<<endl;
	cout<<"原数组为："<<endl;
	for(int j=0;j<n;j++)
		cout<<array1[j]<<setw(3);
	cout<<endl;
	cout<<"排序后:"<<endl;
	ImprovedInsertSorter(array1,n);
	cout<<endl;
	delete array1;
	cout<<endl;
	cout<<endl;
	cout<<endl;

	array1=new int[n];
	for(i=0;i<n;i++)
		array1[i]=array2[i];
	cout<<"改进冒泡排序："<<endl;
	cout<<"原数组为："<<endl;
	for(j=0;j<n;j++)
		cout<<array1[j]<<setw(3);
	cout<<endl;
	cout<<"排序后:"<<endl;
	ImprovedBubbleSorter(array1,n);
	for(int k=0;k<n;k++)
		cout<<array1[k]<<setw(3);
	cout<<endl;	
	cout<<"交换次数为："<<swap2<<endl;
	cout<<"移动次数为："<<move2<<endl;	
	cout<<endl;
	delete array1;
	cout<<endl;
	cout<<endl;
	cout<<endl;

	array1=new int[n];
	for(i=0;i<n;i++)
		array1[i]=array2[i];
    cout<<"直接选择排序："<<endl;
	cout<<"原数组为："<<endl;
	for(j=0;j<n;j++)
		cout<<array1[j]<<setw(3);
	cout<<endl;
	cout<<"排序后"<<endl;
	StraightSelectSorter(array1,n);
	cout<<endl;
	delete array1;
	cout<<endl;
	cout<<endl;
	cout<<endl;

	array1=new int[n];
	for(i=0;i<n;i++)
		array1[i]=array2[i];
	cout<<"优化快速排序："<<endl;
	cout<<"原数组为："<<endl;
	for(j=0;j<n;j++)
		cout<<array1[j]<<setw(3);
	cout<<endl;
	cout<<"排序后"<<endl;
	ImprovedQuickSorter(array1,0,n-1);
	cout<<endl;
	delete array1;
	cout<<endl;
	cout<<endl;
	cout<<endl;

	array1=new int[n];
	for(i=0;i<n;i++)
		array1[i]=array2[i];
	cout<<"希尔排序："<<endl;
	cout<<"原数组为："<<endl;
	for(j=0;j<n;j++)
		cout<<array1[j]<<setw(3);
	cout<<endl;
	cout<<"排序后:"<<endl;
	ShellSorter(array1,n);
	cout<<endl;
	delete array1;
	cout<<endl;
	cout<<endl;
	cout<<endl;
	
	array1=new int[n];
	for(i=0;i<n;i++)
		array1[i]=array2[i];
	cout<<"堆排序："<<endl;
	cout<<"原数组为："<<endl;
	for(j=0;j<n;j++)
		cout<<array1[j]<<setw(3);
	cout<<endl;
	cout<<"排序后"<<endl;
	HeapSorter(array1,n);
	
}