JS数组--冒泡排序的两种实现

概念:

1、时间复杂度:一个算法执行所耗费的时间

2、空间复杂度:运行完一个程序所需内存的大小

3、稳定指:如果a=b,a在b的前面,排序后a仍然在b的前面

4、不稳定指:如果a=b,a在b的前面,排序后可能会交换位置

冒泡排序原理:

用一组嵌套的for循环,外循环会遍历数组的每一项,

内循环依次比较相邻的两个值,如果后面的比前面的小,则将小的元素排到前面。

依照这个规则进行多次并且递减的迭代,直到顺序正确。

冒泡排序法的

1、平均时间复杂度:O(n*n)【最好情况O(n)、最差情况O(n*n)】

2、空间复杂度O(1)

3、稳定性:稳定

实现方法一:

当i=0的时候,里面的循环完整执行,从j=0执行到j=6,这也就是第一遍排序,结果是将最大的数排到了最后,这一遍循环结束后的结果应该是[8,15,88,55,76,21,39,94]

当i=1的时候,里面的循环再次完整执行,由于最大的数已经在最后了,没有必要去比较数组的最后两项,这也是j

即每次将剩下数组里面最大的一个数排到最后面,当第一个循环执行到最后的时候,也就是i=6,此时,j=0,只需要比较数组的第一和第二项,比较完毕,返回。

实现方法二:

外层的for循环采用递减的方式,当outer=2的时候只有两个元素需要比较了,则执行最后一次比较。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 14,357评论 0 33
  • 1、https://zhuanlan.zhihu.com/p/20206932?columnSlug=datama...
    Babyzpj阅读 1,301评论 0 0
  • 今天观看了浪琴赞助的中国马术巡回赛,于是回顾一下马术历史。 马术运动源远流长。关于赛马,在古希腊第三十三届奥运会就...
    江山笑烟雨遥阅读 4,650评论 0 1
  • 把烟都上缴。 圣经里可以赐予玫瑰。 如若这样。 那把灵魂抵出, 换与我新的以色列。 可否。 ​​​
    惟西风恨阅读 1,634评论 2 3

友情链接更多精彩内容