深 圳 大 学 实 验 报 告

      课程名称：­     数据结构                                  

      实验项目名称：     内部排序                               

              

学院：                                    

        

      专业：                                     

        

      指导教师：                 

           

      报告人       学号：      班级：          

      

      实验时间： 20##-12-25                                        

      实验报告提交时间：   20##-12-25                  

教务部制

深圳大学学生实验报告用纸

注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。

    2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。

 

第二篇：内部排序比较 (实验报告+源程序)C++

实验报告3

实验名称：数据结构与软件设计实习

题    目：内部排序算法比较

专业：生物信息学  班级：01   姓名：学号：实验日期：2010.07.24

一、             实验目的：

比较冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序；

二、             实验要求：

待排序长度不小于100，数据可有随机函数产生，用五组不同输入数据做比较，比较的指标为关键字参加比较的次数和关键字移动的次数；

对结果做简单的分析，包括各组数据得出结果的解释；

设计程序用顺序存储。

三、             实验内容

对各种内部排序算法的时间复杂度有一个比较直观的感受，包括关键字比较次数和关键字移动次数。

将排序算法进行合编在一起，可考虑用顺序执行各种排序算法来执行，最后输出所有结果。

四、实验编程结果或过程：

1. 数据定义

typedef struct {

KeyType key;

}RedType;

typedef struct {

RedType r[MAXSIZE+1];

int length;

}SqList;

2. 函数如下，代码详见文件“排序比较.cpp”

int Create_Sq(SqList &L)

void Bubble_sort(SqList &L)//冒泡排序

void InsertSort(SqList &L)//插入排序

void SelectSort(SqList &L) //简单选择排序

int Partition(SqList &L,int low,int high)

void QSort(SqList &L,int low,int high)//递归形式的快速排序算法

void QuickSort(SqList &L)

void ShellInsert(SqList &L,int dk)//希尔排序

 

void ShellSort(SqList &L,int dlta[ ])

3. 运行测试结果，运行结果无误，如下图

语速个数为20

元素个数为100

错误调试无。

调试分析：

时间复杂度与空间复杂度：

理论分析可以得出各种排序算法的时间复杂度和空间复杂度，如下表所示（图6）：

影响排序的因素：

u  待排序的记录数目n 的大小。

u  记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小。

u  关键字的结构及其分布情况。

u  对排序稳定性的要求

从结果中还可看出：

对于一般的排序，比较次数多，而交换次数相对较少；而快速排序比较次数和交换次数都较少，两者相差不如前者大。其中冒泡排序比较和交换次数都很大。

 

五、实验总结：

（1）实验中的存在问题和提高

存在问题：程序有待增强。

提高：界面处理简洁。

（2）收获与体会

各种排序的算法

排序的算法的比较次数与移动次数的计算

随机数的生成

   

附录 源程序

#include <iostream.h>

#include <malloc.h>

#include <stdlib.h>

#include <time.h>

#define LS(a,b) ((a)<(b))

#define LL(a,b) ((a)>(b))

#define MAXSIZE 10000

typedef int KeyType;

typedef struct {

KeyType key;

}RedType;

typedef struct {

RedType r[MAXSIZE+1];

int length;

}SqList;

int compare=0;

int change=0;

int Create_Sq(SqList &L)

{

int k;

cout<<"20074795元素个数:";

cin>>k;

L.length=k;

srand(time(NULL));

       for (int x=1; x<=k; x++)

       {

              L.r[x].key= rand() % k;//随机域为0~k

       }

return 1;

}

 void Bubble_sort(SqList &L)//冒泡排序

 {

int i,j,l,k=L.length,m=0,n=0;

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

  for(j=1;j<=k-1;++j){

   ++m;

   if(LL(L.r[j].key,L.r[j+1].key)){

    l=L.r[j].key;

    L.r[j].key=L.r[j+1].key;

    L.r[j+1].key=l;

    ++n;

    }

  }

  --k;

}

cout<<endl<<"-----冒泡排序后的序列-----"<<endl;

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

  cout<<" "<<L.r[i].key;

cout<<endl;

cout<<"冒泡排序的比较次数:";

