遞歸排序演算法

1. 設計遞歸演算法生成n個元素的所有排列對象

#include<iostream>
#include<iterator>
#include<algorithm>
using namespace std;

template<class T>
void permutation(T list[], int k, int m)
{
if (k == m)
{
(list, list + m + 1, ostream_iterator<T>(cout, "")); //將當前list排序
cout << endl;
}
else{
for (int i = k; i <= m; i++)
{
swap(list[i], list[k]); //將下標為i的元素交換到k位置，類似從list[k:m]中剔除操作
permutation(list, k + 1, m);
swap(list[i], list[k]);
}
}
}

int main(int argc, char* argv[])
{
char arr[3] = { 'a', 'b', 'c' };
cout << "排序結果如下：" << endl;
permutation(arr, 0, 2);
return 0;

}

(1)遞歸排序演算法擴展閱讀

遞歸，在數學與計算機科學中，是指在函數的定義中使用函數自身的方法。也就是說，遞歸演算法是一種直接或者間接調用自身函數或者方法的演算法。

通俗來說，遞歸演算法的實質是把問題分解成規模縮小的同類問題的子問題，然後遞歸調用方法來表示問題的解。

遞歸的基本原理

第一：每一級的函數調用都有自己的變數。

第二：每一次函數調用都會有一次返回。

第三：遞歸函數中，位於遞歸調用前的語句和各級被調用函數具有相同的執行順序。

第四：遞歸函數中，位於遞歸調用後的語句的執行順序和各個被調用函數的順序相反。

第五：雖然每一級遞歸都有自己的變數，但是函數代碼並不會得到復制。

2. 什麼是遞歸演算法

一、含義不同：

遞歸是重復調用函數自身實現循環。迭代是函數內某段代碼實現循環，循環代碼中參與運算的變數同時是保存結果的變數，當前保存的結果作為下一次循環計算的初始值。寬高棚

遞歸循環中，遇到滿足終止條件的情況時逐層返回來結束。迭代則使用計數器結束循環。當然很多情況都是多種循環混合採用，這要根據具體需求。

二、結構不同：

遞歸與迭代都是基於控制結構：迭代用重復結構，而遞歸用選擇結構。 遞歸與迭代都涉及重復：迭代顯式使用重復結構，而遞歸通過重復函數調用實現重復。

遞歸與迭代都涉及終止測試：迭代在循環條件失敗時終止，遞歸慎則在遇到基本情況時終止，使用計數器控制重復的迭代和遞歸都逐漸到達終止點：迭代一直修改計數器，直到計數器值使循環條件失敗；遞歸不念納斷產生最初問題的簡化副本，直到達到基本情況。

遞歸演算法一般用於解決三類問題：

(1)數據的定義是按遞歸定義的。（Fibonacci函數）

(2)問題解法按遞歸演算法實現。

這類問題雖則本身沒有明顯的遞歸結構，但用遞歸求解比迭代求解更簡單，如Hanoi問題。

(3)數據的結構形式是按遞歸定義的。

如二叉樹、廣義表等，由於結構本身固有的遞歸特性，則它們的操作可遞歸地描述。

以上內容參考：網路-遞歸

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

冒泡排序

（1）基本思想：在要排序的一組數中，對當前還未排好序的范圍內的全部數，自上而下對相鄰的兩個數依次進行比較和調整，讓較大的數往下沉，較小的往上冒。即：每當兩相鄰的數比較後發現它們的排序與排序要求相反時，就將它們互換。

（2）用java實現

ublicclassbubbleSort{

publicbubbleSort(){

inta[]={1,54,6,3,78,34,12,45};

inttemp=0;

for(inti=0;i<a.length;i++){

for(intj=i+1;j<a.length;j++){

if(a[i]>a[j]){

temp=a[i];

a[i]=a[j];

a[j]=temp;

}

}

}

for(inti=0;i<a.length;i++)

System.out.println(a[i]);

}

}

遞歸

遞歸演算法，就是程序的自身調用。表現在一段程序中往往會遇到調用自身的那樣一種coding策略，可以利用大道至簡的思想，把一個大的復雜的問題層層轉換為一個小的和原問題相似的問題來求解的這樣一種策略。能看到我們會用很少的語句解決了非常大的問題，所以遞歸策略的最主要體現就是小的代碼量解決了非常復雜的問題。

java代碼：

packagecom.cjq.filedown;

publicclassFab{

publicstaticvoidmain(Stringargs[]){
System.out.println(fab(5));
}

privatestaticintfab(intindex){
if(index==1||index==2){
return1;
}else{
returnfab(index-1)+fab(index-2);
}
}
}

4. 計算機演算法中的遞歸法與選擇排序法是什麼請細講

遞歸是設計和描述演算法的一種有力的工具，由於它在復雜演算法的描述中被經常採用，為此在進一步介紹其他演算法設計方法之前先討論它。
能採用遞歸描述的演算法通常有這樣的特徵：為求解規模為N的問題，設法將它分解成規模較小的問題，然後從這些小問題的解方便地構造出大問題的解，並且這些規模較小的問題也能採用同樣的分解和綜合方法，分解成規模更小的問題，並從這些更小問題的解構造出規模較大問題的解。特別地，當規模N=1時，能直接得解。

