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

《华南农业大学数据结构排序实验程序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告1实验原理直接选择排序每次将无序区第1条记录插入到有序区适当位置。有序区不断扩大，无序区不断缩小。最终无序区为空，有序区包含全部记录。初始取第1条记录为有序区，其它为无序区。有序区也可从数据表的尾部生成。(*……*)(*………*)希尔排序数据表分成若干组，相隔为某个“增量”的记录为一组，各组内直接插入排序；改变增量(一般递减)，再分组再排，直到最后增量为1，所有记录为一组，整体一次直接插入排序。又称“缩小增量排序”(DiminishingIncrementSort)。(*………………………*)冒泡排序设数据表垂直放置，每个记录看

2、作气泡；据轻上重下原则，从下往上扫描，违反本原则的轻气泡，向上“飘浮”，如此反复，直到任何两个气泡都是轻上重下为止。快速排序任选一记录作基准，其它与之比较，小于等于放其前面；大于等于放其后面。一趟排序后，左子序列小于等于基准，右子序列大于等于基准。对两子序列继续同样处理，直至每组只有1个记录，全部记录有序。(*……*)*(*……*)直接选择排序每趟从无序区中选最小记录，与无序区第一个记录交换，则有序区增加一个记录。n-1趟排序后，整个数据表就全部有序了。所有记录组成初始无序区。可看成冒泡排序：比较和交换的是无序区最小和无序区第一个。总比

3、较次数相同，但移动次数少。与直接插入相比：总比较次数多，但移动次数少。堆排序巧妙的树形选择排序，不需专门设立树。将R[1]到R[n]看成完全二叉树的顺序存储结构，利用双亲和孩子间的内在关系来选择关键字最小（或最大）的记录。为保证时间性能，输出堆顶后，新堆不要完全重建，应在原堆上调整得到；为保证空间性能，输出堆顶时，不另用空间存放，可将它与无序区尾记录交换位置。归并排序初始数据表看成n个长度为1的有序子表，两两归并，得到én/2ù个有序的子表(当n为奇数时，归并后仍有一个长度为1的子表)；再把这些有序子表两两归并，如此反复，直到最后得到一

4、个长度为n的有序表为止。2.实验程序#defineCPPC++#defineMPPM++#defineMP2M+=2#defineMP3M+=3#include#include#include#include#include#includeconstintmaxsize=100000000;//数据表容量typedefintdatatype;typedefstruct{datatypekey;//关键字域//other

5、typeother;//其它域}rectype;//记录类型typedefrectypelist[maxsize+2];//数据表类型，0号单元不用__int64C,M;//比较和移动次数voidcheck(listR,intn){//检验排序结果inti;for(i=2;i<=n;i++)if(R[i].key

6、<=R[i-1].key)continue;//R[i]大于有序区最后一个记录，则本趟不需插入MPP,R[0]=R[i];//R[0]是监视哨j=i-1;do{//查找R[i]的插入位置MPP,R[j

7、+1]=R[j];j--;//记录后移，继续向前搜索}while(CPP,R[0].key=R[i-1].key)continue;MPP,x=R[i];//待排记录暂存到xj=i-1;do{//顺序比较和移动MPP,R[j+

8、1]=R[j];j--;}while(j>=1&&(CPP,x.key