回顾冒泡算法

刚开始学编程的时候就学了冒泡,所以一直觉的是很简单的东西,但你真的能随手写出来吗?真的还记得原理吗?

第一种实现

这是根据核心思想写出来的,后来和书上的一对,写法不同,但是原理和结果是一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
let arr = [1, 3, 6, 4, 5, 2, 4, 8, 9, 6, 7, 8, 1, 4];
let l = arr.length - 1;
let count = 0;
for (let i = 0; i < l; i++) {
for (let h = i + 1; h <= l; h++) {
count++;
let tmp = arr[i];
if (arr[i] < arr[h]) {
arr[i] = arr[h];
arr[h] = tmp;
}
}
}
console.log(arr.toString());
console.log(count);

结果

9,8,8,7,6,6,5,4,4,4,3,2,1,1
91 ###原理
实现思想就是用依次用每个位置的数和后面的数进行对比和互换。
比如降序排列,第一个位置时,用 1 和后面的各个数进行对比,如果比 1 大则互换两个位置的数,直到最后。

第二种

这是书上的方法也是冒泡的真正的原理。

就是相邻的两个元素比较,还以降序为例,如果后面的比前面的大,则互换他们的顺序,比如第一个和第二个对比,然后第二个和第三对比,依次类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let arr = [1, 3, 6, 4, 5, 2, 4, 8, 9, 6, 7, 8, 1, 4];
let l = arr.length - 1;
let count = 0;
for (let i = 0; i < l; i++) {
for (let h = 0; h < l - i; h++) {
count++;
let tmp = arr[h];
if (arr[h] < arr[h + 1]) {
arr[h] = arr[h + 1];
arr[h + 1] = tmp;
}
}
}

console.log(arr.toString());
console.log(count);

结果

9,8,8,7,6,6,5,4,4,4,3,2,1,1
91

总结

两种方式结果一样,并且循环的次数也一样,但是如果面试的话还是推荐第二种,保险,哈哈
两种原理其实是一样的,第二个本质也是把数据一个一个从后往前放,和第一种放的顺序相反,所以本质一样。

时间复杂度

若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数)和记录移动次数)均达到最小值:),
所以,冒泡排序最好的时间复杂度为
若初始文件是反序的,需要进行)趟排序。每趟排序要进行)次关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:

时间复杂度可以忽略掉前面的系数和减去的具体数值,因为在指数级前面这些可以忽略不计。

冒泡排序的最坏时间复杂度为
综上,因此冒泡排序总的平均时间复杂度为

这是一个非常高的时间复杂度。冒泡排序早在 1956 年就有人开始研究,之后有很多人都尝试过 对冒泡排序进行改进,但结果却令人失望。如 Donald E. Knuth(中文名为高德纳,1974 年 图灵奖获得者)所说:“冒泡排序除了它迷人的名字和导致了某些有趣的理论问题这一事实 之外,似乎没有什么值得推荐的。”

文章作者: wenmu
文章链接: http://blog.wangpengpeng.site/2020/02/28/%E5%9B%9E%E9%A1%BE%E5%86%92%E6%B3%A1%E7%AE%97%E6%B3%95/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 温木的博客
微信打赏