川大专升本计算机科学与技术数据结构课程设计9005范文

川大20秋学期《数据结构课程设计9005》课程设计（实践）作业
专升本计算机科学与技术数据结构课程设计9005
数据结构课程设计范文

数据结构实验报告


本文是范文，仅供参考写作，禁止抄袭本文内容上传提交，违者取消写作资格，成绩不合格！

实验名称：         排序算法比较                  




提交文档学生姓名：                          
提交文档学生学号：                          
同组 成 员 名 单：                           
指导 教 师 姓 名：                           








排序算法比较
一、实验目的和要求
1、 设计目的
1． 掌握各种排序的基本思想。
2． 掌握各种排序方法的算法实现。
3． 掌握各种排序方法的优劣分析及花费的时间的计算。
4． 掌握各种排序方法所适应的不同场合。
2、 设计内容和要求
利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间
二、 运行环境（软、硬件环境）
软件环境：Vc6.0编程软件
运行平台： Win32
硬    件： 普通个人pc机
三、 算法设计的思想
1、冒泡排序：bubbleSort()
基本思想: 设待排序的文件为r[1..n]
    第1趟(遍)：从r[1]开始,依次比较两个相邻记录的关键字
r[i].key和r[i+1].key,若r[i].key>r[i+1].key，则交换记录
r[i]和r[i+1]的位置；否则,不交换。
     (i=1,2,...n-1)
    第1趟之后,n个关键字中最大的记录移到了r[n]的位置上。
    第2趟：从r[1]开始,依次比较两个相邻记录的关键字
r[i].key和r[i+1].key,若r[i].key>r[i+1].key，则交换记录
r[i]和r[i+1]的位置；否则,不交换。
     (i=1,2,...n-2)
    第2趟之后,前n-1个关键字中最大的记录移到了r[n-1]的位
置上，作完n-1趟,或者不需再交换记录时为止。
2、选择排序：selSort()
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
    选择排序不像冒泡排序算法那样先并不急于调换位置，第一轮（k=1）先从array[k]开始逐个检查，看哪个数最小就记下该数所在的位置于minlIndex中，等一轮扫描完毕，如果找到比array[k-1]更小的元素，则把array[minlIndex]和a[k-1]对调，这时array[k]到最后一个元素中最小的元素就换到了array[k-1]的位置。 如此反复进行第二轮、第三轮…直到循环至最后一元素
3、直接插入排序 ：insSort()
在已经排好序的序列中查找待插入的元素的插入位置，并将待插入元素插入到有序列表中的过程。
    将数组分成两部分，初始化时，前部分数组为只有第一个元素，用来存储已排序元素，我们这里叫 arr1 ；后部分数组的元素为除第一个元素的所有元素，为待排序或待插入元素，我们这里叫 arr2 。
    排序时使用二层循环：第一层对 arr2 进行循环，每次取后部分数组（待排序数组）里的第一个元素（我们称为待排序元素或称待插入元素） e1 ，然后在第二层循环中对 arr1 （已排好序的数组）从第一个元素往后进行循环，查到第一个大于待插入元素（如果是升序排列）或第一个小于待插入元素（如果是降序排列） e2 ，然后对 arr1 从 e2 元素开始往后的所有元素向后移，最后把 e1 插入到原来 e2 所在的位置。这样反复地对 arr2 进行循环，直到 arr2 中所有的待插入的元素都插入到 arr1 中。
4、快序排序：QuickSort()
基本思想：首先在r[1..n]中，确定一个r[i]，经过比较和移动，将r[i]放到"中间"某个位置上，使得r[i]左边所有记录的关键字小于等于r[i].key，r[i]右边所有记录的关键字大于等于r[i].key。以r[i]为界,将文件划分为左、右两个子文件。用同样的方法分别对这两个子文件进行划分, 得到4个更小的子文件。继续进行下去,使得每个子文件只有一个记录为止,便得到原文件的有序文件。
例:给定文件(20,05,37,08,63,12,59,15,44,08)，选用第1个元素20进行划分。
5、归并排序：MegeSort()
    假定文件(r[1],r[2],...,r[n])中记录是随机排列的,进行2-路归并排序，首先把它划分为长度均为1的n个有序子文件，然后对它们逐步进行2－路归并排序。其步骤如下：
