实验五:排序方法的比较

上传人:lis****210 文档编号:212178756 上传时间:2023-05-22 格式:DOCX 页数:7 大小:48.28KB
收藏 版权申诉 举报 下载
实验五:排序方法的比较_第1页
第1页 / 共7页
实验五:排序方法的比较_第2页
第2页 / 共7页
实验五:排序方法的比较_第3页
第3页 / 共7页
资源描述:

《实验五:排序方法的比较》由会员分享,可在线阅读,更多相关《实验五:排序方法的比较(7页珍藏版)》请在装配图网上搜索。

1、成绩:实验报告课程名称:数据结构实验实验项目排序方法的比较姓 名:李翠超专业:计算机科学与技术班级:计算机16-6学号:1609040307计算机科学与技术学院实验教学中心2017 年12 月 20日实验项目名称:排序方法的比较一、实验目的1. 通过实验掌握排序的基本概念,掌握各种排序的基本思想和算法实现。2. 能够较为灵活的选用某种排序方法解决问题二、实验内容1. 实现常用的内部排序算法并进行比较:如起泡排序、直接插入排序、简单选择排序、 快速排序等至少四种排序算法。试通过随机数据比较各算法的关键字比较次数和关键字移 动次数,以取得直观感受。以实践教学,加深对教材内容的吸收,提升自己。2.

2、冒泡排序的基本思想:通过对待排序序列从后向前(从下标较大的元素开始),依 次比较相邻元素的排序码,若发现逆序则交换,使排序码较小的元素逐渐从后部移向前部 (从下标较大的单元移向下标较小的单元),就象水底下的气泡一样逐渐向上冒。3. 直接插入排序基本思想:把n个待排序的元素看成为一个有序表和一个无序表,开 始时有序表中只包含一个元素,无序表中包含有 n-1 个元素,排序过程中每次从无序表中 取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表 中的适当位置,使之成为新的有序表。4快速排序的基本思想是:任取待排序序列中的某个元素作为基准(一般取第一个元 素),通过一趟排序

3、,将待排元素分为左右两个子序列,左子序列元素的排序码均小于或等 于基准元素的排序码,右子序列的排序码则大于基准元素的排序码,然后分别对两个子序 列继续进行排序,直至整个序列有序。三、实验操作步骤1. 阅读实验内容和要求2. 基本要求:待排序表的表长不小于 100;至少要用 5 组不同的输入数据作测试; 至 少完成四个算法。3. 根据编译的结果,如果错误的及时找出并改正四、实验结果分析 C:U$e5dellDe$lctop回家先吃饭Untitled310.exe1 *include 2 # include J im.-.h define OK 1ERROR:42, 68, 35.1 70, 25

4、. 79. 59. 63. 65. 6. 46,82. 28. 62,92.96,43, 2& 37 V泡排序:1.6, 25. 2& 2& 35. 37. 42. 43.46. 59. 62. 63. 65. 68, 70. 79.82. 92.96 也择誹序:1.6, 2b, 28. 28, 35, 37.42,43, 46, 59. 62,63. 65. 68, 70, 79.82,92,96 玫制卜序1.6, 25. 28. 28. 35, 37. 42,43.46. 59. 62. 63.65. 68. 70. 79.82. 92.96 快迫排序;11.6, 2b. 28. 2& 3

5、5, 37. 42.43.46, 59. 62. 63.65, 68, 70, 79.82, 92,96彳:1 YES: 0 NO:|1擲序前:3,54.93.83. 22.17,19.96.48, 27. 72. 39. 70,13.68.100, 36,95,4V泡40序:3.4,5,13,17.19,22.27. 36, 39, 4& 54, 68, 70, 72,83,93,95, 96, 100 i林排片:3,4.5.13.17.19, 22.27. 36. 39. 48,5九 68, 70, 72.83.93.95,96, 100 | 垃 40 4:3.4, b. 13.17.19

6、. 22. 27, 36. 39, 4& 54.68. 70, 72,83,93.95,96, 100 快速那序:13.4, 5J3.17, 19, 22, 27, 36. 39, 4& 54, 68, 70, 72, 83, 93,95, 96, 100 杏址袋樁#:1 YES; 0 NO:Procoss returned 0 (0x0) oxocut ion time : 4.000 s 紋擀膏 # : to continue.五、源代码#include #include #define OK 1#define ERROR 0#define MAX_LENGTH_INSERT_SORT 7

