基于分治法的快速排序

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

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

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

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