遞歸演算法的執行過程分遞推和回歸兩個階段。在遞推階段，把較復雜的問題（規模為n）的求解推到比原問題簡單一些的問題（規模小於n）的求解。例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是說，為計算fib(n)，必須先計算fib(n-1)和fib(n-2)，而計算fib(n-1)和fib(n-2)，又必須先計算fib(n-3)和fib(n-4)。依次類推，直至計算fib(1)和fib(0)，分別能立即得到結果1和0。在遞推階段，必須要有終止遞歸的情況。例如在函數fib中，當n為1和0的情況。
在回歸階段，當獲得最簡單情況的解後，逐級返回，依次得到稍復雜問題的解，例如得到fib(1)和fib(0)後，返回得到fib(2)的結果，……，在得到了fib(n-1)和fib(n-2)的結果後，返回得到fib(n)的結果。
在編寫遞歸函數時要注意，函數中的局部變數和參數知識局限於當前調用層，當遞推進入「簡單問題」層時，原來層次上的參數和局部變數便被隱蔽起來。在一系列「簡單問題」層，它們各有自己的參數和局部變數。
由於遞歸引起一系列的函數調用，並且可能會有一系列的重復計算，遞歸演算法的執行效率相對較低。當某個遞歸演算法能較方便地轉換成遞推演算法時，通常按遞推演算法編寫程序。例如上例計算斐波那契數列的第n項的函數fib(n)應採用遞推演算法，即從斐波那契數列的前兩項出發，逐次由前兩項計算出下一項，直至計算出要求的第n項。

選擇排序法 是對 定位比較交換法 的一種改進。在講選擇排序法之前我們先來了解一下定位比較交換法。為了便於理解，設有10個數分別存在數組元素a[0]～a[9]中。定位比較交換法是由大到小依次定位a[0]～a[9]中恰當的值（和武林大會中的比武差不多），a[9]中放的自然是最小的數。如定位a[0],先假定a[0]中當前值是最大數，a[0]與後面的元素一一比較，如果a[4]更大，則將a[0]、a[4]交換，a[0]已更新再與後面的a[5]～a[9]比較，如果a[8]還要大，則將a[0]、a[8]交換，a[0]又是新數，再與a[9]比較。一輪比完以後，a[0]就是最大的數了，本次比武的武狀元誕生了，接下來從a[1]開始，因為狀元要休息了，再來一輪a[1]就是次大的數，也就是榜眼，然後從a[2]開始，比出探花，真成比武大會了，當必到a[8]以後，排序就完成了。
下面給大家一個例子：
mai()
{
int a[10];
int i,j,t;
for ( i = 0; i < 10; i ++ ) scanf("%d",&a[ i ]); /*輸入10個數，比武報名，報名費用10000￥ ^_^*/
for ( i = 0; i < 9; i ++ )
for ( j = i + 1; j < 10; j ++)
if ( a[ i ] < a[ j ] ) { t = a[ i ]; a[ i ] = a[ j ]; a[ j ] = t; } /*打不過就要讓出頭把交椅，不過a[ i ]比較愛面子，不好意思見 a[ j ]，讓t幫忙*/
for( i = 0; i < 10; i ++) printf("%4d",a[ i ]); /*顯示排序後的結果*/
}
好啦，羅嗦了半天總算把定位比較排序法講完了，這個方法不錯，容易理解，就是有點麻煩，一把椅子換來換去，哎～
所以就有了下面的選擇排序法，開始的時候椅子誰也不給，放在一邊讓大家看著，找個人k記錄比賽結果，然後發椅子。具體來講呢就是，改進定位比較排序法，但是這個改進只是一部分，比較的次數沒變，該怎麼打還是怎麼打，就是不用換椅子了。每次外循環先將定位元素的小標i值記錄到K，認為a[k]是最大元素其實i=k還是a[ i ]最大，a[k]與後面的元素一一比較，該交換的也是也不換，就是把K的值改變一下就完了，最後在把a[k]與a[ i ]交換，這樣a就是最大的元素了。然後進入下一輪的比較。選擇排序法與定位比較排序法相比較，比的次數沒變，交換的次數減少了。
下面也寫個例子：
main()
{
int a[10];
int i,j,t,k;
for ( i = 0; i < 10; i ++ ) scanf("%d",&a[ i ]); /*輸入10個數，比武報名，報名費用10000￥ ^_^*/
for ( i = 0; i < 9; i ++ )
{ k = i; /*裁判AND記者實時追蹤報道比賽情況*/
for ( j = i + 1; j < 10; j ++)
if ( a[ k ] < a[ j ] ) k = j;
t = a[ i ]; a[ i ] = a[ k ]; a[ k ] = t; /* t 發放獎品*/
}
for( i = 0; i < 10; i ++) printf("%4d",a[ i ]); /*顯示排序後的結果*/
}