周亚博的个人博客

  • 首页
  • 盛夏光年
  • 陪风去荡
  • 布响丸啦
我频繁记录着 因为生活值得
  1. 首页
  2. 陪风去荡
  3. 正文

冒泡排序

2022-08-21 84点热度 0人点赞 0条评论

一、什么是冒泡排序

冒泡排序指的是重复从序列一端开始比较相邻两个数字的大小,根据交换两个数字的位置,直到整个序列排列完成;在这个过程中,数字会像冒泡一样,一个个慢慢从初始端移到末端,所以被称为冒泡排序。

排序过程

冒泡排序

二、代码实现

封装一个升序冒泡

function sort(arr) {
  console.log('对'+arr+'进行升序排列')
  // 轮数
  for (let i = 1; i < arr.length; i++) {
    console.log('_____________________')
    console.log('这是第'+i+'轮:')
    // 次数
    for (let j = 0; j < arr.length - i; j++) {
      // 前一个数大于后一个数进行交换
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
        console.log(arr[j]+'和'+arr[j + 1]+'交换了')
        console.log('结果是'+arr)
      }
    }
  }
  return arr
}

console.log(sort([89, 6, 13, 45, 0]))

运行结果

对89,6,13,45,0进行升序排列
_____________________
这是第1轮:
89和6交换了
结果是6,89,13,45,0
89和13交换了
结果是6,13,89,45,0
89和45交换了
结果是6,13,45,89,0
89和0交换了
结果是6,13,45,0,89
_____________________
这是第2轮:
45和0交换了
结果是6,13,0,45,89
_____________________
这是第3轮:
13和0交换了
结果是6,0,13,45,89
_____________________
这是第4轮:
6和0交换了
结果是0,6,13,45,89
[ 0, 6, 13, 45, 89 ]

假设数组长度为9,则需要循环8轮,因为每轮都会确定一个最值,所以每轮相比上一轮会减少一次两两比较的次数

通过分析可以发现一个规律:

  • 循环的轮数为数组长度减1
  • 每轮比较的次数为数组长度减当前轮数

image-20220821113421700

三、代码优化

可以看出,如果在比较完所有的轮数之前数组已经有序,该方法不会停止,仍然会继续执行,有待优化

function sort(arr) {
  if (arr == null || arr.length < 2) {
    return arr
  }
  // 轮数
  for (var i = 1; i < arr.length; i++) {
    console.log('--------------第'+i+'轮')
    let change = false
    // 次数
    for (let j = 0; j < arr.length - i; j++) {
      // 前一个数大于后一个数进行交换
      if (arr[j] > arr[j + 1]) {
        change = true
        console.log(arr[j] + '<==>' + arr[j + 1])
        let temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
        console.log('结果为'+arr)
      }
    }
    if (!change) {
      break
    }
  }
  console.log('执行了'+i+'轮')
  return arr
}
console.log(sort([7, 8, 1, 3, 5, 4, 2, 9, 6]))  

运行结果

--------------第1轮
8<==>1
结果为7,1,8,3,5,4,2,9,6
8<==>3
结果为7,1,3,8,5,4,2,9,6
8<==>5
结果为7,1,3,5,8,4,2,9,6
8<==>4
结果为7,1,3,5,4,8,2,9,6
8<==>2
结果为7,1,3,5,4,2,8,9,6
9<==>6
结果为7,1,3,5,4,2,8,6,9
--------------第2轮
7<==>1
结果为1,7,3,5,4,2,8,6,9
7<==>3
结果为1,3,7,5,4,2,8,6,9
7<==>5
结果为1,3,5,7,4,2,8,6,9
7<==>4
结果为1,3,5,4,7,2,8,6,9
7<==>2
结果为1,3,5,4,2,7,8,6,9
8<==>6
结果为1,3,5,4,2,7,6,8,9
--------------第3轮
5<==>4
结果为1,3,4,5,2,7,6,8,9
5<==>2
结果为1,3,4,2,5,7,6,8,9
7<==>6
结果为1,3,4,2,5,6,7,8,9
--------------第4轮
4<==>2
结果为1,3,2,4,5,6,7,8,9
--------------第5轮
3<==>2
结果为1,2,3,4,5,6,7,8,9
--------------第6轮
执行了6轮
结果为:[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

数组长度为9,本应该执行8轮,但是第六轮发现没有进行交换,直接退出循环

标签: 冒泡 排序 算法
最后更新:2022-08-21

粥呀Bo

所谓惊喜,就是苦苦等候的兔子来了,后面却跟着狼

点赞
< 上一篇

文章评论

取消回复
目录
  • 一、什么是冒泡排序
  • 二、代码实现
  • 三、代码优化

COPYRIGHT © 2022 zhouyaker.cn. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

陕ICP备2022009272号