vlambda博客
学习文章列表

算法之快速排序(递归实现)

什么是递归函数呢?在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函数。

编写递归函数时,必须告诉它何时停止递归。正因为如此,每个递归 函数都有两部分:基线条件 (base case)和递归条件 (recursive case)。递归条件指的是函数调用自己,而基线条件则指的是函数不再 调用自己,从而避免形成无限循环。

 
   
   
 
  1. def countdown(i):

  2. '''递归举例方法'''

  3. print (i)

  4. if(i<=0): #-------------------------------------------基线条件

  5. print("函数执行完成")

  6. return

  7. else: #----------------------------------------------递归条件

  8. i=i-1

  9. countdown(i)

快速排序 排序一个数组arry1=[4,6,3,5,2],从大到小排列数组中的元素值

思路:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。


  • 1 首先,从数组中选择一个元素,这个元素被称为基准值 暂时将数组的第一个元素用作基准值。算法之快速排序(递归实现)



  • 24作为基准值,以4为基准,把原始数组arry1分成两部分数组, arry2:比4小的部分 arry3:比4大的部分算法之快速排序(递归实现)-3 在数组arry2中以第一个元素作为基准值算法之快速排序(递归实现)--3.1 arry2分成两部分,比3小的一部分arry21,与比3大的一部分arry22 这时arry21与arry22中的元素都不超过1个了,不用往下再分算法之快速排序(递归实现)--3.2arry2中完成排序算法之快速排序(递归实现)--4同理在arry3中以以第一个元素作为基准值算法之快速排序(递归实现)


--4.1arry3分成两部分,比6小的一部分arry31,与比6大的一部分arry32 这时arry31与arry32中的元素都不超过1个了,不用往下再分算法之快速排序(递归实现)

--4.2arry3中完成排序算法之快速排序(递归实现)

-5把集合arry2 基准值4 数组arry3组合起来,完成对原始数组的排序算法之快速排序(递归实现)

完整代码:

  • C#

 
   
   
 
  1. #region 快速排序

  2. /// <summary>

  3. /// 快速排序

  4. /// </summary>

  5. /// <param name="Arrylist">要排序的集合</param>

  6. /// <returns></returns>

  7. public static List<int> KuaiPaiMethod(List<int> Arrylist)

  8. {


  9. if (Arrylist.Count < 2)

  10. {

  11. return Arrylist;

  12. }

  13. //比基准值小的数据集合

  14. List<int> MinArry = new List<int>();

  15. //比基准值大的数据集合

  16. List<int> MaxArry = new List<int>();

  17. int label_value = Arrylist[0];//比较基准值

  18. for (int i = 1; i < Arrylist.Count; i++)

  19. {

  20. if (Arrylist[i] <= label_value)

  21. {

  22. MinArry.Add(Arrylist[i]);

  23. }

  24. else

  25. {

  26. MaxArry.Add(Arrylist[i]);

  27. }

  28. }

  29. var result = KuaiPaiMethod(MinArry);

  30. var MaxSum = KuaiPaiMethod(MaxArry);

  31. result.Add(label_value);

  32. result.AddRange(MaxSum);

  33. return result;

  34. }

  35. #endregion

  • Python

 
   
   
 
  1. def KuaiPai(arry):

  2. '''快速排序(从小到大)'''

  3. if len(arry)<2:

  4. return arry

  5. else:

  6. lable_num=arry[0]#基准值

  7. min_arry=[]

  8. max_arry=[]

  9. for x in arry[1:]:

  10. if x<=lable_num:

  11. min_arry.append(x)

  12. else:

  13. max_arry.append(x)

  14. #把几个数组直接相加,合并为一个数组

  15. return KuaiPai(min_arry)+[lable_num]+KuaiPai(max_arry)