10.3.4 快速排序
快速排序（Quick Sort）是对冒泡排序的一种改进，由C.A.R Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
分割时，先选择一个元素，作为大小比较的基准（Pivot）数。把数列里小于Pivot数的元素放到前面，大于Pivot数的元素放到后面。这个基准数可以随意取一个，一般取开始、结束或中间位置的一个元素。
1.快速排序示例举例
根据快速排序算法实现思路，通过取中间值作为基准数，然后分左右两部分进行递归分割排序，举例如下：
初始状态：
用列表存储上述元素data=[12，9，2，8，23，7，16]。
第一轮比较排序过程如下。
（1）取中间值作为基准数。
求中间值下标mid=n//2=3，对应值[mid]=8作为基准数。
（2）从左到右一个个取出data里的元素与中间值进行比较。
12与8比较，把12放入右边列表里right=[12]；
9与8比较，把9放入右边列表里right=[12，9]；
2与8比较，把2放入左边列表里left=[2]；
23与8比较，把23放入右边列表里right=[12，9，23]；(https://www.daowen.com)
7与8比较，把7放入左边列表里left=[2，7]；
16与8比较，把16放入右边列表里right=[12，9，23，16]；
第一轮比较结果为left=[2，7]，中间值为8，right=[12，9，23，16]。
然后继续对left和right分别进行第二轮排序，这里就可以通过递归分别重复（2）的过程；一直到所有的分别递归的列表只有1个元素为止，则递归返回。
2.快速排序代码实现
采用如上举例所示的中间值的情况下，通过递归实现两部分分割排序，最后完成快速排序过程，其代码实现如下：
代码文件：10_3_4_QuickSort.py
上述代码执行结果如下：
注意
递归调用理解提示如下。
每调用一次递归函数本身，在内存里临时记录其调用状态，由此，当需要排序的元素很多时，需要临时消耗大量的内存空间。
当满足递归返回条件时，上例是不满足if n>=2条件时，则一级级把结果往上返回，最后返回给第一次调用处，完成排序过程。
在一行同时递归调用2次本函数时，在内存里同时记录这2个函数的临时状态，如记录QuickSort（[2，7]）+[8]+QuickSort（[12，9，23，16]）。
