算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告-合并排序、快速排序(共3頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí)驗(yàn)報(bào)告課程計(jì)算機(jī)算法設(shè)計(jì)與分析實(shí)驗(yàn)名稱合并排序、快速排序?qū)W號(hào)姓名實(shí)驗(yàn)日期：實(shí)驗(yàn)一 合并排序、快速排序一實(shí)驗(yàn)?zāi)康模?） 學(xué)習(xí)合并排序和快速排序算法的思想，掌握原理。（2） 運(yùn)用合并排序和快速排序算法的思想進(jìn)行編程實(shí)現(xiàn)，以加深理解。二實(shí)驗(yàn)內(nèi)容（1）輸入幾個(gè)整數(shù)，運(yùn)用合并排序的思想進(jìn)行編程實(shí)現(xiàn)，輸出正確的排序結(jié)果。（2）輸入10個(gè)整數(shù)，運(yùn)用快速排序的思想進(jìn)行編程實(shí)現(xiàn)，輸出正確的排序結(jié)果三實(shí)驗(yàn)代碼(1)合并排序源代碼如下：#include <iomanip.h>/調(diào)用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; /合并有序數(shù)組aleft:i,ai+1:right到b,得到新的有序數(shù)組b template <class T> void Merge(T a,T b,int left,int i,int right) int a1cout=left,/指向第一個(gè)數(shù)組開頭 a1end=i,/指向第一個(gè)數(shù)組結(jié)尾 a2co

3、ut=i+1,/指向第二個(gè)數(shù)組開頭 a2end=right,/指向第二個(gè)數(shù)組結(jié)尾 bcout=0;/指向b中的元素 for(int j=0;j<right-left+1;j+)/執(zhí)行right-left+1次循環(huán) if(a1cout>a1end) bbcout+=aa2cout+; continue; /如果第一個(gè)數(shù)組結(jié)束，拷貝第二個(gè)數(shù)組的元素到b if(a2cout>a2end) bbcout+=aa1cout+; continue; /如果第二個(gè)數(shù)組結(jié)束，拷貝第一個(gè)數(shù)組的元素到b if(aa1cout<aa2cout) bbcout+=aa1cout+; conti

4、nue; /如果兩個(gè)數(shù)組都沒結(jié)束，比較元素大小，把較小的放入b else bbcout+=aa2cout+; continue; /對(duì)數(shù)組aleft:right進(jìn)行合并排序 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;/取中點(diǎn) MergeSort(a,left,i);/左半邊進(jìn)行合并排序 MergeSort(a,i+1,right);/右半邊進(jìn)行合并排序 Merge(a,b,left

5、,i,right);/左右合并到b中 Copy(a,b,left,right);/從b拷貝回來(lái) int main() int n; cout<<"請(qǐng)輸入您將要排序的數(shù)目:" cin>>n; int *a=new intn; cout<<"請(qǐng)輸入相應(yīng)的數(shù)字：" for(int i=0;i<n;i+) cin>>ai; MergeSort( a, 0, n-1); cout<<"排序結(jié)果:" 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;/取數(shù)組中間的數(shù)為樞軸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<<"請(qǐng)輸入"<<MAX<<" 個(gè)整數(shù):"for (i=0;i<MAX;i+)cin>>arrayi;QuickSort(array,0,MAX-1);cout<<"快速排序后："<<e