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

回答问题并写出推导过程:

对50个整数进行快速排序需进行关键字间比较次数可能达到的最大值和最小值各为多少?

提示

当初始记录有序或基本有序时,快速排序将蜕化为起泡排序,关键字有序时比较次数最大。

若每次都分割成长度相等或仅相差1的子序列时,比较次数最少。而每次划分所进行比较的次数是该子序列中关键字个数减1,因此通过快速排序的判定树可求出总的比较次数。

答案

最大比较次数:在关键字有序的情况下,为

49+48+...+1=1225

最小比较次数:判定树如下图所示(树中结点,所示数字为此子序列所含关键字个数)

判定树 50 快速排序

最少比较次数:49+47+43+35+19=193.

笔记