2021-03-11 21:27
标签：复杂 写法 大数 大小 i++ 交换 break 进入 数组
冒泡排序 标签：复杂 写法 大数 大小 i++ 交换 break 进入 数组 原文地址：https://www.cnblogs.com/yxks-666/p/14122483.html
// 空间复杂度：O(1)
// 时间复杂度：是一个算法执行所耗费的时间
// 空间复杂度：运行完一个程序所需要的内存大小
// 稳定性：如果a=b,a在b的前面，排序后a仍然在b的前面
// 不稳定性：如果a=b，a在b的前面，排序后a和b可能交换位置
//基础冒泡写法---时间复杂度O(n*n)
var arr = [1, 5, 7, 3];
//外层循环次数，遍历数组
for (var i = 0; i
//里层循环找到最大的数，进行一次完整排序
//根据外层for循环的i,逐渐减少内层for循环的次数
for (var j = 0; j
if (arr[j] > arr[j + 1]) {
var temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
console.log(arr);
//优化冒泡写法----时间复杂度O(n)
var arr1 = [2, 9, 3, 6];
function optimization(arr1) {
for (var i = 0; i
//这里设置一个标志位
var sign = true;
for (var j = 0; j
//当有比较时，进入if进行比较，当有些数组不用太多次比较时，如[1,2,4,3]
//只比较一次就可以跳出循环,不用浪费时间进行全部比较
if (arr1[j] > arr1[j + 1]) {
var temp = arr1[j];
arr1[j] = arr1[j + 1];
arr1[j + 1] = temp;
sign = false;
}
}
if (sign) {
break;
}
}
return arr1;
}
optimization(arr1);
// 总结：
// 外层循环控制次数，内层循环寻找最大数排序，设置一个标志位，减少不必要的循环