数据结构实验8排序

实验八排序一、实验目的1.熟悉掌握教材中所介绍的几种排序方法。2.学会分析各种内排序算法的性能。二、实验内容随机产生20位整数输入序列，编写程序，按下列排序方法将序列从小到大排序并输出。冒泡排序快速排序纪录每种方法比较次数和移动次数三、实验步骤1、冒泡排序冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复以上过程，仍从第一对数开始比较。如此下去，直至最终完成排序。 2、快速排序基本思想快速排序（Quicksort）是对冒泡排序的一种改进。由C.A.R.Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。实现方法设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。一趟快速排序的算法是：1）设置两个变量I、J，排序开始的时候：I=1，J=N-1；2）以第一个数组元素作为关键数据，赋值给X，即X=A[0]；3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于X的值，让该值与X交换；4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于X的值，让该值与X交换；5）重复第3、4步，直到I=J；算法说明首先为了避免产生的随机数过大，我们限定了了随机数为1-100之间，其次我们分别运用函数产生随机数两次，第一次为使用冒泡排序，第二次为使用快速排序。测试结果分析与探讨在设计中除了注意冒泡排序和快速排序的原理外，还需要注意函数间的套用中出现的形参和实参的类型统一，以及交换两个数值时候，中介参数的使用。附录：源代码源代码列在附录中，要求程序风格清晰易理解，有充分的注释。有意义的注释行不少于30%。#include"stdio.h"#include"time.h"#include"stdlib.h"#include"iostream"usingnamespacestd;voidQuickSort(intp[],intstart,intend){if(start>=end){return;}inti=0,j=0,tmp=0;i=start;j=end-1;do{while(p[i]<p[end]){i++;}while(p[j]>=p[end]){j--;}if(i<j){tmp=p[i];p[i]=p[j];p[j]=tmp;}else{tmp=p[i];p[i]=p[end];p[end]=tmp;}}while(i<j);QuickSort(p,start,i-1);QuickSort(p,i+1,end);}voidPrintArrary(intdata[],intsize){for(inti=0;i<size;++i){cout<<data[i]<<"";}cout<<endl;}voidmain(){ inta[20],i,j,t,flag; intargc[20]; srand((unsigned)time(0)); for(i=0;i<20;i++) a[i]=rand()%100; cout<<"随机产生20个100以内的整数"<<endl; for(i=0;i<20;i++) cout<<a[i]<<""; for(i=0;i<19;i++)/*改进型冒泡法排序*/ { flag=0; for(j=0;j<20-i-1;j++) if(a[j]>a[j+1]) { t=a[j];/*交换a[i]和a[j]*/ a[j]=a[j+1]; a[j+1]=t; flag=1; } if(flag==0)break; } cout<<endl; cout<<"将这20个整数按照冒泡排序进行升序排列"<<endl; for(i=0;i<20;i++) cout<<a[i]<<""; cout<<endl; for(i=0;i<20;i++) argc[i]=rand()%100; cout<<"再次随机产生20个100以内的整数"<<endl; Pr