《北邮数据结构实验 第三次实验 排序》由会员分享，可在线阅读，更多相关《北邮数据结构实验 第三次实验 排序（23页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告1实验要求(1)实验目的通过选择下面两个题目之一，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。(2)实验内容使用简单数组实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述
2、各种算法的时间复杂度编写测试main()函数测试排序算法的正确性。 2. 程序分析2.1 存储结构 顺序表: 示意图：a0a1a2a3a4a5a6a7 2.2 关键算法分析（1） 测试数据的产生：正序、逆序、随机数据用两个数组实现乱序、顺序以及逆序数据的排序。基本思想为：随机序列产生一个指定长度的乱序序列，然后通过memcpy()函数拷贝到第二个数组里，第二个数组作为乱序序列的保存数组，每次对第一个数组进行排序，之后拷贝第二个数组中的乱序序列到第一个数组，实现各次乱序排列。只要算法正确（第一步可以检验），之后顺序排列只需反复对第一个数组进行操作即可，再后用第二个数组保存逆序数组，然后同样在每次
3、排序之后复制第二数组存储的乱序序列到第一组，对第一组反复排序即可。 pRandom1=new long intMax+1;pRandom2=new long intMax+1; srand(unsigned)time(NULL); for(int i = 1; i = Max;i+ ) pRandom2i=rand(); memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int);（2） 排序算法：插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。/1/int j=0;/2/ for(int i =
4、2; i = Max;i+) parray0=parrayi;comparetimes0+; /4/parrayj+1=parray0;movetimes0+=2;示意图：r1,r2,r3,ri-1,ri,ri+1,rn 有序区 待插入 无序区希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。int Sort:ShellSort(long int parray)int j=0;for(int d=Max/2;d=1;d/=2)for(int i=d+1;i0 & parray0parrayj;j-=d) parra
5、yj+d=parrayj;movetimes1+;parrayj+d=parray0;movetimes1+=2;return 0;冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。int Sort:BubbleSort(long int parray) int exchange=Max;int bound,j;while(exchange) bound=exchange;exchange=0;for(j=1;jparrayj+1) parray0=parrayj;parrayj=parrayj+1;parrayj+1=parray0;exchange=j;moveti
6、mes2+=3;return 0;示意图：r1,r2,r3,ri-1,ri,ri+1,rn 反序则交换 有序区快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成。int Sort:QuickSort(long int parray)QuickSortRecursion(parray,1, Max);return 0;int Sort:QuickSortRecursion(long int parray, int first=1, int end=Max)if (firstend) int pivot=QuickSo
7、rtPatition(parray, first, end); QuickSortRecursion(parray, first, pivot-1);/左侧子序列排序 QuickSortRecursion(parray, pivot+1, end); /右侧子序列排序return 0;int Sort:QuickSortPatition(long int r, int first, int end )int i=first;int j=end;int temp;while (ij) while (ij & ri= rj) j-; comparetimes3+; /右侧扫描 if (ij) te
8、mp=ri; /将较小记录交换到前面 ri=rj; rj=temp; i+; movetimes3+=3; while (ij & ri= rj) i+; comparetimes3+; /左侧扫描 if (ij) temp=rj; rj=ri; ri=temp; /将较大记录交换到后面 j-; movetimes3+=3; return i; /i为轴值记录的最终位置示意图：r1,r2,r3,ri-1,ri,ri+1,rn rri选择排序：从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并
9、将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。int Sort:SelectSort(long int parray)int i,j,index,temp; for (i=1; iMax; i+) /对n个记录进行n-1趟简单选择排序 index=i; for (j=i+1; j=Max; j+) comparetimes4+;/在无序区中选取最小记录 if (parrayjparrayindex) index=j; if (index!=i) temp=parrayi; parrayi=parrayindex; parrayindex=temp; movetime
10、s4+=3; 示意图：r1,r2,r3,ri-1,ri,ri+1,rn 反序则交换 有序区堆排序：通过建立大根堆或者小根堆，取出根节点，反复调整堆使之保持大根堆或者小根堆，直至最后序列有序。int Sort:HeapSort(long int parray)int i;for (i=Max/2; i=1; i-)HeapSortSift(parray, i, Max) ; for (i=1; iMax; i+) parray0=parrayMax-i+1; parrayMax-i+1=parray1; parray1=parray0; movetimes5+=3; HeapSortSift(p
11、array, 1, Max-i); return 0;void Sort:HeapSortSift(long int parray, int k, int m)int i,j;i=k;j=2*i; /置i为要筛的结点，j为i的左孩子 while (j=m) /筛选还没有进行到叶子 if (jm & parrayjparrayj) comparetimes5+; break; /根结点已经大于左右孩子中的较大者else parray0=parrayi; parrayi=parrayj; parrayj=parray0; movetimes5+=3; i=j; j=2*i; /被筛结点位于原来结点j的位置归并排序：将若干个有序序列两两归并，直至所有待排序的记录都在一个有序序列为止。int Sort:MergeSort(long int parray)long int r1Max+1;int h(1)
