歸并排序?qū)嶒?yàn)報(bào)告

1、int i=s; int j=m+1; if(i<=m)while(i<=m) if(ri<=rj)r1k+=ri+;/r1k+=rj+; else while(j<=t) r1k+=rj+;/ for(int l=0;l<k;l+) rl=r1l;/if(s=t)r1s=rs;elseint m; m=(s+t)/2;第二個(gè)沒(méi)處理完，進(jìn)行收尾將合并完成后的 r1 序列送回 r 中 mergesort(r,r1,s,m);/ 歸并排序前半個(gè)子篇一：歸并排序與快速排序?qū)嶒?yàn)報(bào)告一、實(shí)驗(yàn)內(nèi)容： 對(duì)二路歸并排序和快速排序?qū)τ谀嫘虻捻?/p>

2、序數(shù)的排序時(shí)間復(fù)雜度比較。二、所用算法的基本思想及復(fù)雜度分析：1、歸并排序1) 基本思想：運(yùn)用分治法，其分治策略為： 劃分：將待排序列r1,r2, ” ,rn劃分為兩個(gè)長(zhǎng)度相等的子序列r1, ,rn/2 和 rn/2+1, , ,rn 。 求解子問(wèn)題：分別對(duì)這兩個(gè)子序列進(jìn)行排序，得到兩個(gè)有序子序列。 合并：將這兩個(gè)有序子序列合并成一個(gè)有序子序列。2) 復(fù)雜度分析：二路歸并排序的時(shí)間代價(jià)是 o(nlog2n) 。二路歸并排序在合并過(guò)程中需要與原始記錄序列同 樣數(shù)量的存儲(chǔ)空間，因此其空間復(fù)雜性 o(n) 。2、快速排序：1 ) 基本思想：運(yùn)用分治法，其分治策略為： 劃分：選定一個(gè)記錄作為軸值，以軸

3、值為基準(zhǔn)將整個(gè)序列劃分為兩個(gè)子序列r1 , ri-1和ri+1 , rn，軸值的位置i在劃分的過(guò)程中確定，并且前一個(gè)子序列中記錄的值均小于或等于軸值，后一個(gè)子序列中記錄的值均大于或等于軸值。 求解子問(wèn)題：分別對(duì)劃分后的每一個(gè)子序列遞歸處理。 合并：由于對(duì)子序列r1 , ri-1和ri+1 , rn的排序是就地進(jìn)行的，所以合并不需要執(zhí)行任何操作。2) 復(fù)雜度分析：快速排序在平均時(shí)間復(fù)雜性是o(nlog2n)。最壞的情況下是 o(nA2)。三、源程序及注釋：1 、 歸并排序#include<iostream>#include<fstream>

4、#include windows.h using namespace std;void merge(int r,int r1,int s,int m,int t )int mergesort(int r,int r1,int s,int t)void main()int k=s; while(i<=m&&j<=t)r1k+=ri+;/ 第 一 個(gè) 沒(méi) 處 理 完 ， 進(jìn) 行 收 尾 取 ri 和 rj 中 較 小 的 放 入 r1k 中 else序列 mergesort(r,r1,m+1,t); /歸并排序后半個(gè)子序列 merge(r

5、1,r,s,m,t);/ 合并兩個(gè)已排序的子序列 return 0;int a100000; int a110000;int n,i;產(chǎn)生 3 個(gè)數(shù)組。int b3= 1000,3000,5000;/ for(int j=0; j<3; j+)n=bj;for(i=1; i<=n; i+) ai=n;large_integer begaintime ;large_integer endtime ;large_integer frequency;queryperformancefrequency(&frequency);queryperformance

6、counter(&amp ;begaintime) ;int c=mergesort(a,a1,0,n-1); queryperformancecounter(&endtime); cout << 數(shù) 據(jù) 個(gè) 數(shù) 為 <<n<<時(shí) 歸 并 排 序 的 時(shí) 間 為 ( 單 位 ： s )：<<(double)( endtime1.quadpart - begaintime1.quadpart )/ frequency1.quadpart <&

7、;lt;endl;2、快速排序#include<iostream> #include<fstream>#include windows.husing namespace std;int partition (int data,int first,int end)int i,j; while(i<j) return i; while(i<j&&datai<=dataj)j-;/從左側(cè)掃描 if(i<j) while(i<j&

