您好,欢迎来到花图问答。
搜索
您的当前位置:首页面试——快速排序总结

面试——快速排序总结

来源:花图问答

优点:
增大了记录的比较和移动的距离,将关键字较大的记录从前面直接移动到后面,关键字较少的从后面直接移动到前面,减少了总的比较次数与移动交换次数

缺点:
最坏复杂度为O(n2)
不稳定

时间复杂度:
最好:O(nlog2n)
平均:O(nlog2n)
最坏:O(n2)

最好情况:
每次划分都把当前数组划分为长度相等的两个子数组
最坏情况:
每次划分都只让数组中的元素少1,此时复杂度为O(n2)

空间复杂度:
递归log2n次,每次消耗栈空间为常数,故空间复杂度为O(log2n)

稳定性:
当中枢元素与其他元素交换时可能会把前面元素的稳定性打乱,所以是不稳定的

优化:
1、随机下标或三数取中作为枢轴元素
2、划分的数组变小到一定程度时,改用插入排序

Copyright © 2019- huatuowenda.com 版权所有 湘ICP备2023022495号-1

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务