数据结构内排序实验报告

一、    实验目的

1、了解内排序都是在内存中进行的。

2、为了提高数据的查找速度，需要对数据进行排序。

3、掌握内排序的方法。

二、    实验内容

1、设计一个程序exp10—1.cpp实现直接插入排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序过程。

（1）    源程序如下所示：

//文件名:exp10-1.cpp

#include <stdio.h>

#define MAXE 20                //线性表中最多元素个数

typedef int KeyType;

typedef char InfoType[10];

typedef struct          //记录类型

{   

     KeyType key;               //关键字项

     InfoType data;        //其他数据项,类型为InfoType

} RecType;

void InsertSort(RecType R[],int n) //对R[0..n-1]按递增有序进行直接插入排序

{

     int i,j,k;

     RecType temp;

     for (i=1;i<n;i++)

     {

            temp=R[i];

            j=i-1;               //从右向左在有序区R[0..i-1]中找R[i]的插入位置

            while (j>=0 && temp.key<R[j].key)

            {    

                   R[j+1]=R[j];       //将关键字大于R[i].key的记录后移

                   j--;

            }

        R[j+1]=temp;               //在j+1处插入R[i]

            printf("i=%d,",i);           //输出每一趟的排序结果

            printf("插入%d,结果为: ",temp);

            for (k=0;k<n;k++)

                   printf("%3d",R[k].key);

            printf("\n");

     }

}

void main()

{

     int i,k,n=10;

     KeyType a[]={9,8,7,6,5,4,3,2,1,0};

     RecType R[MAXE];

     for (i=0;i<n;i++)

            R[i].key=a[i];

     printf("初始关键字: ");        //输出初始关键字序列

     for (k=0;k<n;k++)

            printf("%3d",R[k].key);

     printf("\n");

     InsertSort(R,n);

     printf("最后结果: ");            //输出初始关键字序列

     for (k=0;k<n;k++)

            printf("%3d",R[k].key);

     printf("\n");

}

（2）    运行的结果如下图所示：

2、设计一个程序exp10—2.cpp实现希尔插入排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序过程。

（1）    源程序如下所示：

//文件名:exp10-2.cpp

#include <stdio.h>

#define MAXE 20                //线性表中最多元素个数

typedef int KeyType;

typedef char InfoType[10];

typedef struct          //记录类型

{

     KeyType key;           //关键字项

     InfoType data;          //其他数据项,类型为InfoType

} RecType;

void ShellSort(RecType R[],int n)     //希尔排序算法

{

     int i,j,d,k;

     RecType temp;

     d=n/2;                               //d取初值n/2

     while (d>0)

     {     

            for (i=d;i<n;i++) //将R[d..n-1]分别插入各组当前有序区中

            {     

                   j=i-d;

                   while (j>=0 && R[j].key>R[j+d].key)

                   {     

                          temp=R[j];      //R[j]与R[j+d]交换

                          R[j]=R[j+d];

                          R[j+d]=temp;

                          j=j-d;

                   }

            }

            printf("d=%d: ",d); //输出每一趟的排序结果

            for (k=0;k<n;k++)

                   printf("%3d",R[k].key);

            printf("\n");

        d=d/2;               //递减增量d

     }

}

void main()

{

     int i,k,n=10;

     KeyType a[]={9,8,7,6,5,4,3,2,1,0};

     RecType R[MAXE];

     for (i=0;i<n;i++)

            R[i].key=a[i];

     printf("初始关键字: ");               //输出初始关键字序列

     for (k=0;k<n;k++)

            printf("%3d",R[k].key);

     printf("\n");

     ShellSort(R,n);

     printf("最后结果: ");                   //输出初始关键字序列

     for (k=0;k<n;k++)

            printf("%3d",R[k].key);

     printf("\n\n");

}

（2）    结果如下图所示：

3、设计一个程序exp10—3.cpp实现冒泡排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序过程。

