【数据结构实验】上机实验11：几种典型排序算法的实现编程实现：分别利用直接插入/折半插入/希尔/冒泡/快速/简单选择排序算法_输入一组无序数据,分别使用直接插入排序、折半插入算法、冒泡排序、简单选择排序

一、实验要求

上机实验题11：几种典型排序算法的实现

编程实现：分别利用直接插入/折半插入/希尔/冒泡/快速/简单选择排序算法实现将待排序序列{3,6,2,10,1,20,88,8,5,7,4,9}由小到大排序，并输出结果。

二、实验源代码和运行结果

（一）源代码

#include<iostream>
using namespace std;
typedef int ElemType;
#define N 20
typedef struct
{
ElemType key;
}RecType;
RecType t;//用于交换的变量t定义成全局
//冒泡排序
void BubbleSort(RecType R[],int n)
{
	int i,j;
	for(i=0;i<n-1;i++)
       for(j=0;j<n-1;j++)
		   if(R[j].key>R[j+1].key)
			   {
				   t.key=R[j].key;
				   R[j].key=R[j+1].key;
				   R[j+1].key=t.key;
		       }
}
 
//选择排序
void SelectSort(RecType R[],int n)
{
	int i,j,k;
	for(i=0;i<n-1;i++)
	{   
		k=i;
		for(j=i+1;j<n;j++)
			if(R[k].key>R[j].key)
				k=j;
		if(k!=i)
		{
		 t.key=R[k].key;
	     R[k].key=R[i].key;
		 R[i].key=t.key;
		}
}
}
//直接插入排序
void InsertSort(RecType R[],int n)
{
int i,j;
for(i=0;i<n;i++)//4.写的for截止条件是i<n-1，导致少遍历了一个元素，输出结果最后那个元素仍是存在逆序，改为i<n就行了
{
	if(R[i].key<R[i-1].key)//如果遇到首个逆序，刚好从有序区进入无序区
	{//3.if下面的这对括号也没加，导致输出结果是一串零并且提示R[]未进行初始化而强制停止程序
		t=R[i];//先将无序区首个元素存起来，方便前面元素后移为它腾空，而又不被覆盖住
    j=i-1;//将这个元素下标赋给j，j能使有序区元素后移而又不改变当前插入的趟数i
	do{
		R[j+1]=R[j];//有序区元素后移
	    j--;
	}while(j>=0&&R[j].key>t.key);//停止条件有两个，要么有序区已经遍历移动完毕，要么有序区已经遍历到第一个小于待插入元素的数，就可以进行插入了（此时待插入元素要插在找到的元素下一个位置）
R[j+1]=t;//2.这句写在了下面那个花括号后面，导致调用display函数后的结果全是地址
}//1.忘记在for循环下加花括号了，导致if下面的语句成顺序执行了，只执行一遍	
}
}
//折半插入
void BinInsertSort(RecType R[],int n)
{
int i,j,low,high,mid;
for(i=1;i<n;i++)
{
	if(R[i].key<R[i-1].key)
	{
	t=R[i];
	low=0;
	high=i-1;
	while(low<=high)
	{
	mid=(low+high)/2;
	if(t.key<R[mid].key)
		high=mid-1;
	else
		low=mid+1;
	}
	for(j=i-1;j>=high+1;j--)
		R[j+1]=R[j];
	R[high+1]=t;
	}
}
}
//希尔排序
void ShellSort(RecType R[],int n)
{
int i,j,d;
d=n/2;
while(d>0)
{
for(i=d;i<n;i++)
{
t=R[i];
j=i-d;
while(j>=0&&t.key<R[j].key)
{
R[j+d]=R[j];
j=j-d;
}
R[j+d]=t;
}
d/=2;
}
}
//快速排序
int partition(RecType R[],int s,int t)
{
int i=s,j=t;
RecType tmp=R[i];
while(i<j)
{
	while(j>i&&R[j].key>=tmp.key)
		j--;
	R[i]=R[j];
	while(i<j&&R[i].key<=tmp.key)
		i++;
	R[j]=R[i];
}
R[i]=tmp;
return i;
}
void QuickSort(RecType R[],int s,int t)
{
int i;
if(s<t)
{
i=partition(R,s,t);
QuickSort(R,s,i-1);
QuickSort(R,i+1,t);
}
}
//输出
void Display(RecType R[],int n)
{
	for(int i=0;i<n;i++)
		cout<<R[i].key<<" ";
	cout<<endl;
}
//主面板（显式）
void Interface()
{
    cout<<"请输入想要使用的排序算法：（输入序号即可）"<<endl;
	cout<<"1.冒泡排序算法"<<endl;
    cout<<"2.选择排序算法"<<endl;
    cout<<"3.直接插入排序算法"<<endl;
    cout<<"4.折半插入排序算法"<<endl;
    cout<<"5.希尔排序算法"<<endl;
    cout<<"6.快速排序算法"<<endl;
}
//选择匹配面板（隐式）
void Select(RecType R[],int n,int x)
{
	switch(x)
	{
	case 1:BubbleSort(R,n);break;
	case 2:SelectSort(R,n);break;
	case 3:InsertSort(R,n);break;
    case 4:BinInsertSort(R,n);break;
	case 5:ShellSort(R,n);break;
	case 6:QuickSort(R,1,n-1);break;
	};//这里忘记加分号了，一直报错。（这个地方很容易忽略！）
	Display(R,n);
}
int main()
{
	system("color F0");
	int n=0,x;
	RecType R[N]={3,6,2,10,1,20,88,8,5,7,4,9};
	for(int i=0;i<N&&R[i].key!=0;i++)
		n++;
	cout<<"初始序列为："<<endl;
	Display(R,n);
	cout<<endl;
	Interface();
	cin>>x;
	while(!(x==1||x==2||x==3||x==4||x==5||x==6))//如果输入错误就重新输入
	{
	system("cls");//清屏，更简洁
	cout<<"输入错误请重新输入！"<<endl<<endl;
	Interface();
    cin>>x;
	}
	cout<<"排序后的序列为："<<endl;
	Select(R,n,x);
}

（二）运行结果

三、实验总结

 这个实验，关键不是代码，而是这几种排序算法的核心思想，虽然搞懂它真的很费时间，但是一旦你明白了，在脑子里有个大体框架，就不会拘泥于代码层面。

以上仅是个人见解，狗头保命

实验课终于结束了，我终于不用每个周四晚上狂写10页实验报告，写到手指抽搐。我们这个老师，真的很让我痛苦。数据结构理论课，会在学习通布置很多视频和练习题，一章大概七八小节，一节一套练习题，一套3大概0来个题，有选择有填空。大概是这个样子的

 我真的会谢好吗，太多了，每天我课余时间，不是在补数据结构实验，就是在刷数据结构视频和做题，真的很心累。我太想放假了呜呜呜