　　第1趟：从r[1..n]中的第1个和第2个有序子文件开始,调用算法merge,每次归并两个相邻子文件,归并结果放到y[1..n]中。在y中形成 n/2个长度为2的有序子文件。若n为奇数,则y中最后一个子文件的长度为1。
    第2趟：把y[1..n]看作输入文件,将 n/2个有序子文件两两归并,归并结果回送到r[1..n]中,在r中形成n/2 /2个长度为4的有序子文件。若y中有奇数个子文件，则r中最后一个子文件的长度为2。共计经过log2n趟归并,最后得到n个记录的有序文件。
6、堆排序：HeapSort()
堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
1、N（N>1）个节点的的完全二叉树从层次从左自右编号，最后一个分枝节点（非叶子节点）的编号为 N/2 取整。2、且对于编号 i（1<=i<=N）有：父节点为 i/2 向下取整；若2i>N，则节点i没有左孩子，否则其左孩子为2i；若2i+1>N，则没有右孩子，否则其右孩子为2i+1。3、这里使用完全二叉树只是为了好描述算法，它只是一种逻辑结构，真真在实现时我们还是使用数组来存储这棵二叉树的，因为完全二叉树完全可以使用数组来存储。堆排序其实最主要的两个过程：第一步，创建初始堆；第二步，交换根节点与最后一个非叶子节从最后一个非叶子节点为开始向前循环每个会支节点，比较每个分支节点与他左右子节点，如果其中某个子节点比父节点大，则与父节点交换，交换后原父节点可能还小于原子节点的子节点，所以还需对原父节点进行调整，使用原父节点继续下沉，直到没有子节点或比左右子节点都大为止，调用过程可通过递归完成。当某个非叶子节点调整完毕后，再处理下一个非叶子节点，直到根节点也调整完成，这里初始堆就创建好了，这里我们创建的是大顶堆，即大的元素向树的根浮，这样排序最后得到的结果为升序，因为最大的将树中的最后一个元素与堆顶元素进行交换，并从树中去掉最后叶子节点。交换后再按创建初始堆的算法调整根节点，如此下去直到树中只有一个节点为止。
四、 算法的流程图


















五、 算法设计分析
1、冒泡排序：bubbleSort()
冒泡排序算法分析：
(1)最好情况, 待排序的文件已是有序文件:
      只需要进行1趟排序,
      共计比较关键字的次数为n－1
      不交换记录。      
(2)最坏情况, 要经过n-1趟排序，
     所需总的比较关键字的次数为
        (n-1)+(n-2)+...+1＝n(n-1)/2                                       
     交换记录的次数最多为
        (n-1)+(n-2)+...+1＝n(n-1)/2
     移动记录次数最多为
         3n(n-1)/2 。         
(3)只需要少量中间变量作为辅助空间。
     算法是稳定的。
2、选择排序：selSort()
选择排序算法分析：
(1)比较次数，在任何情况下,均为
(2)交换记录的次数
   在最好情况下,原n个记录递增有序：不移动记录。
   在最坏情况下共交换记录n-1对,移动记录数3(n-1)次。故,时间复杂度为O(n2)。
(3)只需少量中间变量作为辅助空间。
(4)算法是不稳定的。
3、直接插入排序 ：insSort()
直接插入排序算法分析：
故,时间复杂度为O(n2)。
(4) 只需少量中间变量作为辅助空间。
(5) 算法是稳定的。
4、快序排序：QuickSort(d)
快速排序算法分析：
(1)就平均速度而言，
   快速排序是已知内部排序方法中最好的一种排序方法,
       其时间复杂度为O(nlog(n))。
