实验报告-各种排序方法及其实现

1、计算机学院实验报告专用纸姓名xxx班级课程名称数据结构任课教师实验项目名称各种排序方法及其实现指导教师实验组别x同组者无教师评语及成绩：卖验成绩：教师签字：实验室：网络实验室机号:网38实验h期：2010年6月25 h（请按照实验报告的有关要求书写。一般必须包括：1、实验目的；2、实验内容；3、实验步骤与方法；4、实验数据与程序清单；5、出现的问题与解决方法；6、实验结果、结果分析与体会等内容）1、实验目的（1 ）理解排序的定义和各种排序方法的特点（2）掌握各种排序方法的排序过程及其依据的原则（3）学握各种排序方法的时间复杂度的分析方法2、实验内容（1）实现总接排序、冒泡、总接选择、快速、堆、

2、归并排序算法;（2）比较各种算法的运行速度。3、实验步骤和方法（1）编写各种排序法函数；（2）设计一个测试主函数，实现对各种排序算法的测试。（3）分析程序的运行结呆。4、实验数据与程序清单计算机学院实验报告附页姓名xxx班级实验名称各种排序方法及其实现#include，zstdio. h"#include"stdlib. h"ttdefine max 100/假设文件长度typedef struct /定义记录类型int key;/关键字项rectype;typedef rectype seqlist max+1 ; /seqlist为顺序表,表中第0个元素作为哨

3、兵int n;顺序表实际的长度/直接插入排序法void insertsort(seqlist r)/对顺序表r中的记录r1n按递增序进行插入排序int i, j；for (i=2; i<=n; i+)/依次插入 r, ,rnif (ri. key<ri-l. key) /若ri key大于等于有序区中所有的keys,则ri留在原位ro=ri;j=i-l;/r0是 ri的副本do/从右向左在有序区rli-1中查找ri的位置rj+l=rj;/将关键字大于ri key的记录后移j一;while (r 0.key<rj.key);rj+1=ro;/endif/=冒泡排序= typed

4、ef enum false, true boolean; void bubblesort(seqlist r) int i, j;booleanfor(i=l;i<n;i+) exchange二false;for (j=n-l; j>=i; j) if (rj+1 key<rj. key) ro=rj+l;rj+1二rj;rj二 r0； exchange二true;当ri keynrj key是终止/ri插入到正确的位置上/false 为 0, true 为 1/自下向上扫描对r做冒泡排序/交换标志exchange;/最多做n-1趟排序 本趟排序开始前，交换标志应为假/対当前

5、无序区rin自下向上扫描 两两比较，满足条件交换记录 /r0不是哨兵，仅做暂存单元/发牛了交换，故将交换标志置为真木趟排序未发生交换，提前终止算法if(! exchange)return;/ endfor (为循环) 计算机学院实验报告附页姓名xxx班级实验名称各种排序方法及其实现/次划分函数二int partition(seqlist r, int i, int j)/ 对rij做一次划分，并返回基准记录的位置rectype pivot=ri;/用第一个记录作为基准while(i<j) /从区间两端交替向小间打描，直到i二jwhile(i<j &&rj. key&

6、gt;二pivot, key)/基准记录 pivot 相当与在位置 i 上j；/从右向左扫描，查找第一个关键字小于pivot, key的记录rjif (i<j)/若找到的 rjl key < pivot, key,则ri+二rj; 交换ri和rj,交换后i指针加1while(i<j &&ri. key<=pivot. key)/基准记录 pivot 相当与在位置 j 上i卄；/从左向右扫描，查找第一个关键字小于pivot, key的记录riif (i<j)若找到的 rij. key > pivot, key,则rj-=ri; /交换r订和rj

7、,交换后j指针减1ri二pivot;此吋，i=j,基准记录已被最后定位return i;/返回基准记录的位置/=二=快速排序=void quicksort(seqlist r, int low, int high)/rlow. high快速排序int pivotpos;/划分后基准记录的位置if(lov<high) /仅当区间长度人于1时才排序pivotpos=partition(r, low, high) ; /对 rlow. high做一次划分，得到基准记录的位置quicksort (r, low, pivotpos-1) ;/对左区间递归排序quicksort (r, pivotp

8、os+1, high) ;/対右区间递归排序/=二直接选择排序=void selectsort(seqlist r)int i, j, k;for (i=l; in; i+) /做第 i 趟排序(lwiwn-1)k二 i ；for (j=i+l; j<=n; j+)/在当前无序区rin中选key最小的记录rkif (rj key<rk. key)k二j;/k记卜目前找到的最小关键字所在的位置if(k!=i) /交换 ri和 rkr0=r订;ri=rk;rk二r0; /endif计算机学院实验报告附页姓名xxx班级实验名称各种排序方法及其实现 /endfor/大根堆调整函数void

9、heapify( seqlist r, int low, int high)将r low., high调整为人根堆，除rlow外，其余结点均满足堆性质int 1 arge;/large指向调整结点的左、右孩了结点中关键字较大者rectype temp二rlow; /暂存调整结点for (large=2*low; large二high; large*二2) /rlow是当前调整结点/若large>high,则表示rlow是叶子,调整结束;否则先令large扌旨向rlow的左孩子 if(1arge<high && rlarge. key<rlarge+l. key

10、)large+; /若rlov的右孩了存在关键字大于左兄弟，则令large指向它 /现在rlarge是调整结点rlow的左右孩子结点中关键字较大者辻(temp. key>=rlarge, key) /temp 始终对应 rlowbreak; 当前调整结点不小于其孩子结点的关键字，结束调整row=rlarge;/相当于交换了 rlow和 rlargelow= large; /令low指向新的调整结点，相当于temp已筛下到large的位置rlow=temp;/将被调整结点放入最终位置上/=构造大根堆=void buildheap(seqlist r)/将初始文件rl.n构造为堆int i;

