基于分治法的快速排序

1、實驗2.基于分治法的快速排序算法實驗內(nèi)容本實驗要求基于算法設計與分析的一般過程（即待求解問題的描述、算法設計、算法描述、算法正確性證明、算法分析、算法實現(xiàn)與測試），針對快速排序算法從實踐中理解分治法的思想、求解策略及步驟。實驗目的理解分治法的核心思想以及分治法求解過程；從算法分析與設計的角度，對快速排序算法有更進一步的理解。環(huán)境要求對于環(huán)境沒有特別要求。對于算法實現(xiàn)，可以自由選擇C,C+,Java，甚至于其他程序設計語言。實驗步驟步驟1：理解問題，給出問題的描述。步驟2：算法設計，包括策略與數(shù)據(jù)結(jié)構(gòu)的選擇步驟3：描述算法。希望采用源代碼以外的形式，如偽代碼、流程圖等；步驟4：算法的正確性證明。

2、需要這個環(huán)節(jié)，在理解的基礎上對算法的正確性給予證明；步驟5：算法復雜性分析，包括時間復雜性和空間復雜性；步驟6：算法實現(xiàn)與測試。附上代碼或以附件的形式提交，同時貼上算法運行結(jié)果截圖步驟7：技術上、分析過程中等各種心得體會與備忘，需要言之有物。說明：步驟1-6在“實驗結(jié)果”一節(jié)中描述，步驟7在“實驗總結(jié)”一節(jié)中描述。實驗結(jié)果問題描述快速排序是一種劃分交換排序，其基本思想是：通過一趟掃描將待排序的元素分割成獨立的三個序列：第一個序列中所有元素均不大于基準元素、第二個序列是基準元素、第三個序列中所有元素均不小于基準元素。由于第二個序列已經(jīng)處于正確位置，因此需要再按此方法對第一個序列和第三個序列分別進

3、行排序，整個排序過程可以遞歸進行，最終可使整個序列變成有序序列。算法設計快速排序采用分治策略快速排序的基本思想是基于分治策略的，利用分治法可將快速排序的基本思想描述如下：設當前排序的序列為R【low：high】，其中l(wèi)ow<=high，如果序列的規(guī)模足夠小則直接進行排序，否則分三步處理：A分解B求解子問題C合并描述算法voidQuickSort(intR，intlow，inthigh)intpivotpos；/劃分后的基準元素所對應的位置if(low<high)/僅當區(qū)間長度大于1時才須排序pivotpos=Partition(R,low,high)；QuickSort(R,low

4、,pivotpos-1)；/對左區(qū)間遞歸排序QuickSort(R,pivotpos+1,high)；/對右區(qū)間遞歸排序正確性證明原始序列：49386597761327第一次掃描：27381349769765以27為基準元素得到的序列:132738以76為基準元素得到的序列：657697最終序列為：13、27、38、49、65、76、97算法復雜性分析最壞情況O(n2)?O(1)n=1T(n)=i?T(n-1)+O(n)n>1精選范本最好情況O(nlogn)1 nT(n)=?(T(n-k)+T(k-1)+n nk=i平均情況：O(nlogn)T(n尸？。?2T(n/2)+O(n)n=1n>1空間復雜性：由于快速排序算法是遞歸執(zhí)行，需要一個棧來存放每一層遞歸調(diào)用的必要信息，其最大容量應與遞歸調(diào)用的深度一致。最好情況下，若每次劃分較為均勻，則遞歸樹的高度為O(logn),故遞歸所需?？臻g為O(logn)。最壞情況下，遞歸樹的高度為O(n),所需的?？臻g同為O(n).平均情況下，所需?？臻g為O(logn)。算法實現(xiàn)與測試實驗總結(jié)在學數(shù)據(jù)結(jié)構(gòu)這門課時，我們就學過多種