(2)在最坏情况下，
   快速排序所需的比较次数和冒泡排序的比较次数相同,
       其时间复杂度为O(n2)。
(3)快速排序需要一个栈作辅助空间，用来实现递归处理左、右子文件。
   在最坏情况下,递归深度为n，所需栈的空间大小为O(n)。
(4)快速排序是不稳定的。
5、归并排序：MegerSort()
归并排序算法分析：
(1)对n个记录的文件进行归并排序,共需log2n趟,
(2)每趟所需比较关键字的次数不超过n, 共比较O(nlog2n) 次。
(3)每趟移动n个记录, 共移动记录O(nlog2n)个
(4)归并排序需要一个大小为n的辅助空间        y[1..n]。
(5)归并排序是稳定的。
6、堆排序：HeapSort()
堆排序算法分析：
(1)堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成， 它们均是通过调用Heapify实现的。
(2)堆排序的最坏时间复杂度为  O(nlgn)。
(3)堆排序的平均性能较接近于最坏性能。
　  由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
(4)堆排序是就地排序，辅助空间为 O(1)。
(5)它是不稳定的排序方法
六、 源代码
#include<iostream.h>
#include<time.h>
#include<math.h>
#include<iomanip.h>
#include <stdlib.h>
//外部变量定义
int count1=0,bj1=0,yd1=0;
int count2=0,bj2=0,yd2=0;
int count3=0,bj3=0,yd3=0;
int count4=0,bj4=0,yd4=0;
int count5=0,bj5=0,yd5=0;
int count6=0,bj6=0,yd6=0;
clock_t start1,finish1;
clock_t start2,finish2;
clock_t start3,finish3;
clock_t start4,finish4;
clock_t start5,finish5;
clock_t start6,finish6;
int b[6]={finish1-start1,finish2-start2,finish3-start3,finish4-start4,finish5-start5,finish6-start6};

template<class T>
class an
{
public:
void selectsort(T A[],int n);//简单选择排序
void insertsort(T A[],int n);//直接插入排序
void shellsort(T A[],int n); //希尔排序
void bubblesort(T A[],int n);//冒泡排序
void quicksort(T A[],int n);//快速排序
void mergesort(T A[],int n);//两路合并排序
private:
void merge(T A[],int i1,int j1,int i2,int j2);
void qsort(T A[],int left,int right);
};


template<class T>
void an<T>::selectsort(T A[],int n)   //简单选择排序
{
int small;
start3=clock();
for(int i=0;i<n-1;i++)      
{  
small=i;
for(int j=i+1;j<n;j++)
{
  if(A[j]<A[small])
  {
  small=j;
  bj3++;
  }
swap(A[i],A[small]);
count3++;
    yd3+=3;
}   
}
cout<<"简单选择排序后的数组是："<<endl;
for(i=0;i<n;i++)
cout<<A[i]<<" ";
cout<<endl;
finish3=clock();
}


template<class T>             //直接插入排序
void an<T>::insertsort(T A[],int n)
{
start1=clock();
  for(int i=1;i<n;i++)
  {
  int j=i;
  T temp=A[i];
  while(j>0 && temp<A[j-1])
  {
  bj1++;
  A[j]=A[j-1];
  j--;
yd1++;
  }
  A[j]=temp;
  }
cout<<"直接插入排序后的数组是："<<endl;
for(i=0;i<n;i++)
cout<<A[i]<<" ";
cout<<endl;
finish1=clock();  
}


template<class T>       //希尔排序
void an<T>::shellsort(T A[],int n)
{
start2=clock();
int j,tmp,jmp;
jmp=n/2;
while(jmp!=0)
{
for(int i=jmp;i<n;i++)
{
tmp=A[i];
j=i-jmp;
while(tmp<A[j]&&j>=0)
{
bj2++;
A[j+jmp]=A[j];   
yd2++;
j=j-tmp;
}
bj2++;
A[jmp+j]=tmp;
yd2++;
}
jmp=jmp/2;
}
cout<<"希尔排序后的数组是："<<endl;
for(int i=0;i<n;i++)
cout<<A[i]<<" ";
cout<<endl;
finish2=clock();
}


