千锋教育web前端高频面试题视频教程，kerwin大话前端面试秘籍（附答案）

冒泡排序

算法描述

1. 比较相邻元素，如果前一个比后一个大，那么就交换位置。
2. 对每一个相邻的元素进行相同的操作，从开始到最后，最终排到最后的是最大的元素。
3. 因为已经确定最后的元素是最大的，所以去除最后一个元素，对前面的所有元素再进行上述操作。
4. 循环1~3

算法实现

算法优化

问题：多余的比较

解决：记录每一趟最后一次交换的位置。

问题：每一趟的结果只有一个最大值效率低

解决：每一趟既找最大值也找最小值

耗时对比：

第二种优化效率最好。

算法分析

• 最佳情况：最终顺序与初始顺序相同。 if语句比较n-1次。 时间复杂度：T(n) = O(n)
• 最差情况：最终顺序与初始顺序相反。 if语句比较次数：n-1+n-2+……+1 时间复杂度：T(n) = n(n-1)/2 = O(n²)
• 平均复杂度：T(n) = O(n²)