減治法解決堆排序

8/9算法分析實驗報告減治法-堆排序?qū)W生：專業(yè)：班級：學號:指導教師：2017年6月12日目錄一、實驗題目2二、實驗?zāi)康?三、實驗要求2四、實現(xiàn)過程31、實驗設(shè)計：32、調(diào)試分析：73、運行結(jié)果：84、實驗總結(jié)：8五、參考文獻9一、實驗題目減治法-堆排序二、實驗?zāi)康?、了解和掌握減治法的設(shè)計思想。2、了解各種經(jīng)典問題的減治思想。三、實驗要求1.[問題描述]：應(yīng)用堆排序方法對一個記錄序列進行升序排列。2.[算法]：減治法：減治法是把一個大問題劃分為若干個子問題，但是這些子問題不需要分別求解，只需求解其中的一個子問題，因而也無需對子問題的解進行合并。減治法將原問題分解為若干個子問題，并且原問題（規(guī)模為n）的解與子問題（規(guī)模通常是n/2或n-1）的解之間存在某種確定的關(guān)系，這種關(guān)系通常表現(xiàn)為：（1）原問題的解只存在于其中一個較小規(guī)模的子問題中；

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

由于原問題的解與較小規(guī)模的子問題的解之間存在這種關(guān)系，所以，只需求解其中一個較小規(guī)模的子問題就可以得到原問題的解。減治法只對一個子問題求解，并且不需要進行解的合并。應(yīng)用減治法（例如減半法）得到的算法通常具有如下遞推式：T(n)={0；n=1T(n/2)+1；n>1}分治法需要對分解的子問題分別求解，再對子問題的解進行合并，而減治法只對一個子問題進行求解，并且不需要進行解的合并。所以，通常來說，應(yīng)用減治法處理問題的效率是很高的，一般是O(logn)數(shù)量級。四、實現(xiàn)過程1、實驗設(shè)計：1.堆排序是利用堆得特性進行排序的方法，其基本思想是：首先將待排列的記錄序列構(gòu)造成一個堆，此時，堆頂記錄是堆中所有記錄的最大者，將它從堆中移走，然后將剩余記錄再調(diào)整成堆，這樣又找出了次大記錄，依次類推，直到堆中只有一個記錄為止。2.圖解過程4747353526262018720187131310104735262018713107101318352647207101318352647207101318352647203.算法實現(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é)點與左右子樹的根結(jié)點進行比較，若不滿足堆的條件，則將根結(jié)點與左右子樹根結(jié)點的較大者進行交換，所以，每比較一次，需要調(diào)整的完全二叉樹的問題規(guī)模就減少一半，因此，其時間性能是O（㏒?n）。3、運行結(jié)果：4、實驗總結(jié)：通過本次實驗加深了我對減治法的理解，同時對用、減治法解決一個實際問題有了一個更深層次的認識。通過本次實驗使我掌握了減治法遞歸的一般模式，以后在解決一類問題時可以照著這個模式編寫程序。通過本次試驗，自