什么是快速排序？
快速排序，顾名思义它排序的速度十分的快。
它快到什么程度呢？
C语言标准库中的qsort函数就是使用快速排序实现的！
说到快速排序，离不开两个重要的概念： 递归 和 分治算法(Divide ans conquer, D&C)。
如果要讲清楚这两个概念，可以单独写两篇文章出来了。
因此这里不做深入，只简单介绍一下：
递归：重复调用自己的函数。一般由两个部分组成基线条件 和 递归条件，程序在符合基线条件的时候返回，在符合递归条件的时候调用自己。
分治算法(Divide ans conquer, D&C): 将大的问题化解为相同类型的小问题。一种著名的递归式问题解决办法，一般分为两个步骤，首先找出尽可能简单的基线条件，然后将递归的将问题分解为小问题，直到小问题符合基线条件。
假如还不太明白这两个概念，没关系，看下面的例子就可以了。
排序过程
既然快速排序的核心思想是D&C，那么它的基线条件和递归条件分别是什么呢？
首先我们思考一下，什么样的数组需要排序？
长度为
0的数组需要排序吗？
不需要。因为它的没有顺序的概念。长度为
1的数组需要排序吗？
不需要。因为可以把它看做一个有序数组了。长度为
2的数组需要排序吗？
需要。因为并不能确定它的顺序。
因此，我们可以把长度为0或1的数组设为是基线条件。
递归条件则是长度大于1的数组。
举个例子：
假如现在有一个无序数组disorder_arr = [4,2,19,10,-1]。
第一步：
我们取第一个数4为基准数，
然后将小于4的分成一类：[2,-1]，放在4的左边
大于4的分成一类：[19,10]，放在4的右边。
第二步：
对 长度大于1 的数组重复上面的步骤，如下图所示：
直到所有的数组都符合基线条件(长度为0或1)后，
我们便可得到一个排列有序的数组了。
写一段代码
代码依然是使用Python3实现的
# quickSort.py
class Solution:
def quick(self, disorder_arr: list):
# 递归实现
if len(disorder_arr) < 2: # 基线条件
return disorder_arr
base_num = disorder_arr[0] # 基数，取数组第一个数
min_arr = [] # 小于基数的数
max_arr = [] # 大于基数的数
for i in range(1, len(disorder_arr)): # 遍历一遍数组，
if disorder_arr[i] <= base_num:
min_arr.append(disorder_arr[i])
elif disorder_arr[i] > base_num:
max_arr.append(disorder_arr[i])
return self.quick(min_arr) + [base_num] + self.quick(max_arr) # 递归
总结
快速排序的原理是首先找到一个基准数，然后通过遍历数组，
将小于基准数的数分成一类，放在基准数的左边，
大于基准数的数分成另一类，放在基准数的右边。
在最优情况下，快速排序算法的平均时间复杂度是O(nlogn),
但是最坏的情况下，它的时间复杂度也会达到O(n^2)。
以上代码已上传至github
欢迎大家友好交流[握手]
