1. 概述
本文将使用 Kotlin 实现冒泡排序（Bubble Sort）算法。作为最简单的排序算法之一，它的核心思想是：✅ 对给定列表进行多次遍历，逐个比较相邻元素，若顺序错误则交换位置，直到整个列表有序为止。
由于实现简单、逻辑直观，冒泡排序非常适合用于教学场景或小规模数据排序。但在生产环境中基本不会使用——性能太差，后文会详细分析。
2. 冒泡排序的执行步骤
我们来一步步拆解冒泡排序的过程：
- 从一个无序数组开始
- 比较第一个和第二个元素，如果前者大于后者，则交换
- 移动到下一组相邻元素，继续比较并按需交换
- 一轮完整遍历结束后，最大值会“浮”到数组末尾
- 接着对前
n-1个元素重复上述过程（最后一个已确定为最大） - 直到某一轮不再发生任何交换，说明排序完成
这个“逐步上浮”的过程就像气泡从水底冒出来一样，因此得名“冒泡排序”。
3. 冒泡排序的 Kotlin 实现
以下是标准升序版本的实现：
fun bubbleSort(arr: IntArray) {
val n = arr.size
for (i in 0 until n - 1) {
for (j in 0 until n - i - 1) {
if (arr[j] > arr[j + 1]) {
// Swap the elements
val temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
}
📌 解读一下关键点：
- 外层循环控制排序轮数，共
n-1轮 - 内层循环每次减少一次比较（因为每轮都会确定一个最大值的位置）
n - i - 1是优化后的边界条件，避免无效比较
测试用例如下：
val arr = intArrayOf(64, 34, 25, 12, 22, 11, 90)
val expected = intArrayOf(11, 12, 22, 25, 34, 64, 90)
bubbleSort(arr)
assertArrayEquals(expected, arr)
3.1 降序排列实现
只需要调整判断条件即可实现降序排序：
fun bubbleSortDescending(arr: IntArray) {
val n = arr.size
for (i in 0 until n - 1) {
for (j in 0 until n - i - 1) {
if (arr[j] < arr[j + 1]) { // 改为小于号
val temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
}
⚠️ 这里踩过坑的同学应该知道：符号写反了会导致结果完全颠倒但不易察觉，建议加上单元测试验证逻辑正确性。
4. 算法复杂度分析
虽然冒泡排序容易理解，但从工程角度看它存在明显短板。
时间复杂度
| 场景 | 复杂度 |
|---|---|
| 最好情况（已排序） | O(n) ✅ |
| 平均情况 | O(n²) ❌ |
| 最坏情况（逆序） | O(n²) ❌ |
🔗 更详细的复杂度推导可参考：Bubble Sort Time Complexity
尽管理论上最好情况能达到 O(n)，但前提是加入提前终止机制（即某轮无交换则退出），而上面的基础版本并没有做这种优化。
空间复杂度
- ✅ O(1) —— 原地排序，仅使用常量级额外空间
- 不依赖辅助数组或其他结构，适合内存受限环境
是否自适应？
❌ 否。即使输入数组已经部分有序，传统冒泡排序仍会执行全部比较操作，无法利用已有顺序提升效率。
实际应用场景
- ✅ 教学演示：帮助初学者理解排序本质
- ✅ 小数据集（< 50 个元素）且对性能无要求的场景
- ❌ 生产系统中应避免使用，推荐改用
Collections.sort()或底层基于 Timsort 的实现
4.1 冒泡排序的主要缺点
- ⚠️ 时间复杂度高：O(n²) 在大数据量下性能急剧下降
- ⚠️ 非稳定进化：相比快速排序、归并排序等高级算法毫无优势
- ⚠️ 实际应用价值低：现代语言标准库都提供了更优的排序方案
一句话总结：能跑，但别真用。
5. 总结
本文介绍了如何在 Kotlin 中实现冒泡排序，包括升序与降序版本，并深入分析了其时间/空间复杂度及适用场景。
虽然冒泡排序因其简洁性成为入门经典，但在真实项目中应优先选择更高效的替代方案，如快速排序、堆排序或 JVM 自带的排序工具类。
完整代码示例已上传至 GitHub：