冒泡排序与选择排序的区别

核心逻辑

逐轮 “冒泡”:相邻元素两两比较,将

最大(小)元素逐步交换到末尾

逐轮 “选择”:先遍历找到本轮

最小(大)元素的位置

,仅一次交换到目标位置

交换次数

最坏情况

O(n2)

(完全逆序时,每轮多次交换)

固定

O(n)

(每轮仅 1 次交换,共 n-1 轮)

比较次数

最坏 / 平均

O(n2)

(可优化:某轮无交换则提前终止)

固定

O(n2)

(无论是否有序,都需遍历找最小元素)

数据移动特性

交换频繁,每次交换涉及 2 次数据移动(如 a↔b)

交换极少,仅最终一次移动目标元素

优化空间

可优化(提前终止、记录最后交换位置减少遍历范围)

优化空间小(仅可双路选择:同时找最大 + 最小)

实际执行效率

通常比选择排序慢

通常比冒泡排序快

全部评论

相关推荐

不愿透露姓名的神秘牛友
12-24 16:55
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务