Excel如何实现快速排序( 二 )

最好情况：每一次选取的“基准”都是序列中最中间的一个数（是中位数，而不是位置上的中间），那么每次都把当前序列划分成了长度相等的两个子序列。这时候，第一次就有n/2、n/2两个子序列，第二次就有n/4、n/4、n/4、n/4四个子序列，依此类推，n个数一共需要logn次才能排序完成（2^x=n，x=logn），然后每次都是n的复杂度，时间复杂度为O（n logn）
空间复杂度最坏情况：需要进行n‐1 次递归调用，其空间复杂度为 O（n）
最好情况：需要logn次递归调用，其空间复杂度为O（logn）
算法的稳定性快速排序是一种不稳定排序算法
例如：现有序列为[1, 0, 1, 3]，“基准”数字选择为第二个1
在第一轮比较之后，变成了[0, 1, 1, 3]，左序列为[0]，右序列为[1, 3]（右序列的1是此前的第一个1）
不难发现，原序列的两个1的先后顺序被破坏了，改变了先后顺序，自然就是“不稳定”的排序算法了
关于O在此前的“冒泡排序法”一文当中，我们详细讲解过O是什么，在此就不多说了，直接上图吧

文章插图