8/9算法分析實(shí)驗(yàn)報(bào)告減治法-堆排序?qū)W生：專業(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)過程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)典問題的減治思想。三、實(shí)驗(yàn)要求1.[問題描述]：應(yīng)用堆排序方法對(duì)一個(gè)記錄序列進(jìn)行升序排列。2.[算法]：減治法：減治法是把一個(gè)大問題劃分為若干個(gè)子問題，但是這些子問題不需要分別求解，只需求解其中的一個(gè)子問題，因而也無(wú)需對(duì)子問題的解進(jìn)行合并。減治法將原問題分解為若干個(gè)子問題，并且原問題（規(guī)模為n）的解與子問題（規(guī)模通常是n/2或n-1）的解之間存在某種確定的關(guān)系，這種關(guān)系通常表現(xiàn)為：（1）原問題的解只存在于其中一個(gè)較小規(guī)模的子問題中；

（2）原問題的解與其中一個(gè)較小規(guī)模的解之間存在某種對(duì)應(yīng)關(guān)系。

由于原問題的解與較小規(guī)模的子問題的解之間存在這種關(guān)系，所以，只需求解其中一個(gè)較小規(guī)模的子問題就可以得到原問題的解。減治法只對(duì)一個(gè)子問題求解，并且不需要進(jìn)行解的合并。應(yīng)用減治法（例如減半法）得到的算法通常具有如下遞推式：T(n)={0；n=1T(n/2)+1；n>1}分治法需要對(duì)分解的子問題分別求解，再對(duì)子問題的解進(jìn)行合并，而減治法只對(duì)一個(gè)子問題進(jìn)行求解，并且不需要進(jìn)行解的合并。所以，通常來說，應(yīng)用減治法處理問題的效率是很高的，一般是O(logn)數(shù)量級(jí)。四、實(shí)現(xiàn)過程1、實(shí)驗(yàn)設(shè)計(jì)：1.堆排序是利用堆得特性進(jìn)行排序的方法，其基本思想是：首先將待排列的記錄序列構(gòu)造成一個(gè)堆，此時(shí)，堆頂記錄是堆中所有記錄的最大者，將它從堆中移走，然后將剩余記錄再調(diào)整成堆，這樣又找出了次大記錄，依次類推，直到堆中只有一個(gè)記錄為止。2.圖解過程4747353526262018720187131310104735262018713107101318352647207101318352647207101318352647203.算法實(shí)現(xiàn)void

SiftHeap(int

r[],int

k,int

n)

{

int

i,j,temp;

i=k;j=2*i+1;

while(j<n)

{

if(j<n-1&&r[j]<r[j+1])

j++;

if(r[i]>r[j])

break;

else

{

temp=r[i];

r[i]=r[j];

r[j]=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=r[0];r[0]=r[n-i];r[n-i]=temp;

SiftHeap(r,0,n-i);

}

}2、調(diào)試分析：算法Sift將根結(jié)點(diǎn)與左右子樹的根結(jié)點(diǎn)進(jìn)行比較，若不滿足堆的條件，則將根結(jié)點(diǎn)與左右子樹根結(jié)點(diǎn)的較大者進(jìn)行交換，所以，每比較一次，需要調(diào)整的完全二叉樹的問題規(guī)模就減少一半，因此，其時(shí)間性能是O（㏒?n）。3、運(yùn)行結(jié)果：4、實(shí)驗(yàn)總結(jié)：通過本次實(shí)驗(yàn)加深了我對(duì)減治法的理解，同時(shí)對(duì)用、減治法解決一個(gè)實(shí)際問題有了一個(gè)更深層次的認(rèn)識(shí)。通過本次實(shí)驗(yàn)使我掌握了減治法遞歸的一般模式，以后在解決一類問題時(shí)可以照著這個(gè)模式編寫程序。通過本次試驗(yàn)，自