7、 / 用于快速排序时判断是否选用插入排序阙值#define MAXSIZE 10000 / 用于要排序数组个数最大值,可根据需要修改#define Max 20typedef structint rMAXSIZE+l; /用于存储要排序数组,r0用作哨兵或临时变量int length;/ 用于记录顺序表的长度 SqList;/ 交换 L 中数组 r 的下标为 i 和 j 的值void swap(SqList *L,int i,int j)int temp=L-ri;L-ri=L-rj;L-rj=temp;void print(SqList L)int i;for(i=1; iL.length;

8、 i+) printf(%d,L.ri);printf(%d,L.ri); printf(n);/对顺序表L作冒泡排序void BubbleSort(SqList *L)int i,j;for(i=1; ilength; i+) for(j=L-length-1; j=i; j-) / 注意 j 是从后往前循环 if(L-rjL-rj+1) / 若前者大于后者(注意这里与上一算法的差异) swap(L,j,j+l); 交换 L-rj与 L-rj+l的值 /对顺序表L作简单选择排序void SelectSort(SqList *L)int i,j,min;for(i=1; ilength; i+

9、)min = i;/ 将当前下标定义为最小值下标for (j = i+1; jlength; j+) / 循环之后的数据if (L-rminL-rj)/ 如果有小于当前最小值的关键字min = j;/ 将此关键字的下标赋值给 minif(i!=min)/若min不等于i,说明找到最小值,交换swap(L,i,min);/ 交换 L-ri与 L-rmin的值/对顺序表L作直接插入排序void InsertSort(SqList *L)int i,j;for(i=2; ilength; i+)if (L-riri-l) / 需将 L-ri插入有序子表 L-r0=L-ri; / 设置哨兵 for(j

10、=i-1; L-rjL-r0; j-)L-rj+1=L-rj; /记录后移 L-rj+1=L-r0; /插入到正确位置/堆排序,已知L-rs.m中记录的关键字除L-rs之外均满足堆的定义,/本函数调整L-rs的关键字,使L-rs.m成为一个大顶堆 void HeapAdjust(SqList *L,int s,int m)int temp,j;temp=L-rs;for(j=2*s; j=m; j*=2) / 沿关键字较大的孩子结点向下筛选 if(jrjrj+1)+j; / j 为关键字中较大的记录的下标if(temp=L-rj)break; / rc 应插入在位置 s 上L-rs=L-rj;

11、哈尔滨理工大学计算机科学与技术学院实验教学中心 s=j;L-rs=temp; / 插入/对顺序表L进行堆排序 void HeapSort(SqList *L)int i;for(i=L-length/2; i0; i-) / 把 L 中的 r 构建成一个大根堆 HeapAdjust(L,i,L-length);for(i=L-length; i1; i-) swap(L,1,i); / 将堆顶记录和当前未经排序子序列的最后一个记录交换HeapAdjust(L,l,i-l); / 将 L-rl.i-l重新调整为大根堆/快速排序/交换顺序表L中子表的记录,使枢轴记录到位,并返回其所在位置/ 此时在

12、它之前(后)的记录均不大(小)于它。int Partition(SqList *L,int low,int high)int pivotkey;pivotkey=L-rlow; / 用子表的第一个记录作枢轴记录 while(lowhigh) / 从表的两端交替地向中间扫描 while(lowrhigh=pivotkey) high-;swap(L,low,high);/ 将比枢轴记录小的记录交换到低端 while(lowrlowrlow.high作快速排序void QSort(SqList *L,int low,int high)int pivot;if(lowrlow.high分为二,算出枢

13、轴值 pivot QSort(L,low,pivot-1);/ 对低子表递归排序QSort(L,pivot+1,high);/ 对高子表递归排序/对顺序表L作快速排序void QuickSort(SqList *L)QSort(L,1,L-length);int main()int i,j=0,y=1,e,yy;SqList L0,L1,L2,L3,L4;while(y)/* printf(”请输入需要排序数列:”); for(i=0;iMax; i+) scanf(%d,&e); L0.ri+1=e;*/for(i=0;i=Max; i+) L0.ri+1=rand()%100+1;L0.length=Max;printf(排序前:n”);print(L0);printf(冒泡排序:n”);BubbleSort(&L0);print(L0);printf(选择排序:n”);SelectSort(&L0);print(L0);printf(” 堆排序:n”);HeapSort(&L0);print(L0);printf(快速排序:n);QuickSort(&L0);print(L0);printf(是否继续排序:1 YES; 0 NO:n”); scanf(%d,&yy);y=yy;return 0;

展开阅读全文
温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

copyright@ 2023-2025  zhuangpeitu.com 装配图网版权所有   联系电话:18123376007

备案号:ICP2024067431-1 川公网安备51140202000466号


本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!