什么是遞歸函數(shù)呢？
在函數(shù)內(nèi)部称勋，可以調(diào)用其他函數(shù)胸哥。如果一個(gè)函數(shù)在內(nèi)部調(diào)用自身本身，這個(gè)函數(shù)就是遞歸函數(shù)赡鲜。
編寫遞歸函數(shù)時(shí)空厌，必須告訴它何時(shí)停止遞歸。正因?yàn)槿绱艘辏總€(gè)遞歸
函數(shù)都有兩部分：基線條件 （base case）和遞歸條件 （recursive
case）嘲更。遞歸條件指的是函數(shù)調(diào)用自己，而基線條件則指的是函數(shù)不再
調(diào)用自己揩瞪，從而避免形成無(wú)限循環(huán)赋朦。
def countdown(i):
'''遞歸舉例方法'''
print (i)
if(i<=0): #-------------------------------------------基線條件
print("函數(shù)執(zhí)行完成")
return
else: #----------------------------------------------遞歸條件
i=i-1
countdown(i)
快速排序
排序一個(gè)數(shù)組arry1=[4,6,3,5,2],從大到小排列數(shù)組中的元素值
思路：
通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小李破，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序宠哄，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列嗤攻。
-
1
首先毛嫉，從數(shù)組中選擇一個(gè)元素，這個(gè)元素被稱為基準(zhǔn)值
暫時(shí)將數(shù)組的第一個(gè)元素用作基準(zhǔn)值屯曹。
image.png -
2
4作為基準(zhǔn)值狱庇，以4為基準(zhǔn)惊畏，把原始數(shù)組arry1分成兩部分?jǐn)?shù)組恶耽，
arry2:比4小的部分
arry3:比4大的部分
image.png
-3 在數(shù)組arry2中以第一個(gè)元素作為基準(zhǔn)值
image.png
--3.1
arry2分成兩部分，比3小的一部分arry21颜启，與比3大的一部分arry22
這時(shí)arry21與arry22中的元素都不超過(guò)1個(gè)了偷俭，不用往下再分
image.png
--3.2arry2中完成排序
image.png
--4同理在arry3中以以第一個(gè)元素作為基準(zhǔn)值
image.png
--4.1
arry3分成兩部分，比6小的一部分arry31缰盏，與比6大的一部分arry32
這時(shí)arry31與arry32中的元素都不超過(guò)1個(gè)了涌萤，不用往下再分
--4.2arry3中完成排序
-5把集合arry2 基準(zhǔn)值4 數(shù)組arry3組合起來(lái)，完成對(duì)原始數(shù)組的排序
完整代碼：
- C#
#region 快速排序
/// <summary>
/// 快速排序
/// </summary>
/// <param name="Arrylist">要排序的集合</param>
/// <returns></returns>
public static List<int> KuaiPaiMethod(List<int> Arrylist)
{
if (Arrylist.Count < 2)
{
return Arrylist;
}
//比基準(zhǔn)值小的數(shù)據(jù)集合
List<int> MinArry = new List<int>();
//比基準(zhǔn)值大的數(shù)據(jù)集合
List<int> MaxArry = new List<int>();
int label_value = Arrylist[0];//比較基準(zhǔn)值
for (int i = 1; i < Arrylist.Count; i++)
{
if (Arrylist[i] <= label_value)
{
MinArry.Add(Arrylist[i]);
}
else
{
MaxArry.Add(Arrylist[i]);
}
}
var result = KuaiPaiMethod(MinArry);
var MaxSum = KuaiPaiMethod(MaxArry);
result.Add(label_value);
result.AddRange(MaxSum);
return result;
}
#endregion
- Python
def KuaiPai(arry):
'''快速排序（從小到大）'''
if len(arry)<2:
return arry
else:
lable_num=arry[0]#基準(zhǔn)值
min_arry=[]
max_arry=[]
for x in arry[1:]:
if x<=lable_num:
min_arry.append(x)
else:
max_arry.append(x)
#把幾個(gè)數(shù)組直接相加口猜，合并為一個(gè)數(shù)組
return KuaiPai(min_arry)+[lable_num]+KuaiPai(max_arry)
