华南农业大学数据结构排序实验程序.doc

实验报告 1 实验原理 直接选择排序 每次将无序区第1条记录插入到有序区适当位置。有序区不断扩大，无序区不断缩小。最终无序区为空，有序区包含全部记录。初始取第1条记录为有序区，其它为无序区。有序区也可从数据表的尾部生成。 (* … … *)(* … … … *) 希尔排序 数据表分成若干组，相隔为某个“增量”的记录为一组，各组内直接插入排序；改变增量(一般递减)，再分组再排，直到最后增量为1，所有记录为一组，整体一次直接插入排序。又称“缩小增量排序”(Diminishing Increment Sort)。 (* … … … … … … … … … *) 冒泡排序 设数据表垂直放置，每个记录看作气泡；据轻上重下原则，从下往上扫描，违反本原则的轻气泡，向上“飘浮”，如此反复，直到任何两个气泡都是轻上重下为止。 快速排序 任选一记录作基准，其它与之比较，小于等于放其前面；大于等于放其后面。一趟排序后，左子序列小于等于基准，右子序列大于等于基准。对两子序列继续同样处理，直至每组只有1个记录，全部记录有序。(* … … *) * (* … … *) 直接选择排序 每趟从无序区中选最小记录，与无序区第一个记录交换，则有序区增加一个记录。n-1趟排序后，整个数据表就全部有序了。所有记录组成初始无序区。可看成冒泡排序：比较和交换的是无序区最小和无序区第一个。总比较次数相同，但移动次数少。与直接插入相比：总比较次数多，但移动次数少。 堆排序 巧妙的树形选择排序，不需专门设立树。将R[1]到R[n]看成完全二叉树的顺序存储结构，利用双亲和孩子间的内在关系来选择关键字最小（或最大）的记录。为保证时间性能，输出堆顶后，新堆不要完全重建，应在原堆上调整得到；为保证空间性能，输出堆顶时，不另用空间存放，可将它与无序区尾记录交换位置。 归并排序 初始数据表看成n个长度为1的有序子表，两两归并，得到?n/2? 个有序的子表(当n为奇数时，归并后仍有一个长度为1的子表)；再把这些有序子表两两归并，如此反复，直到最后得到一个长度为n的有序表为止。 2.实验程序 #define CPP C++ #define MPP M++ #define MP2 M+=2 #define MP3 M+=3 #includeiostream.h #include fstream.h #include iomanip.h #include stdlib.h #include time.h #include math.h const int maxsize=100000000; //数据表容量 typedef int datatype; typedef struct { datatype key; //关键字域 // othertype other; //其它域 } rectype; //记录类型 typedef rectype list[maxsize+2]; //数据表类型，0号单元不用 __int64 C,M; //比较和移动次数 void check(list R,int n) { //检验排序结果 int i; for(i=2;i=n;i++) if(R[i].keyR[i-1].key) {coutError!\n;return;} coutCorrect! ; } void disp(list R,int n) { //显示排序后的结果 int i; for(i=1;i=n;i++) { coutsetw(4)R[i].key; // if(i%20==0) coutendl; } coutendl; } void InsertSort1(list R,int n) {//直接插入排序，带监视哨(并不改变关键字次数) int i,j; for(i=2;i=n;i++) { //依次插入R[2],R[3],…,R[n] if(CPP,R[i].key=R[i-1].key) continue; //R[i]大于有序区最后一个记录，则本趟不需插入 MPP,R[0]=R[i]; //R[0]是监视哨 j=i-1; do { //查找R[i]的插入位置 MPP,R[j+1]=R[j];j--;