概念
冒泡排序只会操作相邻的两个数据，每次冒泡操作操作都会对下一个元素进行比较，看是否满足大小关系要求，如果不满足就让它两互换，一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 次排序工作；
- 外层迭代：将 最大的 元素冒泡的最后面，这样需要迭代的次数正好是 数组的长度；
- 里层迭代：两两对比，如果前一个元素大于后一个元素，则需要交换位置，每轮的循环次数正好是
数组的长度 - 外层循环的次数；
图解
没有优化的冒泡
代码实现
let bubbleSort = function (nums) {
// 冒泡次数，每一次冒泡，都会把最大的放到后面
for (let i = 0; i < nums.length; i++) {
// 两两对比，如果前一个元素大于后一个元素，则需要交换位置，每轮的循环次数正好是 数组的长度 - 外层循环的次数(已经排好了，无需再次排序)
for (let j = 0; j < nums.length - i; j++) {
if (nums[j] > nums[j + 1]) {
[nums[j], nums[j + 1]] = [nums[j + 1], nums[j]]
}
}
}
return nums;
}
复杂度
-
时间复杂度：
O(N^2)- n 表示数组的长度
- 循环次数
第 i 轮 比较次数 第 1 轮 与 N−1 个数比较 第 2 轮 与 N−2 个数比较 第 3 轮 与 N−3 个数比较 … … 第 N 轮 与 1 个数比较 N + (N−1) + (N−2) + ... + 1 = (N - 1 + 1)N/2 = N * N / 2，则时间复杂度为O(N^2)；
-
空间复杂度：
O(1)
优化后的冒泡
代码实现
let bubbleSort = function (nums) {
let isSorted = true; // 标记数组是否是已经排好序的
// 冒泡次数，每一次冒泡，都会把最大的放到后面
for (let i = 0; i < nums.length; i++) {
// 两两对比，如果前一个元素大于后一个元素，则需要交换位置，每轮的循环次数正好是 数组的长度 - 外层循环的次数(已经排好了，无需再次排序)
for (let j = 0; j < nums.length - i; j++) {
if (nums[j] > nums[j + 1]) {
[nums[j], nums[j + 1]] = [nums[j + 1], nums[j]]
isSorted = false; // 一次也没有过交换，说明数组是单调递增的
}
}
if (isSorted) {
break;
}
}
return nums;
}
复杂度
-
时间复杂度：
- 最坏时间复杂度
O(N^2) - 最好时间复杂度
O(N)
- 最坏时间复杂度
-
空间复杂度：
O(1)
打赏作者
您的打赏是我前进的动力
微信
支付宝
👉排序算法的评价指标👈
上一篇
评论