template<class T>     //冒泡排序
void an<T>::bubblesort(T A[],int n)
{
start4=clock();
int i=n-1,j,last;
while(i>0)
{
last=0;
for(j=0;j<i;j++,i--)
{
if(A[j+1]<A[j])
{
bj4++;
swap(A[j],A[j+1]);
count4++;
yd4+=3;
last=j;
}
bj4++;
}
i=last;
}
cout<<"冒泡排序后的数组是："<<endl;
for(i=0;i<n;i++)
cout<<A[i]<<" ";
cout<<endl;
finish4=clock();
}


template<class T>   //快速排序
void an<T>::quicksort(T A[],int n)
{
start5=clock();
qsort(A,0,n-1);
cout<<"快速排序后的数组是："<<endl;
for(int i=0;i<n;i++)
cout<<A[i]<<" ";
cout<<endl;
finish5=clock();
}


template<class T>
void an<T>::qsort(T A[],int left,int right)
{
int i,j;
if(left<right)
{
i=left;
j=right+1;
do{
  do{
   i++;
   bj5++;
  }while(A[i]<A[left]);
  do {
   j--;
   bj5++;
  }while(A[j]>A[left]);
  if(i<j)
  {
   swap(A[i],A[j]);count5++;yd5+=3;
  }
    }while(i<j);
swap(A[left],A[j]);
    yd5+=3;
    count5++;
qsort(A,left,j-1);
qsort(A,j+1,right);
}
}



template<class T>  //两路合并排序
void an<T>::merge(T A[],int i1,int j1,int i2,int j2)
{
T *temp=new T[j2-i1+1];
int i=i1,j=i2,k=0;
while(i<=j1&&j<=j2)
if(A[i]<=A[j])
{
temp[k++]=A[i++];bj6++;yd6++;
}
else
{
temp[k++]=A[j++];bj6++;yd6++;
}
while(i<=j1)
{
temp[k++]=A[i++];bj6++;yd6++;
}
while(j<=j2)  
{
temp[k++]=A[j++];yd6++;
}
  for(i=0;i<k;i++)  
  {
   A[i1++]=temp[i];yd6++;
  }
  delete []temp;
}


template<class T>
void an<T>::mergesort(T A[],int n)
{
start6=clock();
int i1,j1,i2,j2;
int size=1;
while(size<n)
{
i1=0;
while(i1+size<n)
{
           i2=i1+size;
      j1=i2-1;
   if(i2+size-1>n-1)
    j2=n-1;
   else j2=i2+size-1;
   merge(A,i1,j1,i2,j2);
   i1=j2+1;
}
size*=2;
}
cout<<"两路合并排序后的数组是："<<endl;
for(int i=0;i<n;i++)
cout<<A[i]<<" ";
cout<<endl;
finish6=clock();
}


template<class T>
void swap(T &a,T &b)
{
int c;
c=a;
a=b;
b=c;
}


