实验五：排序方法的比较.doc

成绩：实 验 报 告课程名称：数据结构实验实验项目：排序方法的比较姓 名：李翠超专 业：计算机科学与技术班 级：计算机16-6学 号：1609040307计算机科学与技术学院实验教学中心2017 年12月 20日哈尔滨理工大学计算机科学与技术学院实验教学中心 实验报告实验项目名称： 排序方法的比较 一、实验目的 1. 通过实验掌握排序的基本概念，掌握各种排序的基本思想和算法实现。2.能够较为灵活的选用某种排序方法解决问题二、实验内容 1.实现常用的内部排序算法并进行比较：如起泡排序、直接插入排序、简单选择排序、快速排序等至少四种排序算法。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。以实践教学，加深对教材内容的吸收，提升自己。2. 冒泡排序的基本思想：通过对待排序序列从后向前（从下标较大的元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部（从下标较大的单元移向下标较小的单元），就象水底下的气泡一样逐渐向上冒。3. 直接插入排序基本思想：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。4快速排序的基本思想是：任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。三、实验操作步骤 1.阅读实验内容和要求2.基本要求：待排序表的表长不小于100；至少要用5组不同的输入数据作测试； 至少完成四个算法。3.根据编译的结果，如果错误的及时找出并改正四、实验结果分析 五、源代码#include #include #define OK 1#define ERROR 0#define MAX_LENGTH_INSERT_SORT 7 / 用于快速排序时判断是否选用插入排序阙值#define MAXSIZE 10000 / 用于要排序数组个数最大值，可根据需要修改#define Max 20typedef struct int rMAXSIZE+1;/ 用于存储要排序数组，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; 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+1);/ 交换L-rj与L-rj+1的值 / 对顺序表L作简单选择排序void SelectSort(SqList *L) int i,j,min; for(i=1; ilength; i+) min = i;/ 将当前下标定义为最小值下标 for (j = i+1; jlength; j+) / 循环之后的数据 if (L-rminL-rj)/ 如果有小于当前最小值的关键字 min = j;/ 将此关键字的下标赋值给min if(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-1) / 需将L-ri插入有序子表 L-r0=L-ri; / 设置哨兵 for(j=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; 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,1,i-1); / 将L-r1.i-1重新调整为大根堆 / 快速排序*/ 交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置/ 此时在它之前(后)的记录均不大(小)于它。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一分为二，算出枢轴值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); SelectSo