分别继续对新的待排子序列继续执行步骤1~6排序,直到所有元素都排列在相应位置上为止....,即每趟选择key时都恰好选择到数组的中间值时(第n层可以确定
个数字位置),快排的时间复杂度如下图完全(满)二叉树:
该树每层需要遍历一遍数组,时间复杂度为n,而树高为
,因此最优状态下快排的时间复杂度仅为...而最坏情况下,即每趟选择key时都恰好选择到数组最大或最小的值时(即每一层都只能确定一个数字位置),快排的时间复杂度如下单支树:
该树每层遍历一遍数组,时间复杂度为n,而树高也为n,因此最坏状态下快排的时间复杂度为...快排的递归展开思路类似于二叉树,因此它们拥有同样的弊病,就是越靠近树的底部,空递归的情况就越多,并且空递归的规模量非常大,拿下面这颗树来举例:
我们递归遍历该树,发现空递归(紫色)访问次数竟然和总有效访问次数...(绿色)是相同的.而对于快排来说,这样的空递归不仅浪费时间,而且是没有任何实际意义的.