【数据结构】——排序-阿里云开发者社区

🎯目的：

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;
}

【数据结构】——排序

🎯目的：

🎯内容：

🎯环境：

🎯步骤：

💻分部解析：

💎导入头文件和命名空间

💎定义类型

💎输出排序结果函数

💎直接插入排序算法

💎折半插入排序算法

💎冒泡排序算法

💎简单选择排序的算法

💎希尔排序算法

💎快速排序算法

💎主函数

💻总代码：

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【数据结构】——排序

🎯目的：

🎯内容：

🎯环境：

🎯步骤：

💻分部解析：

💎导入头文件和命名空间

💎定义类型

💎输出排序结果函数

💎直接插入排序算法

💎折半插入排序算法

💎冒泡排序算法

💎简单选择排序的算法

💎希尔排序算法

💎快速排序算法

💎主函数

💻总代码：

热门文章

最新文章

相关课程

相关电子书