北邮数据结构实验-第三次实验-排序

第1页数据结构实验报告1．实验要求(1)实验目的通过选择下面两个题目之一，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。(2)实验内容使用简单数组实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试排序算法的正确性。2.程序分析2.1存储结构顺序表:示意图：2.2关键算法分析（1）测试数据的产生：正序、逆序、随机数据用两个数组实现乱序、顺序以及逆序数据的排序。基本思想为：随机序列产生一个指定长度的乱序序列，然后通过memcpy()函数拷贝到第a0a1a2a3a4a5a6a7第2页二个数组里，第二个数组作为乱序序列的保存数组，每次对第一个数组进行排序，之后拷贝第二个数组中的乱序序列到第一个数组，实现各次乱序排列。只要算法正确（第一步可以检验），之后顺序排列只需反复对第一个数组进行操作即可，再后用第二个数组保存逆序数组，然后同样在每次排序之后复制第二数组存储的乱序序列到第一组，对第一组反复排序即可。1pRandom1=newlongint[Max+1];pRandom2=newlongint[Max+1];2srand((unsigned)time(NULL));for(inti=1;i=Max;i++)pRandom2[i]=rand();3memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(longint));（2）排序算法：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希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。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;j0&&parray[0]parray[j];j-=d){parray[j+d]=parray[j];movetimes[1]++;}parray[j+d]=parray[0];movetimes[1]+=2;}}return0;}3冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。intSort::BubbleSort(longintparray[])第3页{intexchange=Max;intbound,j;while(exchange){bound=exchange;exchange=0;for(j=1;jbound;j++){comparetimes[2]++;if(parray[j]parray[j+1]){parray[0]=parray[j];parray[j]=parray[j+1];parray[j+1]=parray[0];exchange=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[],intfirst=1,intend=Max){if(firstend){intpivot=QuickSortPatition(parray,first,end);QuickSortRecursion(parray,first,pivot-1);//左侧子序列排序QuickSortRecursion(parray,pivot+1,end);//右侧子序列排序}return0;}intSort::QuickSortPatition(longintr[],intfirst,intend){inti=first;intj=end;inttemp;while(ij){while(ij&&r[i]=r[j]){j--;comparetimes[3]++;}//右侧扫描if(ij){temp=r[i];//将较小记录交换到前面r[i]=r[j];r[j]=temp;i++;movetimes[3]+=3;}第4页while(ij&&r[i]=r[j]){i++;comparetimes[3]++;}//左侧扫描if(ij){temp=r[j];r[j]=r[i];r[i]=temp;//将较大记录交换到后面j--;movetimes[3]+=3;}}returni;//i为轴值记录的最终位置示意图：r1,r2,r3,…,ri-1,ri,ri+1,…,rnrri轴值rri5选择排序：从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。intSort::SelectSort(longintparray[]){inti,j,index,temp;for(i=1;iMax;i++)//对n个记录进行n-1趟简单选择排序{index=i;for(j=i+1;j=Max;j++){comparetimes[4]++;//在无序区中选取最小记录if(parray[j]parray[index])index=j;}if(index!=i){temp=parray[i];parray[i]=parray[index];parray[index]=temp;movetimes[4]+=3;}}第5页示意图：r1,r2,r3,…,ri-1,ri,ri+1,…,rn反序则交换有序区6堆排序：通过建立大根堆或者小根堆，取出根节点，反复调整堆使之保持大根堆或者小根堆，直至最后序列有序。intSort::HeapSort(longintparray[]){inti;for(i=Max/2;i=1;i--)HeapSortSift(parray,i,Max);for(i=1;iMax;i++){parray[0]=parray[Max-i+1];parray[Max-i+1]=parray[1];parray[1]=parray[0];movetimes[5]+=3;HeapSortSift(parray,1,Max-i);}return0;}voidSort::HeapSortSift(longintparray[],intk,intm){inti,j;i=k;j=2*i;//置i为要筛的结点，j为i的左孩子while(j=m)//筛选还没有进行到叶子{if(jm&&parray[j]parray[j+1]){j++;comparetimes[5]++;}//比较i的左右孩子，j为较大者if(parray[i]parray[j]){comparetimes[5]++;break;}//根结点已经大于左右孩子中的较大者else第6页{parray[0]=parray[i];parray[i]=parray[j];parray[j]=parray[0];movetimes[5]+=3;i=j;j=2*i;//被筛结点位于原来结点j的位置7归并排序：将若干个有序序列两两归并，直至所有待排序的记录都在一个有序序列为止。intSort::MergeSort(longintparray[]){longintr1[Max+1];inth(1);while(hMax){MergePass(parray,r1,h);//归并h=2*h;MergePass(r1,parray,h);h=2*h;}return0;}voidSort::Merge(longintparray[],longintr1[],ints,intm,intt)//一次归并{inti=s;intj=m+1;intk=s;while(i=m&&j=t){comparetimes[6]++;movetimes[6]++;if(parray[i]=parray[j]){r1[k++]=parray[i++];}elser1[k++]=parray[j++];}if(i=m)第7页while(i=m){r1[k++]=parray[i++];movetimes[6]++;}elsewhile(j=t){r1[k++]=parray[j++];movetimes[6]++;}}voidSort::MergePass(longintparray[],longintr1[],inth)//一趟归并{inti(1),k;while(i=Max-2*h+1){Merge(parray,r1,i,i+h-1,i+2*h-1);i+=2*h;}if(iMax-h+1)Merge(parray,r1,i,i+h-1,Max);elsefor(k=i;k=Max;k++){r1[k]=parray[k];movetimes[6]++;（3）比较上述排序算法中关键字的比较次数和移动次数：使用函数指针数组，分别指向各排序函数的入口地址，然后在Statistics()函数中加以调用，使得排序函数运行在统计时间函数之间，这样使用一个for语句即可实现算法的一次性调用、时间统计、移动次数和比较次数统计。voidStatistics(Sort&obj,inti,intj){obj.startTime=obj.GetNowTime();(obj.*pFunction[i])(obj.pRandom1);obj.endTime=obj.GetNowTime();obj.runtime[i][j]=obj.endTime-obj.startTime;}建立两个数组分别统计运行次数，再统一使用一个数组记录七种算法在三种不同数据情况下的移动次数和交换次数。在分别运行乱序、顺序和逆序数组排序时取出前两个数组的值写入第三个数组，然后置零继续统计。(4)算法的执行时间：第8页获取当前系统时间，精确到微秒，分别在代码运行前后调用记录前后时间，再相减即可得到代码运行时间。此处调用函数QueryPerformanceCounter()用于得到高精度计时器的值。longdoubleSort::GetNowT33ime(){LARGE_INTEGERlitmp;LONG64QPart;QueryPerformanceCounter(&litmp);QPart=litmp.QuadPart;return(longdouble)QPart;（5）各种算法的时间复杂度与空间复杂度：3.程