实验7： 内部排序算法比较

1、实验7： 内部排序算法比较1、 问题描述程序对以下4种内部排序（冒泡排序、直接插入排序、简单选择排序、快速排序）算法进行实测比较，测试各种算法在对同样的数据排序时的比较次数和移动次数。二、输入与输出输入：根据用户需要输入待排表的表长（100至1000）和不同测试数据的组数（8至18），不输入则按照默认值进行测试输出：每次测试完毕，列表显示各种比较指标值：比较次数和移动次数2、 需求分析1.本演示程序对以下4种常见的内部排序算法进行实测比较：冒泡排序、直接插入排序、简单选择排序、快速排序2.待排序表的元素的关键字为整数。用正序、逆序和不同乱序程度的不同数据做测试比较。比较的指标为由关键字参加的比

2、较次数和关键字的移动次数（关键字交换计为3次移动）3.演示程序以用户和计算机的对话方式执行，即在计算机终端上菜单，根据用户需要输入待排表的表长（100至1000）和不同测试数据的组数（8至18），不输入则按照默认值进行测试。四、开发工具与环境硬件设备：微型计算机系统软件环境：操作系统Windows，开发工具Devc+五、功能分析存储结构typedef int Typekey;typedef struct Typekey key;Type;typedef struct Type rMAXSIZE+1;/顺序表 int length;PList;/排序表 函数一览表int OneTimeSqCre

3、ate(PList &L)/*手动输入创建排序序列函数*/int ManyTimeSqCreate(PList &L,int m)/*自动生成排序序列函数*/void BubbleSort(PList &L) /*冒泡排序*/void InsertSort(PList &L)/*插入排序*/void SelectSort(PList &L)/*简单选择排序*/int Partition(PList &L,int low,int high)/*一次快速排序*/void QSort(PList &L,int low,int high)/*递归

4、形式的快速排序算法*/void QuickSort(PList &L)/*快速排序*/六、程序代码#include <iostream>#include <malloc.h>#include <stdlib.h>#include <time.h>#define MAXSIZE 10000using namespace std;typedef int Typekey;int compCount; /关键字的比较次数int shiftCount; /关键字的移动次数 typedef struct Typekey key;Type;typede

5、f struct Type rMAXSIZE+1;/顺序表 int length;PList;/排序表 int OneTimeSqCreate(PList &L)/手动输入创建排序序列函数 int x,h;for ( x=1; 1; x+)cin>>h;L.rx.key=h ;if(getchar()='n')/只读入一行，换行则终止 break;L.length=x;int ManyTimeSqCreate(PList &L,int m)/自动生成排序序列函数 L.length=m;for (int x=1; x<=m; x+)L.rx.ke

6、y= rand() % m;/随机数的取值范围为0kreturn 1;void BubbleSort(PList &L) /冒泡排序int i,j,l,m=0,n=0;for(i=1;i<=L.length-1;+i)/只需要比较length-1次 for(j=1;j<=L.length-i;+j)/内层循环所谓的冒泡，将最大值放到末尾 +m;/比较次数 if(L.rj.key>L.rj+1.key) l=L.rj.key; L.rj.key=L.rj+1.key; L.rj+1.key=l; n+=3;/关键字移动次数 cout<<endl<<

7、;" 冒泡排序:"cout<<"比较次数:"<<m;cout<<" 交换次数:"<<n<<endl; void InsertSort(PList &L)/插入排序int i,j,m=0,n=0;/m是比较次数，n是交换次数 cout<<endl;for(i=2;i<=L.length;+i) if(L.ri.key<L.ri-1.key) +m;/比较次数加1 n+=3;/移动次数加3，按实验报告要求一次交换代表3次移动 L.r0=L.ri;/

8、设置哨兵 L.ri=L.ri-1;/后移一位 for(j=i-2;L.r0.key<L.rj.key;-j)/一直找到该插入的位置 +m;/ L.rj+1=L.rj;/后移元素 L.rj+1=L.r0;/将哨兵也就是原来的Li插入序列 cout<<" 直接插入排序:"cout<<"比较次数:"<<m;cout<<" 交换次数:"<<n<<endl; void SelectSort(PList &L) /简单选择排序int l,i,j,m=0,n=0;

