減治法解決堆排序

算法分析實驗報告減治法一堆排序?qū)W生姓名:專業(yè):班級:學號:指導教師:2017年6月12日目錄TOC\o"1-5"\h\z\o"CurrentDocument"一、實驗題目 2\o"CurrentDocument"二、實驗目的 2\o"CurrentDocument"三、實驗要求 2\o"CurrentDocument"四、實現(xiàn)過程 3\o"CurrentDocument"1、實驗設計： 3\o"CurrentDocument"2、調(diào)試分析： 63、運行結果：..…錯誤！未定義書簽。\o"CurrentDocument"4、實驗總結： 7\o"CurrentDocument"五、參考文獻 7一、實驗題目減治法一堆排序二、實驗目的1、了解和掌握減治法的設計思想。2、了解各種經(jīng)典問題的減治思想。三、實驗要求.［問題描述］:應用堆排序方法對一個記錄序列進行升序排列。.［算法］：減治法：減治法是把一個大問題劃分為若干個子問題，但是這些子問題不需要分別求解，只需求解其中的一個子問題，因而也無需對子問題的解進行合并。減治法將原問題分解為若干個子問題，并且原問題（規(guī)模為n）的解與子問題（規(guī)模通常是n/2或n-1）的解之間存在某種確定的關系，這種關系通常表現(xiàn)為：（1）原問題的解只存在于其中一個較小規(guī)模的子問題中；（2）原問題的解與其中一個較小規(guī)模的解之間存在某種對應關系。由于原問題的解與較小規(guī)模的子問題的解之間存在這種關系，所以，只需求解其中一個較小規(guī)模的子問題就可以得到原問題的解。減治法只對一個子問題求解，并且不需要進行解的合并。應用減治法(例如減半法)得到的算法通常具有如下遞推式：T(n)={0；n=1 T(n/2)+1；n>1)分治法需要對分解的子問題分別求解，再對子問題的解進行合并，而減治法只對一個子問題進行求解，并且不需要進行解的合并。所以，通常來說，應用減治法處理問題的效率是很高的，一般是O(logn)數(shù)量級。四、實現(xiàn)過程1、實驗設計：.堆排序是利用堆得特性進行排序的方法，其基本思想是：首先將待排列的記錄序列構造成一個堆，此時，堆頂記錄是堆中所有記錄的最大者，將它從堆中移走，然后將剩余記錄再調(diào)整成堆，這樣又找出了次大記錄，依次類推，直到堆中只有一個記錄為止。

.圖解過程4735262018713107101318352647204.算法實現(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將根結點與左右子樹的根結點進行比較，若不滿足堆的條件，則將根結點與左右子樹根結點的較大者進行交換，所以，每比較一次，需要調(diào)整的完全二叉樹的問題規(guī)模就減少一半，因此，其時間性能是O(logn)。3、運行結果:4、,實驗總結:通過本次實驗加深了我對減治法的理解，同時對用、減治法解決一個實際問題有了一個更深層次的認識。通過本次實驗使我掌握了減治法遞歸的一般模式，以后在解決一類問題時可以照著這個模式編寫程序。通過本次試驗，自己基本上掌握上述算法原理，達