exam5.cpp

来自「C++语言程序设计题典」· C++ 代码 · 共 171 行

#include <iostream.h>  
#define Max 100
class Sample
{
	int A[Max];
	int n;
	friend class process;
public:
	Sample() { n=0; }
};
class process
{
    void qsort(Sample &s,int l,int h);  //私有成员，由quicksort()成员调用
public:
	void getdata(Sample &s);     //获取数据
	void insertsort(Sample &s);  //插入排序
    void shellsort(Sample &s);   //希尔排序
    void bubblesort(Sample &s);  //冒泡排序
    void quicksort(Sample &s);   //快速排序
    void selectsort(Sample &s);  //选择排序
	void disp(Sample &s);
};
void process::getdata(Sample &s)
{
	int i;
	cout << "元素个数:";
	cin >> s.n;
	for (i=0;i<s.n;i++)
	{
		cout << "输入第" << i+1 << "个数据:";
		cin >> s.A[i];
	}
}
void process::insertsort(Sample &s) //插入排序
{
	int i,j,temp;
	for(i=1;i<s.n;i++)
	{
		temp=s.A[i];
		j=i-1;
        while (temp<s.A[j])
		{
			s.A[j+1]=s.A[j];
			j--;
		}
		s.A[j+1]=temp;
	}
}
void process::shellsort(Sample &s) //希尔排序
{
	int i,j,gap,temp;
	gap=s.n/2;
    while (gap>0)
	{
		for(i=gap;i<s.n;i++)
		{
			j=i-gap;
			while (j>=gap)
				if (s.A[j]>s.A[j+gap])
				{
					temp=s.A[j];
					s.A[j]=s.A[j+gap];
					s.A[j+gap]=temp;
					j=j-gap;
				}
				else j=0;
		}
		gap=gap/2;
	}
}
void process::bubblesort(Sample &s)  //冒泡排序
{
	int i,j,temp;
	for(i=0;i<s.n;i++)
		for(j=s.n-1;j>=i+1;j--)
			if(s.A[j]<s.A[j-1])
			{
				temp=s.A[j];
				s.A[j]=s.A[j-1];
				s.A[j-1]=temp;
			}
}
void process::quicksort(Sample &s)  //快速排序
{
	qsort(s,0,s.n-1);
}
void process::qsort(Sample &s,int l,int h)
{
	int i=l,j=h,temp;
	if(l<h)
	{
        temp=s.A[l];
		do
		{
			while (j>i && s.A[j]>=temp)
			j--;
			if(i<j)
			{
				s.A[i]=s.A[j];
				i++;
			}
			while (i<j && s.A[i]<=temp)
				i++;
			if (i<j)
			{
				s.A[j]=s.A[i];
				j--;
			}
		} while(i<j);
		s.A[i]=temp;		
		qsort(s,l,j-1);
		qsort(s,j+1,h);
	}
}
void process::selectsort(Sample &s) //选择排序
{
	int i,j,k,temp;
	for (i=0;i<s.n;i++)
	{
		k=i;
		for (j=i+1;j<=s.n-1;j++)
			if (s.A[j]<s.A[k])
				k=j;
		temp=s.A[i];
		s.A[i]=s.A[k];
		s.A[k]=temp;
	}
}
void process::disp(Sample &s)
{
	for (int i=0;i<s.n;i++)
		cout << s.A[i] << " ";
	cout << endl;
}
void main()
{
	int sel;
	Sample s;
	process p;
	p.getdata(s);
	cout << "原来序列:";
	p.disp(s);
	cout << "0:插入排序 1:希尔排序 2:冒泡排序 3:快速排序 4:选择排序 其他退出" << endl;
	cout << "选择排序方法:";
	cin >> sel;
	switch (sel)
	{
	case 0:
		p.insertsort(s);
		cout << "插入排序结果:";
		break;
	case 1:
		p.shellsort(s);
		cout << "希尔排序结果:";
		break;
    case 2:
		p.bubblesort(s);
		cout << "冒泡排序结果:";
		break;
	case 3:
		p.quicksort(s);
		cout << "快速排序结果:";
		break;
	case 4:
		p.selectsort(s);
		cout << "选择排序结果:";
		break;
	}
	p.disp(s);
}