void main()
{
    an<int> p;
    int   rand(   void   );    //生成函数rand   播种子的srand   
int n,ch,x=78;
int *array;
    cout<<endl;
    cout<<endl;
cout<<"          *   欢 * 迎 * 进 * 入 * 内 * 排 * 序 * 比 * k较 * 系 * 统    *      "<<endl;
     cout<<endl;
    cout<<"            请输入排序个数n!!!!"<<endl;
    cin>>n;
    array=new int[n];
for(int i=0;i<n;i++)  array[i]=rand()%n+1;
cout<<"随机生成的原数组为："<<endl;
    for(i=0;i<n;i++)  cout<<array[i]<<" ";
cout<<endl;
do{
    cout<<"请选择排序方法或查看各种排序算法的性能比较!!!!"<<endl;
    cout<<"<0>  退出"<<endl;
    cout<<"<1>  直接插入排序"<<endl;
    cout<<"<2>  希尔排序"<<endl;
    cout<<"<3>  简单选择排序"<<endl;
    cout<<"<4>  冒泡排序"<<endl;
    cout<<"<5>  快速排序"<<endl;
    cout<<"<6>  两路合并排序"<<endl;
cout<<"<7>  查看各种排序算法的性能比较"<<endl;
cin>>ch;
switch(ch){
case 1:
     p.insertsort(array,n);
    cout<<"排序算法名称为:直接插入排序! "<<endl;
    cout<<"时间复杂度o(n^2)为:O("<<n*n<<")"<<endl;
          cout<<"数据量大小（多少个）为:"<<n<<endl;
          cout<<"比较次数为:"<<bj1<<endl;
          cout<<"平均移动次数为:"<<yd1<<endl;
          cout<<"交换次数为:"<<count1<<endl;
          cout<<"实际执行时间为:"<<finish1-start1<<endl;
    break;
    case 2:
          p.shellsort(array,n);
          cout<<"排序算法名称为:希尔排序! "<<endl;
          cout<<"时间复杂度O(n*log(2*n))为:O("<<int(n*log(2*n))<<")"<<endl;
          cout<<"数据量大小（多少个）为:"<<n<<endl;
          cout<<"比较次数为:"<<bj2<<endl;
          cout<<"平均移动次数为:"<<yd2<<endl;
          cout<<"交换次数为:"<<count2<<endl;
          cout<<"实际执行时间为:"<<finish2-start2<<endl;
          break;
    case 3:   
          p.selectsort(array,n);
          cout<<"排序算法名称为:简单选择排序! "<<endl;
          cout<<"时间复杂度o(n^2)为:O("<<n*n<<")"<<endl;
          cout<<"数据量大小（多少个）为:"<<n<<endl;
          cout<<"比较次数为:"<<bj3<<endl;
          cout<<"平均移动次数为:"<<yd3<<endl;
          cout<<"交换次数为:"<<count3<<endl;
          cout<<"实际执行时间为:"<<finish3-start3<<endl;
          break;
    case 4:
         p.bubblesort(array,n);
         cout<<"排序算法名称为:冒泡排序! "<<endl;
         cout<<"时间复杂度o(n^2)为:O("<<n*n<<")"<<endl;
         cout<<"数据量大小（多少个）为:"<<n<<endl;
         cout<<"比较次数<为:"<<bj4<<endl;
         cout<<"平均移动次数为:"<<yd4<<endl;
         cout<<"交换次数为:"<<count4<<endl;
         cout<<"实际执行时间为:"<<finish4-start4<<endl;
         break;
    case 5:
      p.quicksort(array,n);
         cout<<"排序算法名称为:快速排序! "<<endl;
         cout<<"时间复杂度O(nlogn)为:O("<<int(n*log(n))<<")"<<endl;
         cout<<"数据量大小（多少个）为:"<<n<<endl;
         cout<<"比较次数为:"<<bj5<<endl;
         cout<<"平均移动次数为:"<<yd5<<endl;
         cout<<"交换次数为:"<<count5<<endl;
         cout<<"实际执行时间为:"<<finish5-start5<<endl;
         break;
    case 6:
         p.mergesort(array,n);
         cout<<"排序算法名称为: 两路合并排序! "<<endl;
         cout<<"时间复杂度O(nlog2n)为:O("<<int(n*log(2*n))<<")"<<endl;
         cout<<"数据量大小（多少个）为:"<<n<<endl;
         cout<<"比较次数为:"<<bj6<<endl;
         cout<<"平均移动次数为:"<<yd6<<endl;
         cout<<"交换次数为:"<<count6<<endl;
         cout<<"实际执行时间为:"<<finish6-start6<<endl;
   break;
case 7:
     p.insertsort(array,n);
           p.shellsort(array,n);
           p.selectsort(array,n);
           p.bubblesort(array,n);
           p.quicksort(array,n);
           p.mergesort(array,n);
          cout<<"      排序算法名称|"<<setw(6)<<"时间复杂度|"<<setw(6)<<"数据量|"<<setw(6)<<"比较次数|"<<setw(6)<<"移动次数|"<<setw(6)<<"交换次数|"<<setw(6)<<"执行时间|"<<endl;           
    cout<<endl;
    cout<<"<1>  直接插入排序:"<<setw(6)<<"o("<<n*n<<")"<<setw(6)<<n<<setw(8)<<bj1<<setw(9)<<yd1<<setw(8)<<count1<<setw(6)<<finish1-start1<<setw(4)<<endl;
    cout<<"<2>  希尔排序:"<<setw(10)<<"o("<<int(n*log(2*n))<<")"<<setw(8)<<n<<setw(6)<<bj2<<setw(9)<<yd2<<setw(8)<<count2<<setw(8)<<finish2-start2<<endl;
    cout<<"<3>  简单选择排序:"<<setw(6)<<"o("<<n*n<<")"<<setw(6)<<n<<setw(6)<<bj3<<setw(10)<<yd3<<setw(9)<<count3<<setw(6)<<finish3-start3<<endl;
    cout<<"<4>  冒泡排序:"<<setw(10)<<"o("<<n*n<<")"<<setw(6)<<n<<setw(6)<<bj4<<setw(8)<<yd4<<setw(8)<<count4<<setw(9)<<finish4-start4<<endl;
    cout<<"<5>  快速排序:"<<setw(10)<<"o("<<int(n*log(n))<<")"<<setw(8)<<n<<setw(8)<<bj5<<setw(6)<<yd5<<setw(8)<<count5<<setw(9)<<finish5-start5<<endl;
    cout<<"<6>  两路合并排序:"<<setw(6)<<"o("<<int(n*log(n))<<")"<<setw(8)<<n<<setw(6)<<bj6<<setw(9)<<yd6<<setw(8)<<count6<<setw(8)<<finish6-start6<<endl;
          cout<<endl;
    break;
    case 0:
    x=0;
     break;
}

}while(x);
}