11、for(i=n/2;i>0;i-)heapify (r, i, n);/将 ri. n调整为大根堆/=堆排序=void heapsort(seqlist r)对rl.n进行堆排序，不妨用r0做暂存单元int i;buildheap(r) ;/将rl. n构造为初始人根堆for (i=n; i>l; i) /对当前无序区rl. i进行堆排序，共做n-1趟。ro=r1; rl=ri ;ri二r0;将堆顶和堆中最后一个记录交换heapify (r, 1, i-1); 将rl. it重新调整为堆，仅有rl可能违反堆性质。/二二二=将两个冇序的了序列r|ow. .m和rm+1. high归并

12、成冇序的序列rlow. high = void merge(seqlist r, int low, int m, int high)int i=low, j=m+l, p=0; /置初始值rectype *r1; /rl 为局部量计算机学院实验报告附页姓名xxx班级实验名称各种排序方法及其实现rl= (rectype *)malloc(high-low+1)*sizeof (rectype); 申请空间 while(i<=m && j二high)/两个子序列非空时収其小者输岀到rlp上rlp+ = (ri. key<=rj. key)? ri+:rj+;while(

13、i<=m)/若第一个子序列非空，则复制剩余记录到r1rlp+=ri+;while(j<=high)/若第一个子序列非空，则复制剩余记录到r1中rlp+=rj+；for(p=0, i=low;i<=high;p+, i+)ri二rlp；/归并完成后将结果复制回r low., high/对rl.n做趟归并排序void mergepass(seqlist r, int length)int i;for(i=l;i+2*lengtht二n;i二i+2*length)merge(r, i, i+length-1, i+2*length-l); 归并长度为 length 的两个相邻的了序

14、列 if (i+length-l<n)/尚有一个子序列，其中后一个长度小于lengthmerge(r, i, i+length-1, n) ;/归并最后两个子序列/注意：若iwn且i+lengthtmn时，则剩余一个子序列轮空，无须归并= 自底向上对ri.山做二路归并排序二= void mergesort(seqlist r)int length;for (length=l; lengthn; length*二2)/做lgn趟排序mergcpass (r, length) ;/有序长度2n 吋终止/=输入顺序表=void input_int(seqlist r)int i;printf

15、(z，please in put num( in t):“)；scanf ("%d", &n);printf("plase input %d integer:, n);for(i=l;i<=n;i+)scanf ("%d", &r i . key);/=输出顺序表=void output_int(seqlist r)int i;计算机学院实验报告附页printf (z/t7: exitn");/输入整数1-7,选择排序方式printf (z/t5: heap sortn"); printf (z，t6:

16、 merge sortn)；scanf &i);值为1,直接插入排序值为2,冒泡法排序值为3,快速排序/值为4,肓接选择排序值为5,堆排序/值为6,归并排序/值为7,结朿程序switch (i) case 1: insertsort(r); break;case 2: bubblesort(r); break;case 3: quicksort(r, 1, n); break;case 4: selectsort(r); break; case 5: heapsort(r); break;case 6: mergesort(r); break; case 7: exit (0);pri

17、ntf (z/sort reult：z/); output_int(r);5、实验结果please input num(int):10plase input 10 integer:265301751129937863742694计算机学院实验报告附页姓名xxx班级实验名称各种排序方法及其实现76438* select *1: insert sort2: bubble sort3: quick sort4: straight selection sort5: heap sort6: merge sort7: exitztszts129, 265, 301, 751, 937, 863, 742,

18、 694,76, 43&129,265,301,751,863,937,742,694,76,43&129,265,301,742,751,863,937,694,76,43&129,265,301,694,742,751,863,937,76,43&76,129,265,301,694,742,751,863,937,43&76,129,265,301,43&694,742,751,863,937,sort reu 11:76, 129, 265, 301, 43& 694, 742, 751, 863, 937,276, 265, 3

19、01,751, 129,937, 863,742, 694,438,76, 129, 265,301, 751,438, 937,863, 742,694,76, 129, 265,301, 438,751, 694,937, 863,742,76, 129, 265,301, 438,694, 751,742, 937,863,76, 129, 265,301, 438,694, 742,751, 863,937,sort reult: 76, 129, 265, 301, 43& 694, 742, 751, 863, 937,376, 129, 265,751, 937,863,

20、 742,694, 301,438,76, 129, 265,751, 937,863, 742,694, 301,438,76, 129, 265,438, 301,694, 742,751, 863,937,76, 129, 265,301, 438,694, 742,751, 863,937,76, 129, 265,301, 438,694, 742,751, 863,937,76, 129, 265,301, 438,694, 742,751, 863,937,sort reu 11: 76,129, 265, 301,43&694,742,751, 863, 937,476

21、, 301, 751,129, 937,863, 742,694, 265,438,76, 129, 751,301, 937,863, 742,694, 265,438,76, 129, 265,301, 937,863, 742,694, 751,438,76, 129, 265,301, 438,863, 742,694, 751,937,76, 129, 265,301, 438,694, 742,863, 751,937,76, 129, 265,301, 438,694, 742,751, 863,937,计算机学院实验报告附页姓名xxx班级实验名称各种排序方法及其实现sort reu 11:76,129,265,301,43&694,742,751,863,937,o863, 694, 751, 265, 438, 301, 742, 129, 76, 937, 751, 694, 742, 265, 438, 301, 76, 129, 863, 937, 742, 694, 301, 265, 438, 129, 76, 751, 863, 937,