前端工程师算法之冒泡排序

原创 Fly丶 教程 前端算法 2382阅读 2018-09-29 22:14:27 举报

前言

对于非科班出身的程序员特别是前端工程师来说,算法的确实是一块心病。买一本算法导论来撸几个月同时还得学一门新语言既难以施行,也极度缺乏性价比。

本人自知才疏学浅,所以科学、全面、规范、严谨一律不管,但我会尽量用通俗的语言和代码让缺乏算法概念的人快速理解算法。

如果你觉得不错,或者发现文章中的错误,或者有更好的建议,欢迎加入前端全栈群交流,866109386。

后续文章中会涉及:常见排序算法、常见搜索算法、树、分治法、动态规划、贪心算法等

冒泡排序

一、原理解析

选择第1个和第2个数字,如果第1个>第2个二者交换位置(假设是升序排列)。之后选择第2个和第3个数字,类似交换处理。一轮下来后,最大的数字会“冒泡”到最后一位。

接下来,忽略已经拍好的数字,对于剩下的数字再来一轮

...

直到所有的数字都排列完成。

二、范例演示

以下表格里,红色表示选中的待排序的数字,粗体表示本轮刚刚排列过的数字,蓝色表示最终排好的数字。

第一轮:
1.选择 10 和 34, 进行比较, 其中 10 < 34, 二者不需要交换
2.选择 34 和 21, 进行比较, 其中 34 > 21, 二者需要交换
3.选择 34 和 47, 进行比较, 其中 34 < 47, 二者需不要交换
4.选择 47 和 3, 进行比较, 其中 47 > 3, 二者需要交换
5....
6.最后 47 交换到末尾

第二轮:

忽略已经排列好的47, 按照刚刚的逻辑再次排序

...

三、实现方式

四、效率测试

下面我们测试排序性能。以下的代码中,randomArr 函数会生成一个随机数组, 数组长度默认是100, 最大值默认值是1000。 console.time 和 console.end 用来记录排序时间。

经测试100次取平均值,得出初步结论:测试数组长度增加10倍,排序时间约增加100倍

复杂度分析

时间复杂度(可以理解为排序的次数)计算: (n-1) + (n-2) + ... + 1 = n*(1 + (n-1))/2,所以时间复杂度为 O(n^2) ,和上面的测试基本一致。

如果你觉得不错,或者发现文章中的错误,或者有更好的建议,欢迎进去前端全栈群,866109386。

评论 ( 0 )
最新评论
暂无评论

赶紧努力消灭 0 回复