VR開發(fā)入門教程44：簡單算法之快速排序

　　遞歸算法的思想

　　遞歸算法是把問題轉(zhuǎn)化為規(guī)模縮小了的同類問題的子問題。然后遞歸調(diào)用函數(shù)(或過程)來表示問題的解。在C語言中的運行堆棧為他的存在提供了很好的支持，過程一般是通過函數(shù)或子過程來實現(xiàn)。

　　遞歸算法：在函數(shù)或子過程的內(nèi)部，直接或者間接地調(diào)用自己的算法。

　　遞歸算法的特點：

　　遞歸算法是一種直接或者間接地調(diào)用自身算法的過程。在計算機編寫程序中，遞歸算法對解決一大類問題是十分有效的，它往往使算法的描述簡潔而且易于理解。

　　遞歸算法解決問題的特點：

　　(1) 遞歸就是在過程或函數(shù)里調(diào)用自身。

　　(2) 在使用遞歸策略時，必須有一個明確的遞歸結(jié)束條件，稱為遞歸出口。

　　(3) 遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運行效率較低。所以一般不提倡用遞歸算法設(shè)計程序。

　　(4) 在遞歸調(diào)用的過程當中系統(tǒng)為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數(shù)過多容易造成棧溢出等。所以一般不提倡用遞歸算法設(shè)計程序。

　　遞歸算法的要求

　　遞歸算法所體現(xiàn)的“重復”一般有三個要求：

　　一是每次調(diào)用在規(guī)模上都有所縮小(通常是減半);

　　二是相鄰兩次重復之間有緊密的聯(lián)系，前一次要為后一次做準備(通常前一次的輸出就作為后一次的輸入);

　　三是在問題的規(guī)模極小時必須用直接給出解答而不再進行遞歸調(diào)用，因而每次遞歸調(diào)用都是有條件的(以規(guī)模未達到直接解答的大小為條件)，無條件遞歸調(diào)用將會成為死循環(huán)而不能正常結(jié)束。

　　簡單步驟:

　　1.明確確定方法的功能含義

　　2.明確方法出口

　　3.在使用中遇到符合方法功能定義的地方調(diào)用方法

　　快速排序

　　快速排序是高級排序里最流行的一種，大多數(shù)情況下都是最快的

　　算法描述：

　　1.把序列劃分為兩個部分：左邊較小的部分和右邊較大的部分

　　2.調(diào)用自己為左邊排序 3.調(diào)用自己為右邊排序

　　要注意算法描述和遞歸的應用

　　public static void QuickSort(int[] arr,int start,int end)

　　{

　　if (start < end)

　　{

　　bool turn = true;

　　int s = start;

　　int e = end;

　　while (s < e)

　　{

　　if (arr[s] > arr[e])

　　{

　　int temp = arr[s];

　　arr[s] = arr[e];

　　arr[e] = temp;

　　turn = !turn;

　　}

　　if (turn == true)

　　{

　　e--;

　　}

　　else

　　{

　　s++;

　　}

　　}

　　// 為左邊部分進行再次劃分

　　QuickSort(arr,start,e-1);

　　// 為右邊部分再次劃分

　　QuickSort(arr,s+1,end);

　　}

　　}