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

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

2、t+1拷贝到aleft至aright template <class T> void Copy(T a,T b,int left,int right) int size=right-left+1; for(int i=0;i<size;i+) aleft+=bi; /合并有序数组aleft:i,ai+1:right到b,得到新的有序数组b template <class T> void Merge(T a,T b,int left,int i,int right) int a1cout=left,/指向第一个数组开头 a1end=i,/指向第一个数组结尾 a2co

3、ut=i+1,/指向第二个数组开头 a2end=right,/指向第二个数组结尾 bcout=0;/指向b中的元素 for(int j=0;j<right-left+1;j+)/执行right-left+1次循环 if(a1cout>a1end) bbcout+=aa2cout+; continue; /如果第一个数组结束，拷贝第二个数组的元素到b if(a2cout>a2end) bbcout+=aa1cout+; continue; /如果第二个数组结束，拷贝第一个数组的元素到b if(aa1cout<aa2cout) bbcout+=aa1cout+; conti

4、nue; /如果两个数组都没结束，比较元素大小，把较小的放入b else bbcout+=aa2cout+; continue; /对数组aleft:right进行合并排序 template <class T> void MergeSort(T a,int left,int right) T *b=new intright-left+1; if(left<right) int i=(left+right)/2;/取中点 MergeSort(a,left,i);/左半边进行合并排序 MergeSort(a,i+1,right);/右半边进行合并排序 Merge(a,b,left

5、,i,right);/左右合并到b中 Copy(a,b,left,right);/从b拷贝回来 int main() int n; cout<<"请输入您将要排序的数目:" cin>>n; int *a=new intn; cout<<"请输入相应的数字：" for(int i=0;i<n;i+) cin>>ai; MergeSort( a, 0, n-1); cout<<"排序结果:" for(int j=0;j<n;j+) cout<<setw(5

6、)<<aj; cout<<endl; return 1; （2）快速排序源代码如下：#include <iostream.h>#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 (ai<pivot) i+; /i右移while (aj>pivot) j-; / j左移if (i<=j)tmp=ai; ai=aj; aj=tmp;/交换ai和aji+;j-; while(i<=j);if (l<j) QuickSort(a,l,j);if (i<r) QuickSort(a,i,r);return 1;int main()int arrayMAX;int i;cout<<"请输入"<<MAX<<" 个整数:"for (i=0;i<MAX;i+)cin>>arrayi;QuickSort(array,0,MAX-1);cout<<"快速排序后："<<e