简介快速排序（QuickSort）是对冒泡排序的改进。引用元素的值放在左边，大于等于引用元素的值放在右边；然后分别对参考元素的前半部分和后半部分进行同样的处理。以此类推，直到每个子序列元素都剩下一个，则排序完成（类比二叉树的思想）。算法实现步骤首先设置一个截断值（pivot），数组按截断值分为左右两部分。大于等于截断值的数据收集到数组右边，小于截断值的数据收集到数组左边。此时左边部分的每个元素都小于或等于截止值，右边部分的每个元素都大于或等于截止值，称为分区操作。然后，左右数据可以独立排序。对于左边的数组数据，可以取一个边界值将这部分数据分成左右两部分，较小的放在左边，较大的放在右边。右边的数组数据也可以做类似的处理。重复上面的过程，递归排列左边部分的顺序，再递归排列右边部分的顺序。当左右两部分的数据排序完成后，整个数组的排序也就完成了。Python代码实现#quick_sort代码实现defpartition(arr:List[int],low:int,high:int):pivot,j=arr[low],lowforiinrange(low+1,high+1):如果arr[i]<=pivot:j+=1arr[j],arr[i]=arr[i],arr[j]arr[low],arr[j]=arr[j],arr[low]returnjdefquick_sort_between(arr:List[int],low:int,high:int):ifhigh-low<=1:#递归结束条件returnm=partition(arr,low,high)#arr[m]作为划分标准quick_sort_between(arr,low,m-1)quick_sort_between(arr,m+1,high)defquick_sort(arr:List[int]):"""快速排序（就地）:paramarr:tobesortedList:return:快速排序就是就地排序(in-place)"""quick_sort_between(arr,0,len(arr)-1)#testdataif__name__=='__main__':importrandomrandom.seed(54)arr=[random.randint(0,100)for_inrange(10)]print("原始数据：",arr)quick_sort(arr)print("快速排序结果：",arr)#输出原始数据:[17,56,71,38,61,62,48,28,57,42]快速排序结果：[17,28,38,42,48,56,57,61,62,71]动画演示算法分析快速排序的时间复杂度。最理想的情况是，每个获取的元素只是平分整个数组。此时的时间复杂度公式为：$$T\left[n\right]=2T\left[\dfrac{n}{2}\right]\+\f\left(n\right)$$$T\left[n\right]$是划分子数组度数的时间复杂度，$f\left(n\right)$是平分这个数组所花费的时间；然后有：$$\begin{align}T\left[n\right]&=2T\left[\dfrac{n}{2}\right]+n&\text{1strecursion}n=n\\&=2^2T\left[\dfrac{n}{2^2}\right]+2n&\text{第二次递归}n=\dfrac{n}{2}\\&=2^3T\left[\dfrac{n}{2^3}\right]+3n&\text{3rd递归}n=\dfrac{n}{2^2}\\&\cdots\cdots\\&=2^mT\left[\dfrac{n}{2^m}\right]+mn&\text{mthtimeRecursive}n=\dfrac{n}{2^m}\end{align}$$当最后一个bisect不能再被二等分：$$\begin{align}&T\left[\dfrac{n}{2^m}\right]=T\left[1\right]\\\Rightarrow&\frac{n}{2^m}=1\\\Rightarrow&m=\log_2n\\\Rightarrow&T\left[n\right]=n+n\log_2n=O(nlog_2n)\end{align}$$最优quick的时间复杂度排序为：$O\left(n\log_2n\right)$最坏情况即每次取到的元素是数组中的最小值/最大值。这种情况其实就是冒泡排序（每次都排一个元素的顺序）。这样的话，时间复杂度就是冒泡排序的时间复杂度：$$T\left[n\right]=n\left(n-1\right)=n^2+n=O\left(n^2\right)$$快排的最坏时间复杂度是：$O(n^2)$快排的平均时间复杂度也是：$O\left(n\log_2n\right)$空间复杂度首先，就地快速排序使用的空间为$O(1)$，即递归调用是常量级的真实空间消耗，因为每次递归有必要维护一些数据。最优情况是每次均分数组，空间复杂度为：$O(log_2n)$；在稳定排序的过程中，相同的元素不能保证它们的相对位置不变，所以快速排序是一种不稳定的排序。综合分析时间复杂度（平均）时间复杂度（最好）时间复杂度（最差）空间复杂度排序稳定性$O(nlog_2n)$$O(nlog_2n)$$O(n^2)$$O(log_2n)$in-地方不稳定联系我们的个人博客网址：http://www.bling2.cn/Github地址：https://github.com/lb971216008/Use-Python-to-Achieve知乎专栏：https://zhuanlan.zhihu。com/使用-Python-to-Achieve
