冒泡排序与选择排序的区别
核心逻辑 | 逐轮 “冒泡”:相邻元素两两比较,将 最大(小)元素逐步交换到末尾 | 逐轮 “选择”:先遍历找到本轮 最小(大)元素的位置 ,仅一次交换到目标位置 |
交换次数 | 最坏情况 O(n2) (完全逆序时,每轮多次交换) | 固定 O(n) (每轮仅 1 次交换,共 n-1 轮) |
比较次数 | 最坏 / 平均 O(n2) (可优化:某轮无交换则提前终止) | 固定 O(n2) (无论是否有序,都需遍历找最小元素) |
数据移动特性 | 交换频繁,每次交换涉及 2 次数据移动(如 a↔b) | 交换极少,仅最终一次移动目标元素 |
优化空间 | 可优化(提前终止、记录最后交换位置减少遍历范围) | 优化空间小(仅可双路选择:同时找最大 + 最小) |
实际执行效率 | 通常比选择排序慢 | 通常比冒泡排序快 |