1999年清华大学 · 快速排序 · 考研题

快速排序的最大递归深度是,最小递归深度是

答案

n;[log2n]+1

分析

若每趟排序后,枢轴位置均偏向于序列的一端,则为最坏情况,栈的最大深度为n。

若每趟排序都将记录序列均匀地分割或长度相近的两个子列,遇为最好情况,栈最大深度为[log2n]+1。

【扩展:改进快速排序算法】在一趟排序后比较分割所得两部分的长度,先对长度短的子序列进行快速排序,则栈的最大深度可降为O(log2n)。

笔记