（1）    源程序如下所示：

//文件名:exp10-3.cpp

#include <stdio.h>

#define MAXE 20                //线性表中最多元素个数

typedef int KeyType;

typedef char InfoType[10];

typedef struct          //记录类型

{   

     KeyType key;               //关键字项

    InfoType data;             //其他数据项,类型为InfoType

} RecType;

void BubbleSort(RecType R[],int n) //冒泡排序算法

{

     int i,j,k;

     RecType temp;

     for (i=0;i<n-1;i++)

     {     

            for (j=n-1;j>i;j--)       //比较,找出本趟最小关键字的记录

                   if (R[j].key<R[j-1].key)  

                   {     

                          temp=R[j];  //R[j]与R[j-1]进行交换,将最小关键字记录前移

                          R[j]=R[j-1];

                          R[j-1]=temp;

                   }

            printf("i=%d,冒出的最小关键字:%d,结果为: ",i,R[i].key);  //输出每一趟的排序结果

            for (k=0;k<n;k++)

                   printf("%2d",R[k].key);

            printf("\n");

     }

}

void main()

{

     int i,k,n=10;

     KeyType a[]={9,8,7,6,5,4,3,2,1,0};

     RecType R[MAXE];

     for (i=0;i<n;i++)

            R[i].key=a[i];

     printf("初始关键字: "); //输出初始关键字序列

     for (k=0;k<n;k++)

            printf("%2d",R[k].key);

     printf("\n");

     BubbleSort(R,n);

     printf("最后结果:  ");  //输出初始关键字序列

     for (k=0;k<n;k++)

            printf("%2d",R[k].key);

     printf("\n");

}

（2）    结果如下图所示：

 

第二篇：数据结构与算法实验报告_内排序

数据结构与算法实验报告

   

实验名称：  二分插入排序及其性能 

姓    名：              

学    号：           

专    业：             

指导教师：                

日    期：   20##-5-22        


一、实验目的

了解二分插入排序与直接插入排序的关系；掌握二分插入排序算法的实现；掌握算法运行时间的测量。

二、实验内容

实现二分插入排序算法，并将它和直接插入排序算法进行性能比较，然后用理论分析支持你的结论。

三、实验环境

Window XP操作系统；

Microsoft VisualC++编程环境；

Pentium(R) Dual-Core cpu;

2.50GHz,2.00GB内存

四、实现

1.类间的关系

提示：总排序类、插入排序类、直接插入排序类、二分插入排序类间的关系

答：父类是：总排序类

子类是：插入排序类 和二分插入排序类

父类是：插入排序类

子类是：直接插入排序类

2.二分插入排序类排序函数sort的实现

3.性能测试程序的主要代码

五、实验数据及结论

1.实验数据及分析

实验过程的描述。

2.实验结论

答:1、当输入的数组较小时，两种排序算法用时相差不大。

2、但是，当输入的数组较大时，两种算法的区别就出来了，而二分插入排序时间相对于直接插入排序时间要小得多。说明对于比较大的数组用二分插入排序法比较适合。

3、当输入序列是正序时，直接插入排序算法与二分插入排序算法所用的时间相等。

4、当输入的排序为逆排序时，二分插入排序要优于直接插入排序。

5、二分插入排序法，处理逆序的时间比正序的时间要长。

六、理论分析

答：使用二分查找插入位置尽管总的移动元素次数不可能减少，但是往往可以减少平均搜索长度，可以减少总的平均比较次数。二分插入排序的平均时间复杂度为O(n2)，最坏情况下的时间复杂度为(n2)，当待排序序列已经有序时，排序时间复杂度为O(nlogn)。空间复杂度为O(1)。直接插入排序应用场合是短序列、基本有序的数据，而实验测试的记录很多，已经不是短序列，记录的比较和移动次数也很多，时间代价的分析复杂一些，空间复杂度也大，因此所用的时间比较长。

相关推荐

专栏推荐