java遞歸調用實現排序原理

① 快速排序演算法原理與實現

快速排序的原理：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小。

然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

假設要排序的數組是A[1]……A[N]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然後將所有比它的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一躺快速排序。一躺快速排序的演算法是：

1、設置兩個變數I、J，排序開始的時候I：=1，J：=N；

2、以第一個數組元素作為關鍵數據，賦值給X，即X：=A[1]；

3、從J開始向前搜索，即由後開始向前搜索（J：=J-1），找到第一個小於X的值，兩者交換；

4、從I開始向後搜索，即由前開始向後搜索（I：=I+1），找到第一個大於X的值，兩者交換；

5、重復第3、4步，直到I=J。

(1)java遞歸調用實現排序原理擴展閱讀：

設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選用數組的第一個數）作為關鍵數據，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。

值得注意的是，快速排序不是一種穩定的排序演算法，也就是說，多個相同的值的相對位置也許會在演算法結束時產生變動。

一趟快速排序的演算法是：

1、設置兩個變數i、j，排序開始的時候：i=0，j=N-1；

2、以第一個數組元素作為關鍵數據，賦值給key，即key=A[0]；

3、從j開始向前搜索，即由後開始向前搜索(j--)，找到第一個小於key的值A[j]，將A[j]的值賦給A[i]；

4、從i開始向後搜索，即由前開始向後搜索(i++)，找到第一個大於key的A[i]，將A[i]的值賦給A[j]；

5、重復第3、4步，直到i=j； (3,4步中，沒找到符合條件的值，即3中A[j]不小於key,4中A[i]不大於key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進行交換的時候i， j指針位置不變。

② 用java冒泡排序和遞歸演算法

冒泡排序演算法的運作如下：（從後往前）
1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元3. 素應該會是最大的數。
4. 針對所有的元素重復以上的步驟，除了最後一個。
5. 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
遞歸演算法
遞歸演算法流程
遞歸過程一般通過函數或子過程來實現。遞歸方法：在函數或子過程的內部，直接或者間接地調用自己的演算法時間復雜度
若文件的初始狀態是正序的，一趟掃描即可完成排序。所需的關鍵字比較次數

和記錄移動次數

均達到最小值：

，

。
所以，冒泡排序最好的時間復雜度為

。
若初始文件是反序的，需要進行

趟排序。每趟排序要進行

次關鍵字的比較(1≤i≤n-1)，且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下，比較和移動次數均達到最大值：

冒泡排序的最壞時間復雜度為

。
綜上，因此冒泡排序總的平均時間復雜度為

。

演算法穩定性
冒泡排序就是把小的元素往前調或者把大的元素往後調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以，如果兩個元素相等，我想你是不會再無聊地把他們倆交換一下的；如果兩個相等的元素沒有相鄰，那麼即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前後順序並沒有改變，所以冒泡排序是一種穩定排序演算法。

遞歸演算法是一種直接或者間接地調用自身演算法的過程。在計算機編寫程序中，遞歸演算法對解決一大類問題是十分有效的，它往往使演算法的描述簡潔而且易於理解。
遞歸演算法解決問題的特點：
(1) 遞歸就是在過程或函數里調用自身。
(2) 在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。
(3) 遞歸演算法解題通常顯得很簡潔，但遞歸演算法解題的運行效率較低。所以一般不提倡用遞歸演算法設計程序。
(4) 在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。所以一般不提倡用遞歸演算法設計程序。

③ java中遞歸演算法是什麼怎麼算的

一、遞歸演算法基本思路：

Java遞歸演算法是基於語言實現的遞歸演算法。遞歸演算法是一種直接或者間接調用自身函數或者方法的演算法。遞歸演算法實質是把問題分解成規模縮小的同類問題的子問題，然後遞歸調用方法表示問題的解。遞歸往往能給我們帶來非常簡潔非常直觀的代碼形式，從而使我們的編碼大大簡化，然而遞歸的思維確實跟我們的常規思維相逆的，通常都是從上而下的思維問題，而遞歸趨勢從下往上的進行思維。

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

【1】遞歸就是方法里調用自身。

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

【3】遞歸演算法代碼顯得很簡潔，但遞歸演算法解題的運行效率較低。所以不提倡用遞歸設計程序。

【4】在遞歸調用的過程中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等，所以一般不提倡用遞歸演算法設計程序。

【5】在做遞歸演算法的時候，一定把握出口，也就是做遞歸演算法必須要有一個明確的遞歸結束條件。這一點是非常重要的。其實這個出口就是一個條件，當滿足了這個條件的時候我們就不再遞歸了。

三、代碼示例：

publicclassFactorial{

//thisisarecursivefunction

intfact(intn){

if(n==1)return1;

returnfact(n-1)*n;

}}

publicclassTestFactorial{publicstaticvoidmain(String[]args){

//TODOAuto-generatedmethodstub

Factorialfactorial=newFactorial();

System.out.println("factorial(5)="+factorial.fact(5));

}
}

代碼執行流程圖如下：

此程序中n=5就是程序的出口。