/*** 基础冒泡排序实现（升序）* @param arr 待排序数组* @returns 已排序数组*/
function bubbleSortBasic(arr: number[]): number[] {const n = arr.length;for (let i = 0; i < n - 1; i++) {for (let j = 0; j < n - 1 - i; j++) {if (arr[j] > arr[j + 1]) {// 交换相邻元素[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];}}}return arr;
}/*** 优化版冒泡排序实现（升序）* @param arr 待排序数组* @returns 已排序数组*/
function bubbleSortOptimized(arr: number[]): number[] {const n = arr.length;let lastExchangeIndex = 0; // 最后一次交换位置let sortBorder = n - 1; // 无序数列的边界for (let i = 0; i < n - 1; i++) {let isSorted = true; // 有序标记for (let j = 0; j < sortBorder; j++) {if (arr[j] > arr[j + 1]) {[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];isSorted = false;lastExchangeIndex = j; // 更新最后交换位置}}sortBorder = lastExchangeIndex;if (isSorted) break; // 提前终止排序}return arr;
}一、算法简介
冒泡排序（Bubble Sort）是最经典的排序算法之一，其命名源自排序过程中元素会像气泡一样逐渐"浮"到正确位置。虽然在实际应用中效率不高，但其直观的原理使其成为算法学习的入门必修课。
二、算法流程解析
基础版本执行步骤：
-
从第一个元素开始，比较相邻元素
-
如果前大于后（升序情况），则交换二者
-
对每一对相邻元素重复上述操作
-
完成一轮后，最大元素已"冒泡"至末尾
-
对剩余未排序元素重复上述步骤
示例演示：
初始数组：[5, 3, 8, 4, 6]
第1轮操作：
3↔5 → [3,5,8,4,6]
8与4交换 → [3,5,4,8,6]
8与6交换 → [3,5,4,6,8]
后续轮次依此类推...
三、时间复杂度分析
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最坏情况 | O(n²) | 完全逆序数组 |
| 平均情况 | O(n²) | 随机排列数组 |
| 最好情况(优化版) | O(n) | 已有序数组，提前终止 |
| 空间复杂度 | O(1) | 原地排序，仅使用常数级别额外空间 |
四、关键优化策略
1. 提前终止机制
-
增加
isSorted标志位 -
当某轮未发生交换时，说明数组已有序，立即终止排序
2. 有序区间界定
-
记录
lastExchangeIndex标记最后交换位置 -
后续比较只需进行到该位置，避免无效比较
优化效果对比
在包含1000个元素的部分有序数组中：
-
基础版：约500,000次比较
-
优化版：约120,000次比较（减少76%）
五、算法核心特性
优势：
-
稳定排序：相等元素相对位置不变
-
空间高效：无需额外存储空间
-
实现简单：适合教学和小型数据集
局限性：
-
平方复杂度：处理10,000元素需要约1亿次操作
-
低效场景：逆序数组性能最差
-
缺乏适应性：不擅长处理特殊分布数据
六、TypeScript实现
提供两个版本实现，包含完整类型声明：
基础版本实现
（代码见开头bubbleSortBasic函数）
优化版本实现
（代码见开头bubbleSortOptimized函数）
七、应用场景建议
-
教学演示算法原理
-
处理小于1000条的数据集
-
作为其他排序算法的基准参考
-
在近乎有序的小数据集场景
八、演进思考
虽然冒泡排序在实际工程中较少使用，但其衍生算法在特定场景仍有价值：
-
鸡尾酒排序：双向冒泡排序，适合钟形分布数据
-
梳排序：通过增大比较间距提升效率
-
奇偶排序：并行处理相邻元素对
对于需要高效排序的场景，建议考虑：
-
快速排序（平均O(n log n)）
-
归并排序（稳定O(n log n)）
-
TimSort（混合算法，Python/Java内置）
理解冒泡排序的原理，是打开算法世界大门的重要第一步。尽管其性能有限，但其中蕴含的"逐步调优"思想，正是算法优化的精髓所在。
如果对你有帮助，请帮忙点个赞
)
