sort.cpp

希尔排序

#include<iostream.h>
#include<stdlib.h>
class datalist
{
private:
	int *datas;
	int length;
public:
	datalist(int size);
	int getlength();
	int *getdatas();
	void bubblesort(datalist da);
	void quicksort(int a[],int left,int right);
	void showlist(datalist da);
};
datalist::datalist(int size)
{
	datas=new int[size];
	for(int k=0;k<size;k++)
		datas[k]=rand();
	length=size;
}
int datalist::getlength()
{
	return length;
}
int *datalist::getdatas()
{
	return datas;
}
int move1=0;
int compare1=0;
void datalist::bubblesort(datalist da)
{
	for(int i=0;i<da.getlength()-1;i++)
	{
		for(int j=da.getlength()-1;j>i;j--)
		{
			move1++;
			if(da.datas[j]<da.datas[j-1])
			{
				int temp=da.datas[j];
				da.datas[j]=da.datas[j-1];
				da.datas[j-1]=temp;
				compare1+=3;
			}
		}
	}
	
}
int move2=0;
int compare2=0;
void datalist::quicksort(int a[],int left,int right)
{
	int pivot,l,r,temp;
	l=left;
	r=right;
	pivot=a[(left+right)/2];
	while(l<r)
	{
		
		while(a[l]<pivot)++l;
		while(a[r]>pivot)--r;
		if(l>=r)break;
		temp=a[l];
		a[l]=a[r];
		a[r]=temp;
		move2+=3;
		--r;
		++l;
	}
    compare2+=2;
	if(l==r)l++;
	if(left<r)quicksort(a,left,l-1);
	if(l<right)quicksort(a,r+1,right);
}
void datalist::showlist(datalist da)
{
	for(int m=0;m<da.getlength();m++)
		cout<<da.datas[m]<<" ";
    cout<<endl;
}
void main()
{
	datalist da1(8);
	cout<<"待排序序列为:";
	da1.showlist(da1);
	da1.bubblesort(da1);
	cout<<"冒泡排序后序列为:";
	da1.showlist(da1);
    cout<<"数据比较次数为:"<<compare1<<endl;
	cout<<"数据移动次数为:"<<move1<<endl;
	datalist da2(8);
    cout<<"待排序序列为:";
	da2.showlist(da2);
	da2.quicksort(da2.getdatas(),0,da2.getlength()-1);
	cout<<"快速排序后序列为:";
    da2.showlist(da2);
	cout<<"数据比较次数为:"<<compare2<<endl;
	cout<<"数据移动次数为:"<<move2<<endl;
}