『壹』 用java冒泡排序和遞歸演算法
冒泡排序演算法的運作如下：（從後往前）
1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元3. 素應該會是最大的數。
4. 針對所有的元素重復以上的步驟，除了最後一個。
5. 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
遞歸演算法
遞歸演算法流程
遞歸過程一般通過函數或子過程來實現。遞歸方法：在函數或子過程的內部，直接或者間接地調用自己的演算法時間復雜度
若文件的初始狀態是正序的，一趟掃描即可完成排序。所需的關鍵字比較次數
和記錄移動次數
均達到最小值：
，
。
所以，冒泡排序最好的時間復雜度為
。
若初始文件是反序的，需要進行
趟排序。每趟排序要進行
次關鍵字的比較(1≤i≤n-1)，且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下，比較和移動次數均達到最大值：
冒泡排序的最壞時間復雜度為
。
綜上，因此冒泡排序總的平均時間復雜度為
。
演算法穩定性
冒泡排序就是把小的元素往前調或者把大的元素往後調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以，如果兩個元素相等，我想你是不會再無聊地把他們倆交換一下的；如果兩個相等的元素沒有相鄰，那麼即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前後順序並沒有改變，所以冒泡排序是一種穩定排序演算法。
遞歸演算法是一種直接或者間接地調用自身演算法的過程。在計算機編寫程序中，遞歸演算法對解決一大類問題是十分有效的，它往往使演算法的描述簡潔而且易於理解。
遞歸演算法解決問題的特點：
(1) 遞歸就是在過程或函數里調用自身。
(2) 在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。
(3) 遞歸演算法解題通常顯得很簡潔，但遞歸演算法解題的運行效率較低。所以一般不提倡用遞歸演算法設計程序。
(4) 在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。所以一般不提倡用遞歸演算法設計程序。
『貳』 java中，用遞歸方法求n個數的無重復全排列，n=3。
程序如下所示，輸入格式為：
5
31212
第一行是數字個數，第二行有n個數，表示待排列的數，輸入假設待排序的數均為非負數。
importjava.io.File;
importjava.io.FileNotFoundException;
importjava.util.Arrays;
importjava.util.Scanner;
publicclassMain{
staticfinalintmaxn=1000;
intn;//數組元素個數
int[]a;//數組
boolean[]used;//遞歸過程中用到的輔助變數，used[i]表示第i個元素是否已使用
int[]cur;//保存當前的排列數
//遞歸列印無重復全排列，當前列印到第idx位
voidprint_comb(intidx){
if(idx==n){//idx==n時，表示可以將cur輸出
for(inti=0;i<n;++i){
if(i>0)System.out.print("");
System.out.print(cur[i]);
}
System.out.println();
}
intlast=-1;//因為要求無重復，所以last表示上一次搜索的值
for(inti=0;i<n;++i){
if(used[i])continue;
if(last==-1||a[i]!=last){//不重復且未使用才遞歸下去
last=a[i];
cur[idx]=a[i];
//回溯法
used[i]=true;
print_comb(idx+1);
used[i]=false;
}
}
}
publicvoidgo()throwsFileNotFoundException
{
Scannerin=newScanner(newFile("data.in"));
//讀取數據並排序
n=in.nextInt();
a=newint[n];
for(inti=0;i<n;++i)a[i]=in.nextInt();
Arrays.sort(a);
//初始化輔助變數並開始無重復全排列
cur=newint[n];
used=newboolean[n];
for(inti=0;i<n;++i)used[i]=false;
print_comb(0);
in.close();
}
publicstaticvoidmain(String[]args)throwsFileNotFoundException{
newMain().go();
}
}
客觀來說，非遞歸的無重復全排列比較簡單且高效。