JS实现冒泡排序及优化

实现原理

数组中有n个数,从第一个数开始,逐个比较相邻的两数,如果前面的大于后面的,交换位置,将比较大的数往后排。

实现

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {  // 比较轮数
    for (let j = 0; j < arr.length - 1 - i; j++) {  // 每轮比较次数,由于每次最后一个都是最大值,每轮少比较i次 
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
  }
  return arr;
}

优化1: len

let len = arr.length  // 将len取出,避免每轮循环都去获取
for (let i = 0; i < len - 1; i++) {
  for (let j = 0; j < len - 1 - i; j++) {
    // ...
  }
}

优化2: 数值边缘检测

for (let i = 0; i < len - 1; i++) {
  for (let j = 0; j < len - 1 - i; j++) {
    if(arr[j] > Number.MAX_VALUE || arr[j] < -Number.MAX_VALUE) return "数值溢出!"
  }
}

优化3: 本轮没有交换的标志位

形如[1,2,3,4,6,5]这种数组,只需比较一轮就已经排好了。
所以我们加一个标志位,每次外层循环开始前将标志位置为true,内层循环过程中,出现两数交换时,置为false。
如果内层循环没有任何两数进行交换,标志位为true,表示排序完成。 这样我们就可以减少不必要的排序,提高性能

function bubbleSort(arr) {
  let done  // 已经完成的标志位
  let len = arr.length
  for (let i = 0; i < len - 1; i++) {
    done = true
    for (let j = 0; j < len - 1 - i; j++) {
      if(arr[j] > Number.MAX_VALUE || arr[j] < -Number.MAX_VALUE) return "数值溢出!"
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
        done = false
      }
    }
    if(done){
      return arr
    }
  }
  return arr;
}
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容