🎃个人专栏：
🐬 算法设计与分析：算法设计与分析_IT闫的博客-CSDN博客
🐳Java基础：Java基础_IT闫的博客-CSDN博客
🐋c语言：c语言_IT闫的博客-CSDN博客
🐟MySQL：数据结构_IT闫的博客-CSDN博客
🐠数据结构：数据结构_IT闫的博客-CSDN博客
💎C++：C++_IT闫的博客-CSDN博客
🥽C51单片机：C51单片机（STC89C516）_IT闫的博客-CSDN博客
💻基于HTML5的网页设计及应用：基于HTML5的网页设计及应用_IT闫的博客-CSDN博客
🥏python：python_IT闫的博客-CSDN博客
🐠离散数学：离散数学_IT闫的博客-CSDN博客
欢迎收看，希望对大家有用！
目录
🎯目的：
🎯内容：
🎯环境：
🎯步骤：
💻分部解析：
💎导入头文件和命名空间
💎定义类型
💎输出排序结果函数
💎直接插入排序算法
💎折半插入排序算法
💎冒泡排序算法
💎简单选择排序的算法
💎希尔排序算法
💎快速排序算法
💎主函数
💻总代码：
🎯目的：
1、掌握排序的有关概念和特点。
2、熟练掌握直接插入排序、折半插入排序、冒泡排序、简单选择排序等算法的基本思想。
3、熟练掌握希尔排序、快速排序、堆排序、归并排序、基数排序等算法的基本思想，能够使用程序实现希尔排序、快速排序。
4、关键字序列有序与无序，对于不同的排序方法有不同的影响，通过该实验进一步加深理解。
🎯内容：
设有学生信息表{姓名，成绩}：{{aaa，87}，{bbb，76}，{ccc，92}，{ddd，64}，{eee，55}，{fff，78}，{ggg，100}，{hhh，43}}，试用不同排序算法进行排序。
🎯环境：
TC或VC++。
🎯步骤：
1、使用顺序结构存储学生信息（注意下标从1开始），并输出值。
2.将学生信息按成绩进行排序，输出各种排序算法每一趟排序的结果，观察关键字次序的变化。
（1）直接插入排序算法；
（2）折半插入排序算法；
（3）冒泡排序算法；
（4）简单选择排序的算法。
（5）希尔排序算法；
（6）快速排序算法。
💻分部解析：
💎导入头文件和命名空间
#include <iostream>
#include "cstring"
using namespace std;
该语句块中，使用了两个头文件，一个是
iostream，用于输入输出操作；另一个是cstring，用于字符串操作。使用using namespace std命名空间，可以避免每次都写std::。
💎定义类型
#define MAXSIZE 20
typedef int KeyType;
typedef string InfoType;
typedef struct{KeyType key;//关键字项InfoType otherinfo;//其他数据项
}RedType;
typedef struct {RedType r[MAXSIZE+1];//r[0]闲置 int length;//顺序表长度
}SqList;
该语句块中，定义了
MAXSIZE宏定义常量，KeyType和InfoType类型分别表示关键字类型和其他数据类型，RedType结构体表示记录，包含关键字项和其他数据项，SqList结构体表示顺序表，包含记录数组和顺序表长度。
💎输出排序结果函数
//输出语句
void OutPutSort(SqList L)
{for(int i=1;i<=L.length;i++){cout << " {" << L.r[i].otherinfo << "," << L.r[i].key << "}";}cout<<endl;
}
该语句块中，定义了
OutPutSort函数，用于输出排序结果。
💎直接插入排序算法
//直接插入排序算法
void InsetSort(SqList L)
{//对顺序表L进行直接插入 for(int i=2;i<=L.length;i++)if(L.r[i].key<L.r[i-1].key)//"<",需要将r【i】插入到有序子表{ L.r[0]=L.r[i];//把待插入的暂存到监视哨 L.r[i]=L.r[i-1];//后移操作int j;for(j=i-2;L.r[0].key<L.r[j].key;j--)//往后寻找插入位置L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}cout<<"经过直接插入排序法排序后："<<endl;OutPutSort(L);
}
该语句块中，定义了
InsetSort函数，用于对顺序表进行直接插入排序。
💎折半插入排序算法
//折半插入排序
void BInsertSort (SqList L)
{//对顺序表进行折半插入排序 int low,high,mid;for(int i=2;i<=L.length;i++){L.r[0]=L.r[i];//将待插入的记录暂存到监视哨中low=1;high=i-1;//置查找区间的初值while(low<=high){mid=(low+high)/2;if(L.r[0].key<L.r[mid].key) high=mid-1;//插入到前一个子表else low=mid+1; } for(int j=i-1;j>=high+1;j--)L.r[j+1]=L.r[j];//记录后移L.r[high+1]=L.r[0];//将r[0]插入到正确位置 }cout<<"经过折半插入排序后："<<endl;OutPutSort(L);
}
该语句块中，定义了
BInsertSort函数，用于对顺序表进行折半插入排序。
💎冒泡排序算法
//冒泡排序算法
void BubbleSort(SqList L)
{RedType t;int m=L.length-1;int flag=1;//用flag值用来标记某一趟的排序是否交换 while((m>0)&&(flag==1)){flag=0;//将flag置为0，如果本趟排序没有交换，则不会执行下一趟for(int j=1;j<=m;j++){if(L.r[j].key>L.r[j+1].key){flag=1;t=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=t;}}m--;}cout<<"经过冒泡法排序后："<<endl;OutPutSort(L);
}
该语句块中，定义了
BubbleSort函数，用于对顺序表进行冒泡排序。
💎简单选择排序的算法
//简单选择排序
void SelectSort(SqList L){RedType t;for(int i=1;i<L.length;i++){//在L.r[i...L.length]中选择最小的记录 int 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){t=L.r[i];L.r[i]=L.r[k];L.r[k]=t; }}cout<<"经过简单选择排序后："<<endl;OutPutSort(L);
}
该语句块中，定义了
SelectSort函数，用于对顺序表进行简单选择排序。
💎希尔排序算法
//希尔排序
void ShellInsert(SqList &L,int d){for(int i=d+1;i<=L.length;i++)if(L.r[i].key<L.r[i-d].key){//需将L.r[i]插入有序增量子表中 L.r[0]=L.r[i];//暂存在r[0]中int j;for(j=i-d;j>0&&L.r[0].key<L.r[j].key;j-=d)L.r[j+d]=L.r[j];L.r[j+d]=L.r[0]; }
}
void ShellSort(SqList L,int d[],int t){//按增量排序列d[0 ..t-1]for(int k=0;k<t;k++){ShellInsert(L,d[k]);//每一趟增量为t的希尔排序 }cout<<"经过希尔排序后："<<endl;OutPutSort(L);
}
该语句块中，定义了
ShellInsert函数和ShellSort函数，用于对顺序表进行希尔排序。
💎快速排序算法
//快速排序int Partition(SqList &L,int low ,int high){L.r[0]=L.r[low];//用子表的第一个作为枢轴 int pivotkey=L.r[low].key;//将其关键字保存在pivotkey里while(low<high)//从表的两端交替向中间查找 {while(low<high&&L.r[high].key>=pivotkey)--high;L.r[low]=L.r[high];//将比枢轴记录小的记录移到低位while(low<high&&L.r[low].key<=pivotkey)++low;L.r[high]=L.r[low];// 将比枢轴记录大的记录移到高位}L.r[low]=L.r[0];// 枢轴记录到位return low;//返回枢纽位置 }void QSort(SqList &L,int low,int high){if(low<high){int pivotloc=Partition(L,low ,high);//将L.r一分为二，pivotloc是枢轴位置 QSort(L,low,pivotloc-1);//对左子表递归排序QSort(L,pivotloc+1,high);//对右子表递归排序 }}void QuickSort(SqList L)
{//对顺序表进行快速排序 QSort(L,1,L.length);cout<<"经过快速排序后："<<endl;OutPutSort(L);
}
该语句块中，定义了
Partition函数和QSort函数和QuickSort函数，用于对顺序表进行快速排序。
💎主函数
int main() {// 初始化学生信息表SqList L;L.r[1].key = 87; L.r[1].otherinfo = "aaa";L.r[2].key = 76; L.r[2].otherinfo = "bbb";L.r[3].key = 92; L.r[3].otherinfo = "ccc";L.r[4].key = 64; L.r[4].otherinfo = "ddd";L.r[5].key = 55; L.r[5].otherinfo = "eee";L.r[6].key = 78; L.r[6].otherinfo = "fff";L.r[7].key = 100; L.r[7].otherinfo = "ggg";L.r[8].key = 43; L.r[8].otherinfo = "hhh";L.length = 8;cout << "原始学生信息表：";OutPutSort(L);// 不同排序算法进行排序InsetSort(L);BInsertSort (L);BubbleSort(L);SelectSort(L);int d[] = {5, 3, 1}; // 增量数组dShellSort(L, d, 3);QuickSort(L);return 0;
}对定义函数进行调用。
💻总代码：
#include <iostream>
#include "cstring"
using namespace std;#define MAXSIZE 20
typedef int KeyType;
typedef string InfoType;
typedef struct{KeyType key;//关键字项InfoType otherinfo;//其他数据项
}RedType;
typedef struct {RedType r[MAXSIZE+1];//r[0]闲置 int length;//顺序表长度
}SqList;//输出语句
void OutPutSort(SqList L)
{for(int i=1;i<=L.length;i++){cout << " {" << L.r[i].otherinfo << "," << L.r[i].key << "}";}cout<<endl;
}//直接插入排序算法
void InsetSort(SqList L)
{//对顺序表L进行直接插入 for(int i=2;i<=L.length;i++)if(L.r[i].key<L.r[i-1].key)//"<",需要将r【i】插入到有序子表{ L.r[0]=L.r[i];//把待插入的暂存到监视哨 L.r[i]=L.r[i-1];//后移操作int j;for(j=i-2;L.r[0].key<L.r[j].key;j--)//往后寻找插入位置L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}cout<<"经过直接插入排序法排序后："<<endl;OutPutSort(L);
}//折半插入排序
void BInsertSort (SqList L)
{//对顺序表进行折半插入排序 int low,high,mid;for(int i=2;i<=L.length;i++){L.r[0]=L.r[i];//将待插入的记录暂存到监视哨中low=1;high=i-1;//置查找区间的初值while(low<=high){mid=(low+high)/2;if(L.r[0].key<L.r[mid].key) high=mid-1;//插入到前一个子表else low=mid+1; } for(int j=i-1;j>=high+1;j--)L.r[j+1]=L.r[j];//记录后移L.r[high+1]=L.r[0];//将r[0]插入到正确位置 }cout<<"经过折半插入排序后："<<endl;OutPutSort(L);
}//冒泡排序算法
void BubbleSort(SqList L)
{RedType t;int m=L.length-1;int flag=1;//用flag值用来标记某一趟的排序是否交换 while((m>0)&&(flag==1)){flag=0;//将flag置为0，如果本趟排序没有交换，则不会执行下一趟for(int j=1;j<=m;j++){if(L.r[j].key>L.r[j+1].key){flag=1;t=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=t;}}m--;}cout<<"经过冒泡法排序后："<<endl;OutPutSort(L);
}//简单选择排序
void SelectSort(SqList L){RedType t;for(int i=1;i<L.length;i++){//在L.r[i...L.length]中选择最小的记录 int 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){t=L.r[i];L.r[i]=L.r[k];L.r[k]=t; }}cout<<"经过简单选择排序后："<<endl;OutPutSort(L);
}//希尔排序
void ShellInsert(SqList &L,int d){for(int i=d+1;i<=L.length;i++)if(L.r[i].key<L.r[i-d].key){//需将L.r[i]插入有序增量子表中 L.r[0]=L.r[i];//暂存在r[0]中int j;for(j=i-d;j>0&&L.r[0].key<L.r[j].key;j-=d)L.r[j+d]=L.r[j];L.r[j+d]=L.r[0]; }
}
void ShellSort(SqList L,int d[],int t){//按增量排序列d[0 ..t-1]for(int k=0;k<t;k++){ShellInsert(L,d[k]);//每一趟增量为t的希尔排序 }cout<<"经过希尔排序后："<<endl;OutPutSort(L);
} //快速排序int Partition(SqList &L,int low ,int high){L.r[0]=L.r[low];//用子表的第一个作为枢轴 int pivotkey=L.r[low].key;//将其关键字保存在pivotkey里while(low<high)//从表的两端交替向中间查找 {while(low<high&&L.r[high].key>=pivotkey)--high;L.r[low]=L.r[high];//将比枢轴记录小的记录移到低位while(low<high&&L.r[low].key<=pivotkey)++low;L.r[high]=L.r[low];// 将比枢轴记录大的记录移到高位}L.r[low]=L.r[0];// 枢轴记录到位return low;//返回枢纽位置 }void QSort(SqList &L,int low,int high){if(low<high){int pivotloc=Partition(L,low ,high);//将L.r一分为二，pivotloc是枢纽位置 QSort(L,low,pivotloc-1);//对左子表递归排序QSort(L,pivotloc+1,high);//对右子表递归排序 }}void QuickSort(SqList L)
{//对顺序表进行快速排序 QSort(L,1,L.length);cout<<"经过快速排序后："<<endl;OutPutSort(L);
}int main() {// 初始化学生信息表SqList L;L.r[1].key = 87; L.r[1].otherinfo = "aaa";L.r[2].key = 76; L.r[2].otherinfo = "bbb";L.r[3].key = 92; L.r[3].otherinfo = "ccc";L.r[4].key = 64; L.r[4].otherinfo = "ddd";L.r[5].key = 55; L.r[5].otherinfo = "eee";L.r[6].key = 78; L.r[6].otherinfo = "fff";L.r[7].key = 100; L.r[7].otherinfo = "ggg";L.r[8].key = 43; L.r[8].otherinfo = "hhh";L.length = 8;cout << "原始学生信息表：";OutPutSort(L);// 不同排序算法进行排序InsetSort(L);BInsertSort (L);BubbleSort(L);SelectSort(L);int d[] = {5, 3, 1}; // 增量数组dShellSort(L, d, 3);QuickSort(L);return 0;
}
