当数据量很大时,使用这两种优秀的算法能大幅度提高效率
时间复杂度
最好情况
最好情况是当数组完全无序时,每个基准值都选在了中间位置 这样递归次数是最少的,类似二分法 时间复杂度为 1.39NlgN
平均情况
当数组完全无序时,每个基准值按照正态分布落在整个数组中,那么 算法的平均时间复杂度为 2NlgN
最坏情况
最坏情况分两种 , 第一种 是数组有序,那么每一刀都切在了边缘 其时间复杂度近似为 N*N
第二种 是数组完全无序,但偏偏每一刀都切在了边缘上,其时间复杂度一样为 N*N跟冒泡插入一样都是两层循环
空间复杂度O(1) 使用的额外空间与问题规模无关
那么快排的性能如何呢?
快排的平均情况之比最好情况 多39% 那么只损失了11%的性能,就能高效解决大部分场景的问题,足以说明这个算法的全面性