实验五：排序方法的比较

《实验五：排序方法的比较》由会员分享，可在线阅读，更多相关《实验五：排序方法的比较（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；