9、/m是比较次数，n是移动次数 cout<<endl;for(i=1;i<L.length;+i) L.r0=L.ri; j=i+1;/从j开始寻找最小元素 l=i;/l是最小元素的位置 for(j;j<=L.length;+j) +m;/比较次数加1 if(L.r0.key>L.rj.key)/表明j处key值更小 l=j;/记录下j的值 L.r0=L.rj; if(l!=i)/需要交换位置 n+=3;/移动次数加3，按实验报告要求一次交换代表3次移动 L.rl=L.ri; L.ri=L.r0; cout<<" 简单选择排序:"co

10、ut<<"比较次数:"<<m;cout<<" 交换次数:"<<n<<endl<<endl; int Partition(PList &L,int low,int high)/一次快速排序 int pivotkey;/中间轴 L.r0=L.rlow;/记录轴元素 pivotkey=L.rlow.key;/轴取low while(low<high) while(low<high&&L.rhigh.key>=pivotkey) +compCount

11、;/比较次数加1 -high;/high左移 shiftCount+=3;/移动次数加3，按实验报告要求一次交换代表3次移动 L.rlow=L.rhigh;/此时应当交换位置 while(low<high&&L.rlow.key<=pivotkey) +compCount;/比较次数加1 +low; shiftCount+=3;/移动次数加3，按实验报告要求一次交换代表3次移动 L.rhigh=L.rlow;L.rlow=L.r0;/找到位置插入轴元素 return low;/返回位置 void QSort(PList &L,int low,int high

12、)/递归形式的快速排序算法int Piv;/轴元素位置 if(low<high) Piv=Partition(L,low,high); QSort(L,low,Piv-1);/ 左递归 QSort(L,Piv+1,high);/右递归 void QuickSort(PList &L)/快速排序 int i;QSort(L,1,L.length);cout<<" 快速排序:"cout<<"比较次数:"<<compCount;cout<<" 交换次数:"<<shif

13、tCount<<endl<<endl;compCount=0;shiftCount=0; int main()int i,k,h,n,m;PList L,alist,blist,clist,dlist;cout<<"排序模式选择"<<endl;cout<<"1.手动输入待排序序列 2.系统自动生成待排序序列 : "cin>>h;if(h=1)/手动输入模式 OneTimeSqCreate(L);alist=blist=clist=dlist=L;BubbleSort(L);Inser

14、tSort(alist);SelectSort(blist);QuickSort(clist);cout<<"排序后序列：" for(i=1;i<=L.length;i+)cout<<" "<<L.ri.key; else/自动生成模式 cout<<"输入想要排序的测试组数n和表长m，程序会帮你生成随机序列:"cin>>n>>m;k=1;while(k+<=n)cout<<endl<<"第"<<k

15、-1<<"次排序"<<endl; ManyTimeSqCreate(L,m);alist=blist=clist=dlist=L;BubbleSort(L);InsertSort(alist);SelectSort(blist);QuickSort(clist);return 0;七、运行测试1、手动输入递增序列 1 2 3 4 5 6 7 8 9图的创建1、 手动输入递减序列 9 8 7 6 5 4 3 2 13. 生成随机序列8组，每一个测试序列的表长度为100得到测试结果如下表所示组数1234排序算法比较次数交换次数比较次数交换次数比较次数交换

16、次数比较次数交换次数冒泡排序49507827495076234950693049507407直接插入排序2609273254127623102702469285简单选择排序4950282495028249502854950291快速排序587984660948669930675930组数5678排序算法比较次数交换次数比较次数交换次数比较次数交换次数比较次数交换次数冒泡排序49507467495066544950719449507479直接插入排序2489291221827923982882493285简单选择排序4950273495027349502854950273快速排序596924623918630978677954可以得到4种排序算法的平均比较和移动次数如下表排序算法平均比较次数关键字平均移动次数冒泡排序49507216直接插入排序2398282简单选择排序4950279快速排序633936可以看出快速排序的平均比较次数最少，而直接插入排序和简单选择排序的平均移动次数最少，综合看来