手写算法:冒泡排序

未结 0 3470
VIP1 2019年09月20日
悬赏:20积分

对于经典算法,你是否也遇到这样的情形:学时觉得很清楚,可过阵子就忘了?

本系列文章就尝试解决这个问题。

研读那些排序算法,细品它们的名字,其实都很贴切。

比如冒泡排序就很形象,遍历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其实是不需要再比较的。因为上一次已经把未排好序中最大的数据挑走了。

至此,冒泡排序原理和实现已经说完了。

这里总结一下,冒泡排序不需要额外空间,是本地排序,相等元素是不会交换前后顺序,因而也是稳定排序,时间复杂度为O(n^2),适用于少量数据排序,但实际中用得不多。

冒泡排序,要做到能分分钟手写出来,是需要掌握其排序原理的。每次遍历核心是相邻两两比较,一旦内层遍历能写出来,那么整体就很容易写出来,不需要死记硬背的。

希望有所帮助,本文完。

转至 掘金 老姚
链接:https://juejin.im/post/5d6dcd59e51d45620c1c5416

回帖
  • 还没有人回复
本周热议
没有相关数据
layui

微信扫码关注 网盟开源 公众号