減治法解決堆排序

1、算法分析實(shí)驗(yàn)報(bào)告減治法-堆排序?qū)W生姓名：專(zhuān) 業(yè)： 班 級(jí)： 學(xué) 號(hào):指導(dǎo)教師： 2017年6月12日目錄一、實(shí)驗(yàn)題目2二、實(shí)驗(yàn)?zāi)康?三、實(shí)驗(yàn)要求2四、實(shí)現(xiàn)過(guò)程31、實(shí)驗(yàn)設(shè)計(jì)：32、調(diào)試分析：73、運(yùn)行結(jié)果：84、實(shí)驗(yàn)總結(jié)：8五、參考文獻(xiàn)9一、實(shí)驗(yàn)題目減治法-堆排序二、實(shí)驗(yàn)?zāi)康?、了解和掌握減治法的設(shè)計(jì)思想。2、了解各種經(jīng)典問(wèn)題的減治思想。三、實(shí)驗(yàn)要求1.問(wèn)題描述：應(yīng)用堆排序方法對(duì)一個(gè)記錄序列進(jìn)行升序排列。2.算法：減治法： 減治法是把一個(gè)大問(wèn)題劃分為若干個(gè)子問(wèn)題，但是這些子問(wèn)題不需要分別求解，只需求解其中的一個(gè)子問(wèn)題，因而也無(wú)需對(duì)子問(wèn)題的解進(jìn)行合并。 減治法將原問(wèn)題分解為若干個(gè)子問(wèn)題，并且原問(wèn)

2、題（規(guī)模為n）的解與子問(wèn)題（規(guī)模通常是n/2或n-1）的解之間存在某種確定的關(guān)系，這種關(guān)系通常表現(xiàn)為：（1）原問(wèn)題的解只存在于其中一個(gè)較小規(guī)模的子問(wèn)題中；（2）原問(wèn)題的解與其中一個(gè)較小規(guī)模的解之間存在某種對(duì)應(yīng)關(guān)系。 由于原問(wèn)題的解與較小規(guī)模的子問(wèn)題的解之間存在這種關(guān)系，所以，只需求解其中一個(gè)較小規(guī)模的子問(wèn)題就可以得到原問(wèn)題的解。減治法只對(duì)一個(gè)子問(wèn)題求解，并且不需要進(jìn)行解的合并。應(yīng)用減治法（例如減半法）得到的算法通常具有如下遞推式：T(n)=0；n=1 T(n/2)+1 ；n>1分治法需要對(duì)分解的子問(wèn)題分別求解，再對(duì)子問(wèn)題的解進(jìn)行合并，而減治法只對(duì)一個(gè)子問(wèn)題進(jìn)行求解，并且不需要進(jìn)行解的合并

3、。所以，通常來(lái)說(shuō)，應(yīng)用減治法處理問(wèn)題的效率是很高的，一般是O(logn)數(shù)量級(jí)。四、實(shí)現(xiàn)過(guò)程1、實(shí)驗(yàn)設(shè)計(jì)：1. 堆排序是利用堆得特性進(jìn)行排序的方法，其基本思想是：首先將待排列的記錄序列構(gòu)造成一個(gè)堆，此時(shí)，堆頂記錄是堆中所有記錄的最大者，將它從堆中移走，然后將剩余記錄再調(diào)整成堆，這樣又找出了次大記錄，依次類(lèi)推，直到堆中只有一個(gè)記錄為止。2.圖解過(guò)程4735262018713104735262018713107101318352647207101318352647203.算法實(shí)現(xiàn)void SiftHeap(int r,int k,int n) int

4、0;i,j,temp; i=k;j=2*i+1; while(j<n)if(j<n-1&&rj<rj+1) j+;if(ri>rj) break;else temp=ri; ri=rj; rj=temp; i=j;j=2*i+1;void HeapSort(int r,int n) int i,temp; for(i=(n-1)/2;i>=0;i-) SiftHeap(r,i,n); for(i=1;i<=n-1;i+) temp=r0;r0=rn-i;rn-i=temp; SiftHeap(r,0,n-i); 2、調(diào)試分析：算法Sift將根結(jié)點(diǎn)與左右子樹(shù)的根結(jié)點(diǎn)進(jìn)行比較，若不滿足堆的條件，則將根結(jié)點(diǎn)與左右子樹(shù)根結(jié)點(diǎn)的較大者進(jìn)行交換，所以，每比較一次，需要調(diào)整的完全二叉樹(shù)的問(wèn)題規(guī)模就減少一半，因此，其時(shí)間性能是O（n）。3、運(yùn)行結(jié)果：4、實(shí)驗(yàn)總結(jié)： 通過(guò)本次實(shí)驗(yàn)加深了我對(duì)減治法的理解，同時(shí)對(duì)用、減治法解決一個(gè)實(shí)際問(wèn)題有了一個(gè)更深層次的認(rèn)識(shí)。通過(guò)本次實(shí)驗(yàn)使我掌握了減治法遞歸的一般模式，以后在解決一類(lèi)問(wèn)題時(shí)可以照著這個(gè)模式編寫(xiě)程序。通過(guò)本次試驗(yàn)，自己基本上掌握上述算法原理，達(dá)到實(shí)驗(yàn)的目的。五、參考文獻(xiàn)1