1. AI技术聚合首页
  2. IT

【数据结构】——排序

社会演员多 • • IT • 阅读 44

🎃个人专栏：

🐬 算法设计与分析：算法设计与分析_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}; // 增量数组d
    ShellSort(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}; // 增量数组d
    ShellSort(L, d, 3);
    QuickSort(L);

    return 0;
}

文章出处登录后可见！

已经登录？立即刷新

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
社会演员多的头像社会演员多普通用户
0
上一篇 2023年12月19日
下一篇 2023年12月19日

相关推荐