资源描述：
《北邮大数据结构实验 第三次实验 排序.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构实验报告1．实验要求(1)实验目的通过选择下面两个题目之一，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。(2)实验容使用简单数组实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。3、对于这三类数据，比较上述排序算法中不同算法的执行时间
2、，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试排序算法的正确性。2.程序分析2.1存储结构顺序表:示意图：a0a1a2a3a4a5a6a72.2关键算法分析（1）测试数据的产生：正序、逆序、随机数据用两个数组实现乱序、顺序以及逆序数据的排序。基本思想为：随机序列产生一个指定长度的乱序序列，然后通过memcpy()函数拷贝到第二个数组里，第二个数组作为乱序序列的保存数组，每次对第一个数组进行排序，之后拷贝第二个数组中的乱序序列到第一个数组，实现各次乱序排列。只要算确（第一步可以检验）
3、，之后顺序排列只需反复对第一个数组进行操作即可，再后用第二个数组保存逆序数组，然后同样在每次排序之后复制第二数组存储的乱序序列到第一组，对第一组反复排序即可。<1>pRandom1=newlongint[Max+1];pRandom2=newlongint[Max+1];<2>srand((unsigned)time(NULL));for(inti=1;i<=Max;i++)pRandom2[i]=rand();<3>memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(longint));（1）
4、排序算法：<1>插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。/1/intj=0;/2/for(inti=2;i<=Max;i++)parray[0]=parray[i];comparetimes[0]++;/4/parray[j+1]=parray[0];movetimes[0]+=2;示意图：r1,r2,r3,…,ri-1,ri,ri+1,…,rn有序区待插入无序区<2>希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插
5、入排序。intSort::ShellSort(longintparray[]){intj=0;for(intd=Max/2;d>=1;d/=2){for(inti=d+1;i<=Max;i++){parray[0]=parray[i];comparetimes[1]++;for(j=i-d;j>0&&parray[0]冒泡排序：
6、两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。intSort::BubbleSort(longintparray[]){intexchange=Max;intbound,j;while(exchange){bound=exchange;exchange=0;for(j=1;jparray[j+1]){parray[0]=parray[j];parray[j]=parray[j+1];parray[j+1]=parray[0];excha
7、nge=j;movetimes[2]+=3;}}}return0;}示意图：r1,r2,r3,…,ri-1,ri,ri+1,…,rn反序则交换有序区<4>快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成。intSort::QuickSort(longintparray[]){QuickSortRecursion(parray,1,Max);return0;}intSort::QuickSortRecursion(longintparray[],intfirs
8、t=1,intend=Max){if(first
