程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> C++ 遞歸函數的詳解

C++ 遞歸函數的詳解

編輯:C++入門知識

C++ 遞歸函數的詳解


說到遞歸函數,就會想起遞歸的快速排序。

1.快速排序是什麼呢?

快速排序的基本思想是:通過一趟快速排序,把待排記錄分成兩
個子序列,其中一個子系列中的記錄都小於另一個子序列,然後,
分別對兩個子序列進行快速排序。
可以看出,快速排序的核心就是劃分子序列。


2.下面讓我們了解一下遞歸函數快速排序的思想:

(1)將待排序的數據放入某數組中(如數組a[]) 中,下標從 low 到 high;

(2)對數組進行如下操作:從數組中取一個元素值作為樞軸

記錄(一般取第 0 號元素,即 a[0]),存入 key(一個變量) 中;

(3)在數組 a 中,將 key 調整到適當位置,然後將比 key
大的元素都放在 key 的右邊,比 key 小的數都放在 key
的左邊。

(4)這一趟排序的結果是key 將原數組 a 分割成
了兩個子數組,key 的左邊的值都比key 小,右邊的都比
key 大。

(5)此時,問題就成了如何都將這兩個子數組進行排序的問題,顯然
對這兩個子數組調用上述方法即可,即進行遞歸調用上述方法,
直到排序完成。

(6)顯然,通過上述過程,當我們處理完所有的元素時,最終結果
為:每個元素的左邊的元素都不大於該元素,而右邊的元素都不小
於該元素。


3.如何確定key的位置呢?

我們確定key的值後,利用 key 將數組 a 劃分成兩個子數組。

具體方法:

(1)取出數組的第 0 個元素,作為分界值放到 key 裡,
即 key = a[0]; 此時,數組元素 a[0] 空閒,用一個左探針left
指示,即 left = 0;
(2)利用右探針 right 從右往左走,尋找小於 key 的元素,找到
後就將該元素的值放進 left 所指示的空閒位置,此時 right 所
指示位置成為空閒位置;
(3)讓左探針 left 往右走,尋找比 key 大的元素,找到則將該
元素的值放進 right 所指示的空閒位置。此時 left 所指示位置
變為空閒;
(4)循環執行 2、3步,直到 right 不再大於 left為止(此時,
意味著將所有元素都與 key 進行了比較)。left 與 right 相遇的
地方就是 key 的位置。


具體的代碼:

#include

void QuickSort( int a[], int low, int high);
void main()
{
int a[] = { 32, 8, 65, 18, 19, 12, 61 };
int i;

QuickSort(a, 0, 6);

for(i=0; i<7; i++)
printf("%4d", a[i]);
}

//QuickSort方法,實現函數的快速排序

void QuickSort( int a[], int low, int high)
{
int key;
int left, right;
// 若待排序列為空或僅有一個元素,則無需排序
if( low >= high ) return ;
// 1 將待排記錄劃分成兩個子序列
// 1.1 選擇序列中第一元素作為軸記錄
key = a[low];
// 1.2 根據軸記錄 key 將待排序列劃分成兩個子序列
left = low;
right = high;

while( left < right )
{
while( left= key)
right--; // right從後向前掃描,跳過"大"的元素
a[left] = a[right]; // 遇到"小"元素,移動到前面去
while( left left++; //left 從前向後掃描,跳過小於軸記錄的元素
a[right] = a[left]; // 遇到"大"元素,移動到後面去
}
// 1.3 放置軸記錄
a[left] = key;
// 2.對兩個子序列分別進行快速排序
QuickSort(a, low, left-1);
QuickSort(a, left+1, high);
}





  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved