大门|大门-CS-2014-（第1组）|问题23

让P成为一个快速排序程序，使用第一个元素作为轴心按升序对数字进行排序。设t1和t2分别是P对输入{1,2,3,4,5}和{4,1,5,3,2}进行比较的次数。以下哪一项适用？ （A） t1=5 （B） t1 （C） t1>t2 （D） t1=t2 答复: （C） 说明： 选择第一个元素或最后一个元素作为轴心时， 快速排序 的最坏情况发生在已排序的数组中。

在快速排序的每个步骤中，数字都会按照以下循环进行划分。

T（n）=T（n-1）+O（n）

这个问题的小测验