《计算机算法设计与分析》实 验 报 告

 

第二篇：算法设计实验报告一_

算法设计实验报告

一、实验内容：

题目：1、 编程实现常见排序算法，如插入排序、归并排序、快速排序、随机化的快速排序等，并统计不同输入规模下（1组从小到大排序，1组从大到小排序，其余8组随机）的平均物理执行时间。

     

     2、编程实现循环赛日程表

设有n=2k个运动员要进行网球循环赛，先要设计一个满足一下要求的比赛日常表：

（1）每个选手必须与其他n-1个选手各赛一次

（2）每个选手一天只能赛一次

（3）循环赛一共进行n-1天

二、核心代码说明：

1、 sort.h

template<class type>

struct SqList{

   type * key;

   int length;

};

template<class type>

void CreateSqList(SqList<type> &sl)//type为int

{

   int n;

   cout<<"请输入顺序表的长度"<<endl;

   cin>>n;

   sl.length=n;

   sl.key=new int[sl.length+1];

   assert(sl.key);

   srand(time(0));

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

   {

      sl.key[i]=rand();

   }

}

template<class type>

void OutPut(SqList<type> &L)

{

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

      cout<<L.key[j]<<"\t";

   cout<<endl;

}

//折半插入排序

template<class type>

void BInsertSort(SqList<type> &L)

{

   int high,low,m;

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

   {

      L.key[0]=L.key[i];//将L.key[i]暂存到L.key[0]

      low=1;

      high=i-1;

      while(low<=high)//在key[low]到key[high]中折半查找有序插入的位置

      {

        m=(low+high)/2;//折半

        if(L.key[0]<=L.key[m])

           high=m-1;//插入低半区

        else

           low=m+1;//插入高半区

      }

      for(int j=i-1;j>=high+1;--j)

        L.key[j+1]=L.key[j];      //记录后移

        L.key[high+1]=L.key[0];   //插入

   }

}

//归并排序

template<class type>

void Merge(type *SR,type *TR,int i,int m,int n)

{//将有序的SR[i...m]和SR[m+1...n]归并为有序的TR[i...n]

   int j,k;

   for(j=m+1,k=i;i<=m&&j<=n;k++)//将SR中的记录由大到小并入TR

   {

      if(SR[i]<=SR[j])

        TR[k]=SR[i++];

      else

        TR[k]=SR[j++];

   }

   if(i<=m)//将剩余的SR[i...m]赋值到TR

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

        TR[k++]=SR[a];

   else if(j<=n)//将剩余的SR[j...n]复制到TR

      for(int b=j;b<=n;b++)

        TR[k++]=SR[b];

}

template<class type>

void MSort(type *SR,type *TR1,int s,int t)

{

   type TR2[100000];//数组大小可以根据实际情况重新定义

   int m;

   //将SR[s...t]归并排序为TR[s...t]

   if(s==t)

      TR1[s]=SR[s];

   else

   {

      m=(s+t)/2;//将SR[s...t]平分为SR[s...m]和SR[m+1...t]

      MSort(SR,TR2,s,m);//递归地将SR[s...m]归并为有序的TR2[s...m]

      MSort(SR,TR2,m+1,t);//递归地将SR[m+1...t]归并为TR2[m+1...t]

      Merge(TR2,TR1,s,m,t);//将TR2[s...m]和TR2[m+1...t]归并到TR1[s...t]

   }

}

template<class type>

void MergeSort(SqList<type> &L)

{//对顺序表L作归并排序

   MSort(L.key,L.key,1,L.length);

}

//快速排序

template<class type>

int Partition(SqList<type>& L,int low,int high)

{//交换顺序表L中子表key[low]--key[high]中的记录，枢轴记录到位，并返回其所在位置，

//此时在它之前（后）的记录均不大（小）于它

   type pivotkey;

   L.key[0]=L.key[low];//用子表的第一个记录作枢轴记录

   pivotkey=L.key[low];//关键字

   while(low<high)//从表的两端交替向中间扫描

   {

      while(low<high&&L.key[high]>=pivotkey) --high;

      L.key[low]=L.key[high];//将比枢轴小的记录移至低端

      while(low<high&&L.key[low]<=pivotkey) ++low;

      L.key[high]=L.key[low];//将比枢轴大的记录移至高端

   }

   L.key[low]=L.key[0];//枢轴记录到位

   return low;//返回枢轴位置

}

template<class type>

void QSort(SqList<type>& L,int low,int high)

{

   int mid;//接收枢轴位置

   if(low<high)

   {

      mid=Partition(L,low,high);

      QSort(L,low,mid-1);//对低子表进行排序

      QSort(L,mid+1,high);//对高子表进行排序

   }

}

template<class type>

void QuitSort(SqList<type>& L)//对顺序表进行快速排序

{

   QSort(L,1,L.length);

}

          Sort.cpp

void main()

{

   SqList<int> sl;

   LONGLONG start1,finish1,start2,finish2,start3,finish3;

   CreateSqList(sl);

   start1=GetTickCount();

   BInsertSort(sl);

   finish1=GetTickCount();

   delete sl.key;

   cout <<"插入排序平均物理执行时间为"<<finish1-start1<<"ms"<<endl;

   CreateSqList(sl);

   start3=GetTickCount();

   QuitSort(sl);

   finish3=GetTickCount();

   delete sl.key;

   cout <<"快速排序平均物理执行时间为"<<finish3-start3<<"ms"<<endl;

   CreateSqList(sl);

   start2=GetTickCount();

   MergeSort(sl);

   finish2=GetTickCount();

   delete sl.key;

   cout <<"归并排序平均物理执行时间为"<<finish2-start2<<"ms"<<endl;

}

2、 richengbiao.cpp

int main(void)

{

   int k;

   cout << "输入k值，且运动员数为2^k：" << endl;

   cin >> k;

   int n = 1;

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

      n *= 2;

   int players = n;

   int a[100][100];

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

   {

      a[1][i] = i;

   }

   int m = 1;

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

   {

      n /= 2;

      for (int t = 1; t <= n; t++)

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

           for (int j = m+1; j <= 2*m; j++)

           {

              a[i][j+(t-1)*m*2] = a[i-m][j+(t-1)*m*2-m];

              a[i][j+(t-1)*m*2-m] = a[i-m][j+(t-1)*m*2];

           }

           m *= 2;

   }

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

   {

      for (int j = 1; j <= players; j++)

        cout << a[i][j] << " ";

      cout << endl;

   }

   return 0;

}

三、测试结果：

1、 题目一先把每个算法的排序时间得到：

再做成表格：

2、 题目二

四、心得与体会：

第一次实验中学到了不同算法的执行时间上的差异，而且懂得了分治法的基本思想，相当于回顾了之前学习的一些数据结构的知识，并且为以后的算法学习做铺垫。在代码设计上也遇到了各种各样的问题，比如rand()函数只能生成零到三万多的随机数，在10万个随机数的排序中必然会产生很多重复数，这是否对算法产生影响；归并排序中，TR2数组大小的定义也是和所排序数的数量有关。所以，很明显的是，代码的优化程度对实验结果也有巨大的影响。