冒泡排序法在最坏的情况下的比较次数是n(n-1)/2,快速排序呢它不是据说是冒泡排序的优化版么…

问题描述:

冒泡排序法在最坏的情况下的比较次数是n(n-1)/2,快速排序呢
它不是据说是冒泡排序的优化版么…

快速排序的时间复杂度
最坏为n*(n-1)/2
最好为n*logn
不同的结果和用于划分的key大小有关:
最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候;
最好情况是每次划分过程产生的区间大小都为n/2 .
数据结构里说的很清楚.百度百科里也有说明的.