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

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

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

def countdown(i):
    '''递归举例方法'''
    print (i)
    if(i<=0):  #-------------------------------------------基线条件
        print("函数执行完成")
        return
    else:    #----------------------------------------------递归条件
         i=i-1
        countdown(i)

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

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

image.png
  • 1
    首先,从数组中选择一个元素,这个元素被称为基准值
    暂时将数组的第一个元素用作基准值。


    image.png
  • 2
    4作为基准值,以4为基准,把原始数组arry1分成两部分数组,
    arry2:比4小的部分
    arry3:比4大的部分


    image.png

    -3 在数组arry2中以第一个元素作为基准值


    image.png

    --3.1
    arry2分成两部分,比3小的一部分arry21,与比3大的一部分arry22
    这时arry21与arry22中的元素都不超过1个了,不用往下再分
    image.png

    --3.2arry2中完成排序
    image.png

    --4同理在arry3中以以第一个元素作为基准值


    image.png

--4.1
arry3分成两部分,比6小的一部分arry31,与比6大的一部分arry32
这时arry31与arry32中的元素都不超过1个了,不用往下再分


image.png

--4.2arry3中完成排序


image.png

-5把集合arry2 基准值4 数组arry3组合起来,完成对原始数组的排序


image.png
image.png

完整代码:

  • C#
   #region 快速排序
        /// <summary>
        /// 快速排序
        /// </summary>
        /// <param name="Arrylist">要排序的集合</param>
        /// <returns></returns>
        public static List<int> KuaiPaiMethod(List<int> Arrylist)
        {
           
            if (Arrylist.Count < 2)
            {
                return Arrylist;
            }
            //比基准值小的数据集合
            List<int> MinArry = new List<int>();
            //比基准值大的数据集合
            List<int> MaxArry = new List<int>();
            int label_value = Arrylist[0];//比较基准值
            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]#基准值
        min_arry=[]
        max_arry=[]
        for x in arry[1:]:
            if  x<=lable_num:
                min_arry.append(x)
            else:
                max_arry.append(x)
    #把几个数组直接相加,合并为一个数组
    return KuaiPai(min_arry)+[lable_num]+KuaiPai(max_arry)

image.png
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 概述 因为健忘,加上对各种排序算法理解不深刻,过段时间面对排序就蒙了。所以决定对我们常见的这几种排序算法进行统一总...
    清风之心阅读 722评论 0 1
  • 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    蚁前阅读 5,222评论 0 52
  • 查找和排序算法是算法的入门知识,其经典思想可以用于很多算法当中。因为其实现代码较短,应用较常见。所以在面试中经常会...
    JourWon阅读 2,261评论 0 34
  • 0、排序算法说明 0.1 排序的定义 对一序列对象根据某个关键字进行排序。 0.2 术语说明 稳定:如果a原本在b...
    SithCait阅读 2,092评论 0 37
  • 今天我们数学课上学的。六到十的加减法。我们语文课上学的课文《秋天》。学的汉字是什么?。秋 大 人 子 了!我们还上...
    杨昊天_阅读 392评论 0 0