在快速排序中,如果选择第一个元素作为分区的枢轴元素,那么
快速排序会显示其最差的投射复杂度 - 在这种情况下为O(n ^ 2).
更确切地说,当要排序的输入按降序或递增顺序(如果第一个elemnet是枢轴元素)时,观察到快速排序的最坏情况复杂度为O(n ^ 2).
这种最坏情况性能的原因是,在分区之后,一个分区的大小为1,另一个分区的大小为n-1
所以,快速排序'n'个元素的
时间T(n)= 所需的时间分区'n'个元素O(n)+快速排序'n-1'个元素的时间T(n-1)
所以,T(n)= T(n-1)+ O(n)
=> T(n )= O(n ^ 2)