對于一個程序員來說，算法是必不可少的�，F(xiàn)在的算法五花八門，讓人有點找不到北，不過歸根結底，也就那么幾類，其他算法都是這些算法的優(yōu)化或者派生。
今天就跟大家說說分治法。
【算法本質】
分治法是得益于“大禹治水”的思想研究得來的算法。本質為“分而治之”。俗一點就是“大事化小，小事化了”。
【設計思想】
將一個難以直接解決的大問題分解成一些規(guī)模較小的相同問題以便各個擊破，分而治之。如果規(guī)模為n的問題，可以分解成k個子問題，1<k<=n，這些子問題相互獨立切與原問題相同，分治法產生的子問題，往往是原問題的較小模式，這就為遞歸技術提供了方便。
【算法遞歸步驟】
（一）分解。將原問題分解成一系列子問題。
（二）求解。遞歸地求解各子問題。若子問題足夠小，則直接求解。
（三）合并。將子問題的解合并成原問題的解。
【沙場點兵】
這是一道軟考題。QUICKSORT函數(shù)為快速排序，PARTITION函數(shù)作用為對數(shù)組A排序，并返回樞軸元素位置下標。
舉一個實例：對數(shù)組A=｛ 9，3，5，8，7｝ 進行排序。
跟著代碼走，現(xiàn)在p=0,r=4，所以p<r，執(zhí)行q=PARTITION(A，p，r)，進入第一次排序。
x=A[r]=7，i=p-1=-1，j的變化從p-》r-1，即0-》3。循環(huán)體內，比較A[j]與x的值：
j=0時，A[j]=9>x。j=1進入下次循環(huán)，如圖；
j=1時，A[j]=3<x，i=i+1=0，交換A[i]和A[j]。j=2進入下次循環(huán)，如圖；
j=2時，A[j]=8>x，j=3進入下次循環(huán)，如圖；
j=3時，A[j]=4<x，i=i+1=2，交換A[i]和A[j]，如圖。j=4>r-1，退出循環(huán)；
根據(jù)分治算法，由樞軸元素為界限，把原數(shù)組劃分為2組，樞軸元素左邊的元素>樞軸元素>樞軸元素右邊的元素。所以，我們現(xiàn)在要做的就是把x的值與i+1所在位置的元素進行交換。即A[i+1]與A[r]交換。
最后把樞軸元素的下標返回給q，即q=2。第一趟排序完成。然后執(zhí)行QUICKSORT（A，p，q-1）和QUICKSORT（A，q+1，r）。即分別對劃分的子數(shù)組進行快速排序�？赐暾膱D解：
不難發(fā)現(xiàn)，在分治策略中，由于子問題與原問題在結構和解法上的相似性，用分治方法解決的問題，大都采用了遞歸的形式。在各種排序方法中，如歸并排序、堆排序、快速排序等，都存在有分治的思想。
喜歡 
頂
難過
囧
圍觀
無聊
