数据结构实验报告六（排序实…

数据结构与算法课程实验报告

实验六：排序实践

姓名：

班级：               

学号： 

实验六 排序实践

一．实验内容：

      实现各排序算法，必须实现起泡排序、希尔排序和简单选择排序，其他排序算法选做，并分析各算法的性能。

二．实验目的：

     掌握各排序算法的实现方法，并分析各排序算法的时间和空间性能。

三：问题描述：

希尔排序：在每趟排序前，先设置一个增量，将整个待排记录序列逐段分割成若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

起泡排序：第一趟起泡排序是将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。以此类推，直到将第n-1个记录和第n个记录的关键字进行比较过为止。再进行第二趟起泡排序，直到在一趟排序过程中没有进行过交换记录的操作为止。

简单选择排序：通过n-i次关键字间的比较，从n-i+1个记录中选择出关键字最小的记录，并和第i（1<=i<=n）个记录交换。

四：问题实现：

1.定义了两个数据结构，记录类型和顺序表类型。

typedef struct

{

      int key;         //关键字项

}RedType;           //记录类型

typedef struct

{

RedType r[MAX+1];  //r[0]做监视哨或暂存空间，MAX 20 为顺序表的最大长度

int length;   //顺序表长度

}SqList;  //顺序表类型。

2.主要实现思路：将待排序的序列存放在顺序表里，再进行相应的排序，每个排序都有初始关键字、每趟排序结果、最终排序结果的显示。

希尔排序：要自定义排序的趟数和每趟排序的增量，增量存放在一个数组里。主要是通过比较关键字的大小，记录后移，找到插入位置，然后插入。

起泡排序：设置了一个标记 flag;用于标记排序是否结束，flag=1继续，flag=0结束。主要是通过两两比较，每次都选出一个无序区里最大的关键字，直到全部有序为止。

简单选择排序：定义了一个函数SelectMinKey(SqList &L,int i)返回key最小的记录的下标。主要是选择关键字最小的记录的操作。

五：主要源程序代码（包含程序备注）

1.顺序表的初始化

SqList InitSqList(SqList &L)

{

      int N;

      cout<<“请输入待排序数据的个数N=”<<endl;

      cin>>N;

      L.length=N+1;

      return L;

}

2.顺序表的创建

SqList CreateSqList(SqList &L)

{

      InitSqList(L);

    cout<<“请输入待排序的数据“<<endl;

      for(int i=1;i<L.length;i++)

      {

           cout<<“L.r[“<<i<<“].key=”;

           cin>>L.r[i].key;

      }

      return L;

}

3.定义SelectMinKey(SqList &L,int i)函数，返回key最小的记录的下标。

int SelectMinKey(SqList &L,int i)

{

      int j;//v记录关键字最小的记录的下标

      int v=i;

      for(j=i+1;j<L.length;j++)

      {

           if(L.r[j].key<L.r[v].key)v=j;

      }

      return v;

}

4. 简单选择排序的实现

void SelectSort(SqList &L)//对顺序表L作简单选择排序

{

      cout<<“初始关键字 ：“;

      for(int j1=1;j1<L.length;j1++)cout<<” “<<L.r[j1].key;

      int j;

      int count=0;//记录排序趟数

      for(int i=1;i<L.length;i++)   //选择第i小的记录，并交换到位

      {

       j=SelectMinKey(L,i);    //选择key最小的记录

         if(i!=j)                    //与第i个记录交换

         {

              L.r[0]=L.r[i];   

              L.r[i]=L.r[j];

              L.r[j]=L.r[0];

         }

         count++;   

           cout<<endl<<count<<“趟排序结果：“;

           for(int j2=1;j2<L.length;j2++)cout<<” “<<L.r[j2].key;

      }

}

5.起泡排序的实现

void BubbleSort(SqList &L)

{

      cout<<“初始关键字 ：“;

      for(int j1=1;j1<L.length;j1++)cout<<” “<<L.r[j1].key;

      int count=0;//记录排序趟数

      int flag=1;//用于标记排序是否结束，flag=1继续，flag=0结束

      int m=L.length-2;//m用于记录无序区的个数,初始为n-1,因为L.r[0]不放数据，所以L.length=n+1

      while((m>0)&&(flag==1))   //m=0说明数据已全部有序

      {

           flag=0;

           for(int i=1;i<=m;i++)

           {

                 if(L.r[i].key>L.r[i+1].key)

                 {

                flag=1;

                      L.r[0]=L.r[i];

                      L.r[i]=L.r[i+1];

                      L.r[i+1]=L.r[0];

                 }

           }

           m–;

           count++;   

           cout<<endl<<count<<“趟排序结果：“;

           for(int j2=1;j2<L.length;j2++)cout<<” “<<L.r[j2].key;

      }

}

6.一趟希尔排序的实现

void ShellInsert(SqList &L,int d) // L.r[0]是暂存单元，不是哨兵。j<=0时，插入位置已找到

{

      int j;

    for(int i=d+1;i<L.length;++i)

      {

           if(L.r[i].key<L.r[i-d].key)

           {

                 L.r[0]=L.r[i];//将L.r[i]插入有序增量子表，暂存在L.r[0]

                 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];      //插入位置已找到，插入

           }

      }

}

7. t趟希尔排序的实现

void ShellSort(SqList &L)

{

      int t;

      int dk[MAX];

      cout<<“请输入排序趟数“<<endl;

      cin>>t;

      cout<<“请输入增量序列，要求没有除1外的公因子“<<endl;

      for(int i=0;i<t;i++)

      {

           cin>>dk[i];

      }

      while(dk[t-1]!=1)

      {

           cout<<“最后一个增量值必须为1！“<<endl;

      }

      cout<<“初始关键字 ：“;

      for(int j1=1;j1<L.length;j1++)cout<<” “<<L.r[j1].key;

      for(int k=0;k<t;k++)

      {

           ShellInsert(L,dk[k]);

           cout<<endl<<k+1<<“趟排序结果：“;

           for(int j2=1;j2<L.length;j2++)cout<<” “<<L.r[j2].key;

      }

}

8.主程序

void main()

{
 

      int ch,n=1; 

      do

      {

           SqList L;

          CreateSqList(L);

           cout<<“1.简单选择排序；2.冒泡排序；3.希尔排序“<<endl;

          cin>>ch;

           switch(ch)

           {

           case 1:SelectSort(L);

                 break;

           case 2:BubbleSort(L);

                 break;

           case 3:ShellSort(L);

                 break;       

           }

           cout<<endl<<endl<<“排序后：“<<endl;

           for(int i=1;i<L.length;i++)

           {

                 cout<<” “<<L.r[i].key;

           }

           do

           {

           cout<<endl<<endl<<“1.继续；2.退出“<<endl;

           cin>>n;          

           }while(n!=1&&n!=2);

      }while(n==1);

}

六：总结

在设计希尔排序的增量时，存在一些问题。我设计的是让用户自己定义要排序的趟数，和每趟排序的增量，并且设置了最后一趟增量必须为1，但其他没有强制设置。