算法分析与设计实验报告-合并排序、快速排序(共3页).doc

《算法分析与设计实验报告-合并排序、快速排序(共3页).doc》由会员分享，可在线阅读，更多相关《算法分析与设计实验报告-合并排序、快速排序(共3页).doc（3页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上实验报告课程计算机算法设计与分析实验名称合并排序、快速排序学号姓名实验日期：实验一 合并排序、快速排序一实验目的（1） 学习合并排序和快速排序算法的思想，掌握原理。（2） 运用合并排序和快速排序算法的思想进行编程实现，以加深理解。二实验内容（1）输入几个整数，运用合并排序的思想进行编程实现，输出正确的排序结果。（2）输入10个整数，运用快速排序的思想进行编程实现，输出正确的排序结果三实验代码(1)合并排序源代码如下：#include /调用setw #include /将b0至bright-left+1拷贝到aleft至aright template void Cop

2、y(T a,T b,int left,int right) int size=right-left+1; for(int i=0;isize;i+) aleft+=bi; /合并有序数组aleft:i,ai+1:right到b,得到新的有序数组b template void Merge(T a,T b,int left,int i,int right) int a1cout=left,/指向第一个数组开头 a1end=i,/指向第一个数组结尾 a2cout=i+1,/指向第二个数组开头 a2end=right,/指向第二个数组结尾 bcout=0;/指向b中的元素 for(int j=0;ja

3、1end) bbcout+=aa2cout+; continue; /如果第一个数组结束，拷贝第二个数组的元素到b if(a2couta2end) bbcout+=aa1cout+; continue; /如果第二个数组结束，拷贝第一个数组的元素到b if(aa1coutaa2cout) bbcout+=aa1cout+; continue; /如果两个数组都没结束，比较元素大小，把较小的放入b else bbcout+=aa2cout+; continue; /对数组aleft:right进行合并排序 template void MergeSort(T a,int left,int righ

4、t) T *b=new intright-left+1; if(leftright) int i=(left+right)/2;/取中点 MergeSort(a,left,i);/左半边进行合并排序 MergeSort(a,i+1,right);/右半边进行合并排序 Merge(a,b,left,i,right);/左右合并到b中 Copy(a,b,left,right);/从b拷贝回来 int main() int n; coutn; int *a=new intn; cout请输入相应的数字：; for(int i=0;iai; MergeSort( a, 0, n-1); cout排序结

5、果:; for(int j=0;jn;j+) coutsetw(5)aj; coutendl; return 1; （2）快速排序源代码如下：#include #define MAX 10int QuickSort(int a,int l,int r)int pivot;/枢轴int i=l;int j=r;int tmp;pivot=a(l+r)/2;/取数组中间的数为枢轴do while (aipivot) j-; / j左移if (i=j)tmp=ai; ai=aj; aj=tmp;/交换ai和aji+;j-; while(i=j);if (lj) QuickSort(a,l,j);if (ir) QuickSort(a,i,r);return 1;int main()int arrayMAX;int i;cout请输入MAX 个整数:;for (i=0;iarrayi;QuickSort(array,0,MAX-1);cout快速排序后：endl;for (i=0;iMAX;i+)coutarrayi ;coutendl;return 0;四实验结果五总结与思考专心-专注-专业