快速排序由坦率的玫瑰在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
算法实现(1) 从数列中挑出一个元素，称为 “基准”（pivot）；
(2) 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
(3) 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
平均时间复杂度：O(nlogn)
空间复杂度：O(logn)
python代码：
def quick_sort(list): left = [] pivotList = [] right = [] # 递归出口 if len(list) <= 1: return list else: # 将第一个数做为基准 pivot = list[0] for i in list: # 比基准小的值放到left列表 if i < pivot: left.append(i) # 比基准大的值放到right列表 elif i > pivot: right.append(i) # 将和基准相同的值保存在基准列表 else: pivotList.append(i) # 对left列表和right列表继续进行排序 left = quick_sort(left) right = quick_sort(right) return left + pivotList + rightli = [78,17,39,26,72,94,21,12,23,68]quick_sort(li) 时间复杂度计算快速排序涉及到递归调用，所以该算法的时间复杂度还需要从递归算法的复杂度开始说起； 递归算法的时间复杂度公式：T[n] = aT[n/b] + f(n) ；对于递归算法的时间复杂度这里就不展开来说了（具体可参考算法书籍《数据结构与算法python语言描述》等）
最优情况下的时间复杂度快速排序最优的情况就是每一次取到的元素都刚好平分整个数组。 此时的时间复杂度公式则为：T[n] = 2T[n/2] + f(n)；T[n/2]为平分后的子数组的时间复杂度，f[n] 为平分这个数组时所花的时间；下面来推算下，在最优的情况下快速排序时间复杂度的计算(用迭代法)：
T[n] = 2T[n/2] + n —————-第一次递归，令：n = n
T[n] = 2 { 2 T[n/4] + (n/2) } + n —————-第二次递归，令：n = n/2
= = 2^2 T[ n/ (2^2) ] + 2n
T[n] = 2^2 { 2 T[n/ (2^3) ] + n/(2^2)} + 2n —————-第三次递归 令：n = n/(2^2)
= 2^3 T[ n/ (2^3) ] + 3n
T[n] = 2^m T[1] + mn —————-第m次递归(m次后结束)， 令：n = n/( 2^(m-1) )
当最后平分的不能再平分时，也就是说把公式一直往下跌倒，到最后得到T[1]时，说明这个公式已经迭代完了（T[1]是常量了）。
得到：T[n/ (2^m) ] = T[1] ===>> n = 2^m ====>> m = logn；
T[n] = 2^m T[1] + mn ；其中m = logn;
T[n] = 2^(logn) T[1] + nlogn = n T[1] + nlogn = n + nlogn ；其中n为元素个数
又因为当n >= 2时：nlogn >= n (也就是logn > 1)，所以取后面的 nlogn；
综上所述：快速排序最优的情况下时间复杂度为：O( nlogn )
参考https://blog.csdn.net/not_in_mountain/article/details/77976743