8、&datai<=dataj)i+;/ 從右側(cè)掃描 if(i<j) int temp1; temp1=datai; datai=dataj; dataj=temp1; /將較小的放到后面 j-; int temp; temp=datai; datai=dataj; dataj=temp;/將較小的放到前面 i+;int quicksort(int c,int first,int end)int i; if(first<end) i=partition(c,first,end);/對(duì) chs 到 cht 進(jìn)行一次劃分 quicksort(c

9、,i+1,end);/ 遞歸處理右區(qū)間 return 0;void main()int a100000,n,i;int b3= 1000,3000,5000;/3 個(gè)數(shù)據(jù)范圍for(int j=0; j<3; j+)n=bj;for(i=1; i<=n; i+) ai=n;large_integer begaintime ;large_integer endtime;large_integer frequency ;queryperformancefrequency(&frequency);queryperformancecounter(&a

10、mp;begaintime) ;int c= quicksort(a,0,n);queryperformancecounter(&endtime);cout << 數(shù) 據(jù) 個(gè) 數(shù) 為 <<n<<時(shí) 快 速 排 序 的 時(shí) 間 為 ( 單 位 ： s )：<<(double)( endtime.quadpart - begaintime.quadpart )/ frequency.quadpart <<endl;四、運(yùn)行輸出結(jié)果： 歸并排序篇

11、二：算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告 - 合并排序、快速排序 實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)一合并排序、快速排序一實(shí)驗(yàn)?zāi)康? 1) 學(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 至 br

12、ight-left+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,

13、/ 指向第一個(gè)數(shù)組開(kāi)頭 a1end=i,/ 指向第一個(gè)數(shù)組結(jié)尾 a2cout=i+1,/ 指向第二個(gè)數(shù)組開(kāi)頭 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ù) 組

14、 結(jié) 束 ， 拷 貝 第 一 個(gè) 數(shù) 組 的 元 素 到 b if(aa1cout<aa2cout) bbcout+=aa1cout+;continue; / 如果兩個(gè)數(shù)組都沒(méi)結(jié)束，比較元素大小，把較小的放入 belse 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+ri

15、ght)/2;/ 取中點(diǎn)mergesort(a,left,i);/ 左半邊進(jìn)行合并排序 mergesort(a,i+1,right);/ 右半邊進(jìn)行合并 排序 merge(a,b,left,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

16、>>ai; mergesort( a, 0, n-1); cout<< 排序結(jié)果 :; for(int j=0;j<n;j+) cout<<setw(5)<<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

17、 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 和 aj i+;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&

18、lt;< 請(qǐng)輸入 <<max<< 個(gè)整數(shù) :; for (i=0;i<max;i+) cin>>arrayi;quicksort(array,0,max-1); cout<< 快 速 排 序 后 ： <<endl; for (i=0;i<max;i+)cout<<arrayi<< ; cout<<endl;return 0; 四實(shí)驗(yàn)

19、結(jié)果五總結(jié)與思考篇三：合并、快速排序?qū)嶒?yàn)報(bào)告 合并、快速排序 一實(shí)驗(yàn)?zāi)康模?. 理解算法設(shè)計(jì)的基本步驟及各部的主要內(nèi)容、基本要求；2. 加深對(duì)分治設(shè)計(jì)方法基本思想的理解， 并利用其解決現(xiàn)實(shí)生活中的問(wèn)題； 3. 通過(guò)本次試 驗(yàn)初步掌握將算法轉(zhuǎn)化為計(jì)算機(jī)上機(jī)程序的方法。 二實(shí)驗(yàn)內(nèi)容：1. 設(shè)計(jì)和實(shí)現(xiàn)遞歸的合并排序算法、 快速排序算法； 2. 設(shè)計(jì)和實(shí)現(xiàn)消除遞歸的合并排序算 法、快速排序算法；3. 設(shè)計(jì)有代表性的典型輸入數(shù)據(jù)，分析算法的效率；4. 對(duì)于給定的輸入數(shù)據(jù)， 給出算運(yùn)行結(jié)果和運(yùn)行結(jié)果， 并給出實(shí)驗(yàn)結(jié)果分。 三實(shí)驗(yàn)操作：1. 合并排序思想： 歸并排序是建立在歸并操作上的一種有效的排序算法。該

