C++ 数据结构 使用直接插入排序法、冒泡排序法和简单选择排序法这三种方法对顺序表进行排序

文章目录

• • 实验内容
  • 代码内容
  • 运行结果
  • 总结

实验内容

1.设计一个程序，用于演示直接插入排序法、冒泡排序法或简单选择排序法，要求采用菜单的形式进行选择。
2.测试数据：265，301，751，129，937，863，742，694，76，438
3.测试：分别用上面的数据测试直接插入排序法、冒泡排序法和简单选择排序法，并把排序结果输出。

代码内容

#include
#define MAXSIZE 20	//顺序表的最大长度
typedef int KeyType;	//关键字类型为整形
using namespace std;
typedef struct RedType{
	KeyType key;	//关键字
}RedType;
typedef struct SqList{
	RedType r[MAXSIZE+1]; //r[0]可以闲置以备使用或者作为哨兵使用
	int length;	//顺序表长度
}SqList;//顺序表类型
//直接插入法排序
void InsertSort(SqList &L){
	int j;
	for(int i=2;i<=L.length;i++){
		if(L.r[i-1].key>L.r[i].key){
			L.r[0]=L.r[i];	//将待插入的记录暂存到监视哨中
			L.r[i]=L.r[i-1];	//r[i-1]后移，并把L.r[i-1]空出来
			for(j=i-2;L.r[j].key>L.r[0].key;j--)
				L.r[j+1]=L.r[j];	//逐个后移
			L.r[j+1]=L.r[0];	//将r[0]即r[i]插入到正确的位置r[j+1]
		}	
	}
}
//冒泡排序法
void BubbleSort(SqList &L){
	int flag=1;	//flag用来标记某一趟排序是否发生交换
	for(int i=1;i<L.length&&flag==1;i++){
		flag=0;	//置0，如果本次没有交换则下一次不会执行
		for(int j=1;j<=L.length-i;j++){
			if(L.r[j].key>L.r[j+1].key){
		 		L.r[0].key=L.r[j].key;
				L.r[j].key=L.r[j+1].key;
				L.r[j+1].key=L.r[0].key;	//交换前后两个记录的关键字
				flag=1;	//发生交换，flag置1，表示本次发生了交换
			}
		}
	}
}
//选择排序法
void SelectSort(SqList &L){
	int k;	//选择第几个排序
	for(int i=1;i<L.length;i++){
		k=i;	//第一个开始选择，进行排序
		for(int j=i+1;j<=L.length;j++)
			if(L.r[j].key<L.r[k].key)
				k=j;	//k指向此趟排序中关键字最小的记录
		if(k!=i){
			L.r[0]=L.r[k];
			L.r[k]=L.r[i];
			L.r[i]=L.r[0];	//交换指定记录和指向最小关键字的个记录
		}
	}
}
//输入测试数据函数
void InputFunction(SqList &L){
	L.length=0;
	cout<<"输入测试数据，退出请输入999"<<endl;
	for(int i=1;cin>>L.r[i].key&&L.r[i].key!=999;i++)
		L.length++;
}
//输出排序数据
void display(SqList L){
	cout<<"按从小到大排序后的数据为："<<endl;
	for(int i=1;i<=L.length;i++)
		cout<<L.r[i].key<<"  ";
}
int main(){
	SqList L;
	int n;
	cout<<"请输入对应的序号"<<endl;
	cout<<"1.直接插入法排序"<<endl;
	cout<<"2.冒泡排序法"<<endl;
	cout<<"3.选择排序法"<<endl;
	cout<<"4.退出该程序"<<endl;
	while(cin>>n){
		switch(n){
			case 1:
				InputFunction(L); //输入测试数据
				InsertSort(L);	//直接插入法排序
				display(L);	//输出排序数据
				break;
			case 2:
				InputFunction(L); //输入测试数据
				BubbleSort(L);	//冒泡排序法
				display(L);	//输出排序数据
				break;
			case 3:
				InputFunction(L); //输入测试数据
				SelectSort(L);	//选择排序法
				display(L);	//输出排序数据
				break;
			case 4:
				exit(0);
			default:
				exit(0);
		}
	}
	return 0;
}

运行结果

总结

这次试验主要考察我们对于直接插入排序法、冒泡排序法和简单选择排序法这三种简单排序法的理解
而排序法的好坏在于时间效率，空间效率和稳定性，这三种方法还是比较实用的且都可以用于链式存储结构