22、排序实验(二)

实验二十二排序实验(二)一、实验目的1、掌握用VC工具上机调试集合结构基于交换策略的排序算法。2、掌握在线性表的顺序存储结构下冒泡排序和快速排序算法实现。二、实验学时2学时三、实验类型验证型四、实验内容1、数据集合的顺序存储结构下冒泡排序算法实现。2、数据集合的顺序存储结构下快速排序算法实现。五、实验原理1、基于交换策略的排序概述交换排序的基本思想是两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止，基于交换策略的排序有冒泡排序和快速排序。2、冒泡排序和快速排序冒泡排序是对n个记录从前往后两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，得到一个关键字最大的记录交换到第n个位置，然后对剩余的前n-1个元素继续从前往后两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，得到一个关键字最大的记录交换到第n-1个记录的位置，如此重复直到n个关键字全部按关键字有序。快速排序是通过比较关键字、交换记录，以某个记录为枢轴，将待排序数据分成两部分，其中一部分所有记录的关键字大于等于枢轴记录的关键字，另一部分所有记录的关键字小于枢轴记录的关键字。快速排序对各部分不断划分，直到整个序列按关键字有序。2、基于交换策略排序的基本算法(1)voidCreateSqList(SqList*L)/*创建线性表*/(2)voidBubbleSort(SqList*L)/*冒泡排序算法*/(3)intPartition(SqList*L,intlow,inthigh)/*一趟快速排序寻找枢轴*/(4)voidQSort(SqList*L,ints,intt)/*对数据元素区间[s,t]进行快速排序*/(5)voidQuickSort(SqList*L)/*对顺序表L进行快速排序*/(6)Display(SqList*L)/*输出线性表*/(7)voidmenu()/*定义菜单*/(8)voidfunc()/*封装的功能函数*/3、模块层次图要求画出基于交换策略的排序程序模块层次图。如图所示图19基于交换策略的排序程序算法模块层次图4、关键算法NS图六、测试数据：1、冒泡排序线性表长度：6线性表：42,21,89,15,43,282、快速排序线性表长度：6线性表：42,21,89,15,43,28七、实验步骤及要求用VC语言编程实现线性表的冒泡排序和快速排序算法。1.输入操作序号1选择冒泡排序；2.输入顺序表长度及相应的顺序表；3.输出顺序表；4.输出冒泡排序结果；5.输入操作序号2选择快速排序；6.输入顺序表长度及相应的顺序表；7.输出顺序表；8.输出快速排序结果；9.程序运行结束。八、运行结果图24冒泡排序算法运行图图快速排序算法运行图九、思考问题结合实验过程，回答下列问题：1、思考冒泡排序算法运行步骤？试写出相应的算法。2、思考快速排序算法运行步骤？试写出相应的算法。十、实验报告要求1、调试程序过程中遇到的问题及解决方案；2、本次实验的结论与体会。程序附录：基于线性表的交换类策略排序算法的代码。#includestdio.h#includeprocess.h#defineMAXSIZE20/*最大的空间数量*/typedefintKeyType;typedefstruct{KeyTypekey;/*只有唯一的关键字*/}RedType;typedefstruct{RedTyper[MAXSIZE+1];intlength;}SqList;/*数据元素组织的结构*/voidCreateSqList(SqList*L)/*创建线性表*/{inti;printf(请输入数据元素的个数:);scanf(%d,&L-length);printf(请输入数据元素:\n);for(i=1;i=L-length;++i)scanf(%d,&L-r[i]);}voidBubbleSort(SqList*L)/*冒泡排序*/{inti=L-length,j,temp;intlastExchangeIndex;while(i1){lastExchangeIndex=1;for(j=1;ji;j++)if(L-r[j+1].keyL-r[j].key){temp=L-r[j+1].key;L-r[j+1].key=L-r[j].key;L-r[j].key=temp;lastExchangeIndex=j;}i=lastExchangeIndex;}}intPartition(SqList*L,intlow,inthigh)/*一趟快速排序寻找枢轴*/{intkey;key=L-r[low].key;while(lowhigh){while(lowhigh&&L-r[high].key=key)--high;L-r[low].key=L-r[high].key;;while(lowhigh&&L-r[low].key=key)++low;L-r[high].key=L-r[low].key;}L-r[low].key=key;returnlow;}voidQSort(SqList*L,ints,intt)/*对区间[s,t]进行快速排序*/{intpivotloc=Partition(L,s,t);if(t-s=1)return;QSort(L,s,pivotloc-1);QSort(L,pivotloc+1,t);}voidQuickSort(SqList*L)/*对顺序表L进行快速排序*/{QSort(L,1,L-length);}Display(SqList*L)/*输出线性表*/{inti;printf(序号\t\t);for(i=1;i=L-length;++i)printf(%d\t,i);printf(\n);printf(数据元素\t);for(i=1;i=L-length;++i)printf(%d\t,L-r[i]);printf(\n);}voidmenu(){printf(*************************************************************\n);printf(1:冒泡排序;\n);printf(2:快速排序;\n);printf(0:退出;\n);printf(*************************************************************\n);}voidfunc(){inti;SqListl;while(1){menu();printf(请选择:\n);scanf(%d,&i);switch(i){case1:{printf(您所选择的是冒泡排序方法。\n);CreateSqList(&l);printf(数据集合输出:\n);Display(&l);BubbleSort(&l);printf(冒泡排序输出:\n);Display(&l);break;}case2:{printf(您所选择的是快速排序方法。\n);CreateSqList(&l);printf(数据集合输出:\n);Display(&l);printf(快速排序输出:\n);QuickSort(&l);Display(&l);break;}case0:exit(1);default:{printf(输入命令错误，请重新输入!\n);break;}menu();printf(请选择:\n);scanf(%d,&i);}}}main(){func();}