七、 运行结果分析
1、截图显示：

2、结果分析：
排序方法的选用应该根据具体情况而定，一般应该从以下几个方面综合考虑：
1. 时间复杂性
2. 空间复杂性
从空间复杂性看，所有排序方法分为三类：
归并排序单独属于一类，其空间复杂性为O(n)；
快速排序单独属于一类，其空涓丛有晕?em>O(log2n) ~ O(n)；
其它排序方法归为一类，其空间复杂性为O(1)。
3. 稳定性
所有排序方法可分为两类，一类是稳定的，包括直接插入排序、起泡排序、简单选择排序和归并排序；
另一类是不稳定的，包括希尔排序、快速排序和堆排序。

4. 算法简单性
从算法简单性看，一类是简单算法，包括直接插入排序、简单选择排序和起泡排序；
另一类是改进算法，包括希尔排序、堆排序、快速排序和归并排序，这些算法都很复杂。
5. 记录本身信息量的大小
记录本身信息量越大，移动记录所花费的时间就越多，所以对记录的移动次数较多的算法不利。
排序方法
最好情况
最坏情况
平均情况
直接插入排序： O(n)、 O(n2) 、O(n2)
起泡排序： 0、 O(n2)、 O(n2)
简单选择排序 0、 O(n) 、O(n)
6. 关键码的分布情况
当待排序记录序列为正序时，直接插入排序和起泡排序能达到O(n)的时间复杂度；
对于快速排序而言，这是最坏的情况，此时的时间性能蜕化为O(n2)；
简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键码的分布而改变。