快速排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

算法步骤：

1 、从数列中挑出一个元素，称为 "基准"（pivot）

2 、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作

3 、递归（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

这里简单的介绍一下递归的三个原则，

1、有基本的结束条件，比如这里结束条件是只剩两个数对比

2、问题规模不断减少，比如这里不断地对比两个数字，剩下的可以比的数不断减少

3、调用函数自身，例如累加返回return x+add(x-1)

本处代码"[x for x in arr if x<i]"为“list comprehension”（列表推导式）是一个python书写技巧，用法如下：

列表推导式提供了从序列创建列表的简单途径。通常应用程序将一些操作应用于某个序列的每个元素，用其获得的结果作为生成新列表的元素，或者根据确定的判定条件创建子序列。

每个列表推导式都在 for 之后跟一个表达式，然后有零到多个 for 或 if 子句。返回结果是一个根据表达从其后的 for 和 if 上下文环境中生成出来的列表。如果希望表达式推导出一个元组，就必须使用括号。

这里我们将列表中每个数值乘三，获得一个新的列表：

>>> vec = [2, 4, 6]
>>> [3*x for x in vec]
[6, 12, 18]

教程讲解视频：【排序算法精华3】快速排序 (上）_哔哩哔哩_bilibili

#简单的快排代码如下：

def qsort(arr):

    if len(arr)<=1:

        return arr

    #元素数量为0或1，直接返回

    elif len(arr)==2:

        #有2个元素的情况

        if arr[0]>arr[1]:

            return arr[1],arr[0]

        else:

            return arr

    else:

        #选取标杆

        i=arr[0]

        #比标杆小的元素集合

        L=[x for x in arr if x<i]

        #比标杆大的元素集合

        R=[x for x in arr if x>i]

        #重复以上两个步骤并合并

        res=qsort(L)+qsort(R)+[i]

        return res

Myarr=[5,2.343,35,6,8,24,67]

qsort(Myarr)