前端开发必会的JS算法之冒泡排序
很多做前端开发的小伙伴都有这样的情况,对于 JS 的一些经典算法,在学时都觉得很清楚,当时也确实学会了,小手啪啪不在话下,然后过一阵子就会遗忘了,再让他动手写就显得很生疏,甚至哪儿学的还到哪儿去。所以,本系列文章就尝试解决这个问题。
比如冒泡排序就很形象,遍历 n 次,每次循环相邻元素两两比较,把其中大的元素往后放。例如:
上图演示了冒泡过程的第一次循环。其中,最大的元素 5 就像气泡一样逐步上升到最后一位。
通过上图的演示过程我再用代码翻译出来:
let array = [5, 4, 3, 2, 1] for (let i = 0; i < array.length - 1; i++) { if (array[i] > array[i+1]) { swap(array, i, i+1) } } console.log(array) // [4, 3, 2, 1, 5]
其中 swap 函数封装了两个元素如何交换:
function swap(array, i, j) { [array[i], array[j]] = [array[j], array[i]] }
第一次遍历会把最大的元素放到倒数第一个位置上,第二次遍历会把第 2 大的元素放倒数第二个位置上。
其余次数,以此类推。此时,我们也很容易把这 n 次遍历写出来:
for (let j = 0; j < array.length; j++) { for (let i = 0; i < array.length - 1; i++) { if (array[i] > array[i+1]) { swap(array, i, i+1) } } }
上述代码,还有优化的空间,比如第 2 次遍历时,元素 4 和 5 其实是不需要再比较的。因为上一次已经把未排好序中最大的数据挑走了。查看完整代码:
const utils = { swap(array, i, j) { [array[i], array[j]] = [array[j], array[i]] }, randomNum() { return Math.floor(Math.random() * 100) }, randomArray() { return Array.from(Array(this.randomNum()), _ => this.randomNum()) } } function bubbleSort(array) { const length = array.length for (let i = 0; i < length; i++) { for (let j = 0; j < length -1 - i; j++) { if (array[j] > array[j + 1]) { utils.swap(array, j, j + 1) } } } return array } const array = bubbleSort(utils.randomArray()) console.log(array)
至此,冒泡排序原理和实现已经说完了。
这里总结一下,冒泡排序不需要额外空间,是本地排序,相等元素是不会交换前后顺序,因而也是稳定排序,时间复杂度为 O(n^2),适用于少量数据排序,但实际中用得不多。
冒泡排序,要做到能分分钟手写出来,是需要掌握其排序原理的。每次遍历核心是相邻两两比较,一旦内层遍历能写出来,那么整体就很容易写出来,不需要死记硬背的。
以上就是前端开发必会的 JS 算法之冒泡排序的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持码云笔记!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。
码云笔记 » 前端开发必会的JS算法之冒泡排序
码云笔记 » 前端开发必会的JS算法之冒泡排序