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

　　遞歸算法的思想

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

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

　　遞歸算法的特點(diǎn)：

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

　　遞歸算法解決問(wèn)題的特點(diǎn)：

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

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

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

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

　　遞歸算法的要求

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

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

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

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

　　簡(jiǎn)單步驟:

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

　　2.明確方法出口

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

　　快速排序

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

　　算法描述：

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

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

　　要注意算法描述和遞歸的應(yīng)用

　　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++;

　　}

　　}

　　// 為左邊部分進(jìn)行再次劃分

　　QuickSort(arr,start,e-1);

　　// 為右邊部分再次劃分

　　QuickSort(arr,s+1,end);

　　}

　　}