（PS：直接拿的友友zy的）
一个不知名大学生，江湖人称菜狗
original author: jacky Li
Email : 3435673055@qq.com
Time of completion：2023.1.1
Last edited: 2023.1.1
目录
（PS：直接拿的友友的）
排序1
第1关：简单选择排序算法
任务描述
相关知识
编程要求
测试说明
参考代码
第2关：直接插入排序实现
任务描述
相关知识
编程要求
测试说明
参考代码
第3关：折半插入排序实现
任务描述
相关知识
编程要求
测试说明
参考代码
排序2
第1关：希尔排序实现
任务描述
编程要求
测试说明
参考代码
第2关：冒泡排序算法实现
任务描述
编程要求
测试说明
参考代码
排序3
第1关：快速排序算法实现
任务描述
编程要求
测试说明
参考代码
第2关：选择排序算法实现
任务描述
编程要求
测试说明
参考代码
排序4
第1关：堆排序算法实现
任务描述
编程要求
测试说明
参考代码
第2关：二路归并算法实现
任务描述
编程要求
测试说明
参考代码
作者有言
排序1
第1关：简单选择排序算法
任务描述
本关任务：试以单链表为存储结构，实现简单选择排序算法。
相关知识
为了完成本关任务，你需要掌握：链表的相关操作和掌握选择排序算法。
编程要求
根据提示，在右侧编辑器补充代码。
测试说明
平台会对你编写的代码进行测试：
参考代码
#include <iostream>
using namespace std;
#define OK 1;
typedef struct Node
{
int data;
struct Node *next;
}Node,*LinkedList;
int LinkCreate(LinkedList &head)
{
int i=0,n;
LinkedList p,rear;
head = new Node;
head->next = NULL;
rear=head;
cin>>n;
while(i<n)
{
i++;
p=new Node;
cin>>p->data;
p->next=NULL;
rear->next=p; //将新结点链入到尾部
rear=p; //新结点变成新的尾部
}
return OK;
}
void LinkedListSelectSort(LinkedList head)
//本算法一趟找出一个关键字最小的结点，其数据和当前结点进行交换;若要交换指针，则须记下
//当前结点和最小结点的前驱指针
{
//###### Begin ######
LinkedList p, q, min;
p = head;
while(p->next) {
q = p->next;
min = q;
while(q) {
if(q->data < min->data) {
min = q; //min指向数据元素最小的结点
}
q = q->next;
}
for(q = p; q->next != min; q = q->next); //q指针指向min指针的前一个
q->next = min->next;
min->next = p->next; //min指向的结点插入到p指针后面
p->next = min;
p = p->next; //p指针后移一位
}
// ###### End ######
}
void LinkOut(LinkedList head) //对链表的输出
{
LinkedList p;
p=head->next;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
int main()
{
LinkedList head;
if(LinkCreate(head))
cout<<"创建成功"<<endl;
LinkedListSelectSort(head);
LinkOut(head);
}
第2关：直接插入排序实现
任务描述
本关任务：编写函数实现直接插入排序算法
相关知识
为了完成本关任务，你需要掌握：直接插入排序的算法思想。
编程要求
根据提示，在右侧编辑器补充代码
测试说明
平台会对你编写的代码进行测试：
参考代码
#include <iostream>
using namespace std;
# define MAXSIZE 20 //设记录不超过20个
# define OK 1;
typedef struct { //定义顺序表的结构
int r[MAXSIZE+1]; //存储顺序表的向量 r[0]一般作哨兵或缓冲区
int length ; //顺序表的长度
}SqList;
int ListCreate(SqList &L)
{
int i=1,n;
cin>>n;
while(i<=n)
{
cin>>L.r[i];
i++;
}
L.length=n;
return OK;
}
void InsertSort(SqList &L)
{
//###### Begin ######
for(int i=1;i<=L.length;i++)
{
for(int j=i+1;j<=L.length;j++)
{
if(L.r[i]>=L.r[j])
{
swap(L.r[i],L.r[j] );
}
}
}
// ###### End ######
}
void ListOut(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
cout<<L.r[i]<<" ";
cout<<endl;
}
int main()
{
SqList L;
if(ListCreate(L))
cout<<"创建成功\n";
InsertSort(L);
ListOut(L);
}第3关：折半插入排序实现
任务描述
本关任务：编写函数实现折半插入排序算法。
相关知识
为了完成本关任务，你需要掌握：折半插入排序算法。
编程要求
根据提示，在右侧编辑器补充代码
测试说明
平台会对你编写的代码进行测试：
测试输入：
5 （数字个数）
3 9 5 8 7 （数字序列）
预期输出：
创建成功
3 5 7 8 9
参考代码
#include <iostream>
using namespace std;
# define MAXSIZE 20 //设记录不超过20个
# define OK 1;
typedef struct { //定义顺序表的结构
int r[MAXSIZE+1]; //存储顺序表的向量 r[0]一般作哨兵或缓冲区
int length ; //顺序表的长度
}SqList;
int ListCreate(SqList &L)
{
int i=1,n;
cin>>n;
while(i<=n)
{
cin>>L.r[i];
i++;
}
L.length=n;
return OK;
}
void BInsertSort( SqList &L )
{
//###### Begin ######
int i,j;
for(i = 2;i<=L.length;i++)
{//如果遍历到的确实比前半部分最后一个大，插到尾部即可
if(L.r[i]<L.r[i-1])
{
L.r[0] = L.r[i];//把r[0]作为哨兵，记录要执行此次插入的数据
L.r[i] = L.r[i-1];//把i位置的数据换成i-1的数据，即已经使得前部分的数量+1
//i-1位置的数据现在被记录到了第i个位置，本身存在无意义，可以理解为空出一个位置，看这个位置能不能插
for(j=i-2;L.r[0]<L.r[j];--j)
{ //这个循环是为了把要插入的空位置找到合适的地方
//j+1=i-1
L.r[j+1]=L.r[j];
}
//这个循环结束后肯定能找到合适的位置
L.r[j+1]=L.r[0];
}
}
// ###### End ######
} // BInsertSort
void ListOut(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
cout<<L.r[i]<<" ";
cout<<endl;
}
int main()
{
SqList L;
if(ListCreate(L))
cout<<"创建成功\n";
BInsertSort( L );
ListOut(L);
}排序2
第1关：希尔排序实现
任务描述
本关任务：编写一个能实现希尔排序算法的函数。
编程要求
根据提示，在右侧编辑器补充代码
测试说明
平台会对你编写的代码进行测试：
文章来源：https://www.toymoban.com/news/detail-481583.html
参考代码
#include <iostream>
using namespace std;
# define MAXSIZE 20 //设记录不超过20个
# define OK 1;
typedef struct { //定义顺序表的结构
int r[MAXSIZE+1]; //存储顺序表的向量 r[0]一般作哨兵或缓冲区
int length ; //顺序表的长度
}SqList;
int ListCreate(SqList &L)
{
int i=1,n;
cin>>n;
while(i<=n)
{
cin>>L.r[i];
i++;
}
L.length=n;
return OK;
}
void ShellInsert(SqList &L,int dk)
{
//###### Begin ######
int i,j;
//从dk+1开始
for(i=dk+1 ; i<=L.length;i++)
{
//从当前下标向前 与同一小组的数据进行比较，如果前面数据大，就把前面数据赋值给当前位置
if( L.r[i] <L.r[i-dk] )//同一组元素中前一个相比较
{
L.r[0]=L.r[i];//暂存哨兵
for(j=i-dk; j>0 &&(L.r[0]<L.r[j] ) ; j-=dk )
{
//后移
L.r[j+dk]=L.r[j];
}
//插入位置
L.r[j+dk]=L.r[0];
}
}
// ###### End ######
}
void ShellSort(SqList &L,int dlta[ ],int t) //按增量序列dlta[0…t-1]对顺序表L作Shell排序
{
for(int k=0;k<t;++k)
ShellInsert(L,dlta[k]);//增量为dlta[k]的一趟插入排序
} // ShellSort
void ListOut(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
cout<<L.r[i]<<" ";
cout<<endl;
}
int main()
{
SqList L;
int dlta[3]={5,3,1};
if(ListCreate(L))
cout<<"创建成功\n";
ShellSort( L,dlta,3 );
ListOut(L);
}
第2关：冒泡排序算法实现
任务描述
本关任务：编写一个能实现希尔排序算法的函数。
编程要求
根据提示，在右侧编辑器补充代码
测试说明
平台会对你编写的代码进行测试：
参考代码
#include <iostream>
using namespace std;
# define MAXSIZE 20 //设记录不超过20个
# define OK 1;
typedef struct { //定义顺序表的结构
int r[MAXSIZE+1]; //存储顺序表的向量 r[0]一般作哨兵或缓冲区
int length ; //顺序表的长度
}SqList;
int ListCreate(SqList &L)
{
int i=1,n;
cin>>n;
while(i<=n)
{
cin>>L.r[i];
i++;
}
L.length=n;
return OK;
}
void ShellInsert(SqList &L,int dk)
{
//###### Begin ######
int i,j;
//从dk+1开始
for(i=dk+1 ; i<=L.length;i++)
{
//从当前下标向前 与同一小组的数据进行比较，如果前面数据大，就把前面数据赋值给当前位置
if( L.r[i] <L.r[i-dk] )//同一组元素中前一个相比较
{
L.r[0]=L.r[i];//暂存哨兵
for(j=i-dk; j>0 &&(L.r[0]<L.r[j] ) ; j-=dk )
{
//后移
L.r[j+dk]=L.r[j];
}
//插入位置
L.r[j+dk]=L.r[0];
}
}
// ###### End ######
}
void ShellSort(SqList &L,int dlta[ ],int t) //按增量序列dlta[0…t-1]对顺序表L作Shell排序
{
for(int k=0;k<t;++k)
ShellInsert(L,dlta[k]);//增量为dlta[k]的一趟插入排序
} // ShellSort
void ListOut(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
cout<<L.r[i]<<" ";
cout<<endl;
}
int main()
{
SqList L;
int dlta[3]={5,3,1};
if(ListCreate(L))
cout<<"创建成功\n";
ShellSort( L,dlta,3 );
ListOut(L);
}
排序3
第1关：快速排序算法实现
任务描述
本关任务：编写一个能实现希尔排序算法的函数。
编程要求
根据提示，在右侧编辑器补充代码
测试说明
平台会对你编写的代码进行测试：
参考代码
#include <iostream>
using namespace std;
# define MAXSIZE 20 //设记录不超过20个
# define OK 1;
typedef struct { //定义顺序表的结构
int r[MAXSIZE+1]; //存储顺序表的向量 r[0]一般作哨兵或缓冲区
int length ; //顺序表的长度
}SqList;
int ListCreate(SqList &L)
{
int i=1,n;
cin>>n;
while(i<=n)
{
cin>>L.r[i];
i++;
}
L.length=n;
return OK;
}
void QSort(SqList &L,int low, int high)
{
//###### Begin ######
if(low>=high) return ;
int i=low-1 ,j =high+1 , mid = L.r[low + high >>1];
while(i<j)
{
do i++ ;while(L.r[i]<mid);
do j-- ; while(L.r[j]>mid);
if(i<j)
swap(L.r[i],L.r[j]);
}
QSort(L,low, j);
QSort(L,j+1,high);
// ###### End ######
}
void ListOut(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
cout<<L.r[i]<<" ";
cout<<endl;
}
int main()
{
SqList L;
if(ListCreate(L))
cout<<"创建成功\n";
QSort(L,1,L.length);
ListOut(L);
return 0;
}
第2关：选择排序算法实现
任务描述
本关任务：编写一个能实现希尔排序算法的函数。
编程要求
根据提示，在右侧编辑器补充代码
测试说明
平台会对你编写的代码进行测试：
参考代码
#include <iostream>
using namespace std;
# define MAXSIZE 20 //设记录不超过20个
# define OK 1;
typedef struct { //定义顺序表的结构
int r[MAXSIZE+1]; //存储顺序表的向量 r[0]一般作哨兵或缓冲区
int length ; //顺序表的长度
}SqList;
int ListCreate(SqList &L)
{
int i=1,n;
cin>>n;
while(i<=n)
{
cin>>L.r[i];
i++;
}
L.length=n;
return OK;
}
void SelectSort(SqList &L)
{
//###### Begin ######
int i,j,min;//min存储L.r[i...n]中最小值的下标
for(i=1;i<L.length;i++)
{
min=i;
for(j=i+1;j<=L.length;j++)
{
if(L.r[j]<L.r[min])
min=j;
}
if(min!=i)//如果min较比初值发生变化，则交换
{
L.r[0]=L.r[i];
L.r[i]=L.r[min];
L.r[min]=L.r[0];
}
}
// ###### End ######
}
void ListOut(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
cout<<L.r[i]<<" ";
cout<<endl;
}
int main()
{
SqList L;
if(ListCreate(L))
cout<<"创建成功\n";
SelectSort(L);
ListOut(L);
return 0;
}
排序4
第1关：堆排序算法实现
任务描述
本关任务：编写一个能实现希尔排序算法的函数。
编程要求
根据提示，在右侧编辑器补充代码
测试说明
平台会对你编写的代码进行测试：
参考代码
#include <iostream>
using namespace std;
# define MAXSIZE 20 //设记录不超过20个
# define OK 1;
typedef struct { //定义顺序表的结构
int r[MAXSIZE+1]; //存储顺序表的向量 r[0]一般作哨兵或缓冲区
int length ; //顺序表的长度
}SqList;
int ListCreate(SqList &L)
{
int i=1,n;
cin>>n;
while(i<=n)
{
cin>>L.r[i];
i++;
}
L.length=n;
return OK;
}
void HeapAdjust(SqList &H,int s,int m)
{//从H中调整下标s的位置 一共M个元素
int j;
int rc;
rc=H.r[s];//将要移动的元素 暂存
//暂存堆顶r[s]到rc
for(j=2*s ; j<=m; j*=2)//2*s是左孩子
{
//如果左孩子<右孩子
if(j<m && H.r[j]<H.r[j+1] )//横比，j初值指向左孩子
{
++j;//就指向右孩子
}//如果右孩子大于左孩子，j指向右孩子，j指示关键字较大位置
if(rc>=H.r[j])//如果基准值大于等于j的key
break;//纵比,如果…，定位成功
H.r[s]=H.r[j];//指向当前结点的左孩子
s=j;//
//否则,r[j]上移到s,s变为j, 然后j*=2,进入下一层
}
H.r[s]=rc;//插入
// 将调整前的堆顶记录rc到位置s中
}
void HeapSort(SqList &H)
{
int i;
int temp;
for(i=H.length/2 ;i>0;--i)//建堆
{
HeapAdjust(H,i,H.length);
}
for(i=H.length ;i>1;--i)
{
//交换r[1]和r[i]
temp=H.r[i];
H.r[i]=H.r[1];
H.r[1]=temp;
HeapAdjust(H,1,i-1); //调整，使得1~i-1符合堆的定义
}
}
void ListOut(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
cout<<L.r[i]<<" ";
cout<<endl;
}
int main()
{
SqList L;
if(ListCreate(L))
cout<<"创建成功\n";
HeapSort(L);
ListOut(L);
return 0;
}
第2关：二路归并算法实现
任务描述
本关任务：编写一个能实现希尔排序算法的函数。
编程要求
根据提示，在右侧编辑器补充代码
测试说明
平台会对你编写的代码进行测试：
参考代码
#include <iostream>
using namespace std;
# define MAXSIZE 20 //设记录不超过20个
# define OK 1;
typedef struct { //定义顺序表的结构
int r[MAXSIZE+1]; //存储顺序表的向量 r[0]一般作哨兵或缓冲区
int length ; //顺序表的长度
}SqList;
int ListCreate(SqList &L)
{
int i=1,n;
cin>>n;
while(i<=n)
{
cin>>L.r[i];
i++;
}
L.length=n;
return OK;
}
void RedCopy(int &r1,int r2)
{
//复制元素r2到r1
r1=r2;
}
void Merge(int R[],int T[],int low,int mid,int high)
{
//###### Begin ######
//将相邻有序序列R[low..mid]和R[mid+1..high]归并为T[low..high]
int i=low,j=mid+1,k=low; //ijk各遍历一序列
while(i<=mid&&j<=high)
{
//选择两子序列中当前小的填入T[k]
if(R[i]<=R[j])
RedCopy(T[k++],R[i++]);
else
RedCopy(T[k++],R[j++]);
}
while(i<=mid) //剩余段复制到T
RedCopy(T[k++],R[i++]);
while(j<=high)
RedCopy(T[k++],R[j++]);
for(i=low;i<=high;i++) //将合并完的T复制到R 以便下次归并时用
RedCopy(R[i],T[i]);
// ###### End ######
}
void MSort(int R[],int T[],int low,int high)
{
//###### Begin ######
/*归并排序
若序列为1直接填入T即可，否则，将元序列一分为二，左右两侧子
序列递归排序 最后调用归并函数进行归并 将R[low..high]归并排
序到T[low..high] 下标不变*/
int mid;
if(low==high)
RedCopy(T[low],R[low]);
else
{
mid=(low+high)/2;
MSort(R,T,low,mid); //递归排序到临时数组
MSort(R,T,mid+1,high);
Merge(R,T,low,mid,high); //归并到目标数组
}
// ###### End ######
}
void MergeSort(SqList &L)
{
//###### Begin ######
//归并排序 递归实现
int *T; //临时数组
if(!(T=(int *)malloc((L.length+1)*sizeof(int ))))
exit(0);
MSort(L.r,T,1,L.length);
free(T);
T=NULL;
// ###### End ######
}
void ListOut(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
cout<<L.r[i]<<" ";
cout<<endl;
}
int main()
{
SqList L;
if(ListCreate(L))
cout<<"创建成功\n";
MergeSort(L);
ListOut(L);
return 0;
}
作者有言
如果感觉博主讲的对您有用，请点个关注支持一下吧，将会对此类问题持续更新……文章来源地址https://www.toymoban.com/news/detail-481583.html
到了这里，关于头歌作业之排序1、2、3、4的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
