減治法解決堆排序

算法分析實(shí)驗(yàn)報(bào)告減治法一堆排序?qū)W生姓名:專業(yè):班級(jí):學(xué)號(hào):指導(dǎo)教師:2017年6月12日目錄TOC\o"1-5"\h\z\o"CurrentDocument"一、實(shí)驗(yàn)題目 2\o"CurrentDocument"二、實(shí)驗(yàn)?zāi)康?2\o"CurrentDocument"三、實(shí)驗(yàn)要求 2\o"CurrentDocument"四、實(shí)現(xiàn)過程 3\o"CurrentDocument"1、實(shí)驗(yàn)設(shè)計(jì)： 3\o"CurrentDocument"2、調(diào)試分析： 63、運(yùn)行結(jié)果：..…錯(cuò)誤！未定義書簽。\o"CurrentDocument"4、實(shí)驗(yàn)總結(jié)： 7\o"CurrentDocument"五、參考文獻(xiàn) 7一、實(shí)驗(yàn)題目減治法一堆排序二、實(shí)驗(yàn)?zāi)康?、了解和掌握減治法的設(shè)計(jì)思想。2、了解各種經(jīng)典問題的減治思想。三、實(shí)驗(yàn)要求.［問題描述］:應(yīng)用堆排序方法對(duì)一個(gè)記錄序列進(jìn)行升序排列。.［算法］：減治法：減治法是把一個(gè)大問題劃分為若干個(gè)子問題，但是這些子問題不需要分別求解，只需求解其中的一個(gè)子問題，因而也無需對(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=1 T(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ì)：.堆排序是利用堆得特性進(jìn)行排序的方法，其基本思想是：首先將待排列的記錄序列構(gòu)造成一個(gè)堆，此時(shí)，堆頂記錄是堆中所有記錄的最大者，將它從堆中移走，然后將剩余記錄再調(diào)整成堆，這樣又找出了次大記錄，依次類推，直到堆中只有一個(gè)記錄為止。

.圖解過程4735262018713107101318352647204.算法實(shí)現(xiàn)voidSiftHeap(intr[],intk,intn)(inti,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;)))voidHeapSort(intr[],intn)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(logn)。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)，自己基本上掌握上述算法原理，達(dá)