cout<<m<<endl;

cout<<"冒泡排序的交换次数:";

cout<<n<<endl;

}

 void InsertSort(SqList &L)//插入排序

 {

int i,j,m=0,n=0;

cout<<endl;

  for(i=2;i<=L.length;++i)

  if(LS(L.r[i].key,L.r[i-1].key))

  {

   ++m;

   ++n;

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

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

   for(j=i-2;LS(L.r[0].key,L.r[j].key);--j)

   {

    ++m;

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

   }

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

  }

cout<<"-----直接插入排序后的序列-----"<<endl;

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

  cout<<" "<<L.r[i].key;

cout<<endl;

cout<<"直接插入排序的比较次数:";

cout<<m<<endl;

cout<<"直接插入排序的交换次数:";

cout<<n<<endl;

}

 void SelectSort(SqList &L) //简单选择排序

 {

int l,i,j,m=0,n=0;

cout<<endl;

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

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

  j=i+1;

  l=i;

  for(j;j<=L.length;++j){

   ++m;

   if(LL(L.r[0].key,L.r[j].key)){

    l=j;

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

   }

  }

   if(l!=i){

    ++n;

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

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

  }

}

cout<<"-----简单选择排序后的序列-----"<<endl;

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

cout<<" "<<L.r[i].key;

cout<<endl;

cout<<"简单选择排序的比较次数:";

cout<<m<<endl;

cout<<"简单选择排序的交换次数:";

cout<<n<<endl;

}

int Partition(SqList &L,int low,int high){

int pivotkey;

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

pivotkey=L.r[low].key;

while(low<high){

  while(low<high&&L.r[high].key>=pivotkey){

   ++compare;

   --high;

  }

  ++change;

  L.r[low]=L.r[high];

  while(low<high&&L.r[low].key<=pivotkey){

   ++compare;

   ++low;

  }

  ++change;

  L.r[high]=L.r[low];

}

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

return low;

}

void QSort(SqList &L,int low,int high)//递归形式的快速排序算法

{

int pivotloc;

if(low<high){

  pivotloc=Partition(L,low,high);

  QSort(L,low,pivotloc-1);

  QSort(L,pivotloc+1,high);

}

}

void QuickSort(SqList &L){

int i;

QSort(L,1,L.length);

cout<<"-----快速排序后的序列为-----"<<endl;

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

cout<<" "<<L.r[i].key;

cout<<endl;

cout<<"快速排序的比较次数:";

cout<<compare<<endl;

cout<<"快速排序的交换次数:";

cout<<change<<endl;

compare=0;

change=0;

}

 void ShellInsert(SqList &L,int dk)//希尔排序

 {

int i;

int j;

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

  if(LS(L.r[i].key,L.r[i-dk].key)){

   ++compare;

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

  for(j=i-dk;j>0&&LS(L.r[0].key,L.r[j].key);j-=dk){

   ++compare;

   ++change;

   L.r[j+dk]=L.r[j];

  }

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

  }

}

 void ShellSort(SqList &L,int dlta[])//希尔排序

 {

int k,j=L.length/2,t=0;

while(j>=0){

  ++t;

  j-=2;

}

j=L.length/2;

for(k=0;k<t;++k)//计算每次的增量值

{

  if(j==0)

   j=1;//定义最后一趟排序的增量

  dlta[k]=j;

  j-=2;

}

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

  ShellInsert(L,dlta[k]);

cout<<"-----希尔排序后的序列为-----"<<endl;

for(k=1;k<=L.length;k++)

  cout<<" "<<L.r[k].key;

cout<<endl;

cout<<"希尔排序的比较次数:";

cout<<compare<<endl;

cout<<"希尔排序的交换次数:";

cout<<change<<endl;

compare=0;

change=0;

}

void main(){

int i;

int dlta[MAXSIZE];

SqList L,a,b,c,d;

Create_Sq(L);

a=b=c=d=L;

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

cout<<" "<<L.r[i].key; 

Bubble_sort(L);

InsertSort(a);

SelectSort(b);

QuickSort(c);

ShellSort(d,dlta);

}