20、算法是采用分治法的思想，是一種 穩(wěn)定的排序方法。將以有序的子序列合并，得到完全有序的序列；及先使每個(gè)字序列有序， 再使子序列段間有序。歸并過(guò)程：比較數(shù)組中兩個(gè)元素的大小，如比較 ai 和 aj 的大小，若 ai<=aj ， 將第一個(gè)有序表中的元素 ai 復(fù)制到 rk 中，并令 i 和 k 分別加上 1，如此循環(huán)下去，直到 其中一個(gè)有序表取完，然后再將另一個(gè)有序表剩下的元素復(fù)制到 r 中從下標(biāo) k 到下標(biāo) t 的單 元。如： 6 ， 202，100， 301， 38， 8，1第一次歸并： 6 ，202 ，100 ，301 ，8 ，38 ，1 第二次歸并： 6 ，100，202，30

21、1 ，1， 8，38 第三次歸并： 1 ，6，8，38，100，202，301 合并排序算法： void merge(int array,int low,int high)int i=low,j,k;int mid=(low+high)/2; j=mid+1; k=low;int* list=new inthigh+1; while(i<=mid&&j<=high) if(arrayi<=arrayj) listk+=arrayi+;else listk+=arrayj+; while(i<=mid) li

22、stk+=arrayi+; while(j<=high) listk+=arrayj+; for(int n=low;n<=high;n+)arrayn=listn;void mergesort(int array,int low,int high)if(low<high)int mid=(low+high)/2;mergesort(array,low,mid);mergesort(array,mid+1,high); merge(array,low,high); 2. 快速排序思想：將要排序的數(shù)據(jù)存入數(shù)組中，首先任意去一個(gè)元素（通常選用數(shù)組的第一個(gè)數(shù)

23、）作為關(guān)鍵數(shù) 據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，值得注意的是， 快速排序不是一種穩(wěn)定的排序算法，即多個(gè)相同的值的相對(duì)位置也許會(huì)在算法結(jié)束時(shí)產(chǎn)生變 動(dòng)。快速排序的過(guò)程：1） 設(shè)置兩個(gè)變量 i,j ，排序開(kāi)始的時(shí)候： i=0,j=n-1 （ n 為元素個(gè)數(shù)） ； 2 ） 以第一個(gè)數(shù)組 元素作為關(guān)鍵數(shù)據(jù)，賦給key，即key=aO ; 3 ）從j開(kāi)始向前搜索，即由后開(kāi)始向前搜索（j- ），找到第一個(gè)小于 key的值 aj ，將 aj 和 ai 互換;4） 從 i 開(kāi)始向后搜索，即由前開(kāi)始向后搜索（ i+ ），找到第一個(gè)大于 key的 ai ，將 ai 和 aj 互換;

24、 5） 重復(fù)第 3、4 步，直到 i=j ; 如：快速排序的算法：void qsort(int list,intlow,int high) if(low>=high)return; int first=low; intlast=high;-last;+first;int key=listfirst; while(first<last) while(first<last&&listlast>=key) listfirst=listlast;while(first<last&&am

25、p;amp;listfirst<=key) listlast=listfirst; listfirst=key;qsort(list,low,first-1); qsort(list,last+1,high);3. 實(shí)驗(yàn)數(shù)據(jù)的輸入：Cin 流輸入來(lái)控制數(shù)據(jù)的輸入。本實(shí)驗(yàn)采用將數(shù)據(jù)輸入與輸出存儲(chǔ)到文件中的方式，需要采用C+文件流操作，對(duì)于數(shù)據(jù)的輸入，由于 cin 對(duì)數(shù)據(jù)的讀取會(huì)忽略空格和換行操作，使用 對(duì)于輸出操作，首先要從文件中讀取數(shù)據(jù)，為了區(qū)別各數(shù)據(jù)，用逗號(hào)隔離，經(jīng)過(guò)處理后將數(shù) 據(jù)存入到另一文件之中。由于輸入需要大量的數(shù)據(jù)，可采用從“隨機(jī)數(shù) .txt ”中讀取數(shù)據(jù)。 文件輸入算

26、法：int input()ofstream outfile;outfile.open(e:/ 程 序 設(shè) 計(jì) /praCtiCe 1/ 算 法 設(shè) 計(jì) 與 分 析 文 本 文 件 夾 /number2.txt,ios:trunC);if(!outfile.is_open() Cout<<file Cant open!<<endl;Cout<<input numbers:<<endl;Char num;int length=0;Cin.get(num);while(num!=e) length+; outfile<<num;Cin.get(num); outfile.Close(); return length;文件輸出算法：void output(int length) double start,end; ifstream infile; ofstream outfile;infile.open(e:/ 程序設(shè)計(jì) /practice 1/ 算法設(shè)計(jì)與分析 / 文本文件夾 /number2.txt);outfil