快速排序和歸并排序

快速排序和歸并排序

ID:16317303

大小:45.50 KB

頁數(shù):4頁

時間:2018-08-09

快速排序和歸并排序_第1頁
快速排序和歸并排序_第2頁
快速排序和歸并排序_第3頁
快速排序和歸并排序_第4頁
資源描述:

《快速排序和歸并排序》由會員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、實驗三:快速排序和歸并排序的實現(xiàn)與效率比較一、實驗環(huán)境:windowsxpMatlabR2010b二、實驗內(nèi)容:對數(shù)組進(jìn)行升序排序,運(yùn)用快速排序和歸并排序的方法實現(xiàn)。三、問題分析:1.快速排序2.歸并排序四、算法描述:快速排序:是對冒泡排序的一種改進(jìn)通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小,然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序,整個排序過程可以遞歸進(jìn)行,以此達(dá)到整個數(shù)據(jù)變成有序序列。偽代碼:算法quick_sort輸入一串亂序的整數(shù)輸出一串遞增的整數(shù)1.以第一個數(shù)a為ref,如果while

2、(a(i)ref),4.j=j-1,向左掃描,找到第一個大于ref的值,執(zhí)行swap算法5.遞歸執(zhí)行,直到i=j;歸并排序:歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法的一個非常典型的應(yīng)用。申請空間,使其大小為兩個已經(jīng)排序序列之和,該空間用來存放合并后的序列設(shè)定兩個指針,最初位置分別為兩個已經(jīng)排序序列的起始位置比較兩個指針?biāo)赶虻脑兀x擇相

3、對小的元素放入到合并空間,并移動指針到下一位置重復(fù)步驟3直到某一指針達(dá)到序列尾將另一序列剩下的所有元素直接復(fù)制到合并序列尾。五、實驗結(jié)果分析:歸并排序,時間復(fù)雜度為O(nlogn)這是該算法中最好、最壞和平均的時間性能。賦值操作的次數(shù)是(2nlogn)。歸并算法的空間復(fù)雜度為:0(n)。歸并排序比較占用內(nèi)存,但卻效率高且穩(wěn)定的算法。快速排序算法是不穩(wěn)定的,最理想的情況下,算法時間復(fù)雜度為O(nlog2n),最壞為O(n2),在最壞情況下的時間消耗不如歸并排序。一、程序源代碼:快速排序算法:Part1function[b,q]=Partition(a,p

4、,r)i=p;j=r;ref=a(p);%基準(zhǔn)值while(1)while(a(i)=r)break;end;end;while(a(j)>ref)j=j-1;%向左掃描end;if(i>=j)break;end;a=swap(a,i,j);endb=a;q=j;disp(num2str(a));Part2functiona=quick_sort(a,p,r)if(p

5、%右半end調(diào)用函數(shù):Part3a=[45361853723048931535];quick_sort(a,1,length(a));運(yùn)行結(jié)果:35361815304548937253301518353645489372531815303536454893725315183035364548937253151830353645489372531518303536454853729315183035364548537293Elapsedtimeis0.257036seconds.歸并排序算法:Part1function[tt,A]=ms(A,p,r)%ê

6、μ??ò?′?1é2¢??Dòx=A(r);i=p-1;temp=0;forj=p:r-1ifA(j)<=x%é?????D?μ??a??·?μ?êy×éA(i)?Di=i+1;temp=A(i);A(i)=A(j);A(j)=temp;endendtemp=A(i+1);A(i+1)=A(r);A(r)=temp;tt=i+1;endPart2functionA=mysort(A,p,r)%êμ??1é2¢??Dòoˉêyifp

7、Part3tic;clear;clcA=[45361853723048931535];N=length(A);p=1;r=N;A=mysort(A,p,r)toc;運(yùn)行結(jié)果:A=15183035364548537293Elapsedtimeis0.009773seconds.

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動畫的文件,查看預(yù)覽時可能會顯示錯亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負(fù)責(zé)整理代發(fā)布。如果您對本文檔版權(quán)有爭議請及時聯(lián)系客服。
3. 下載前請仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時可能由于網(wǎng)絡(luò)波動等原因無法下載或下載錯誤,付費(fèi)完成后未能成功下載的用戶請聯(lián)系客服處理。