JS冒泡排序算法代码及优化方案

冒泡排序基本原理与过程演示

冒泡排序是一种基础的排序算法，其核心逻辑是将数组中的元素按照从大到小或从小到大的顺序进行重新排列。


var array=[9,8,7,6,5,4,3,2,1];

在第一轮比较中，初始数组为8,7,6,5,4,3,2,1,9，经过8次交换后，最大值9被移动至末尾，此时外层循环变量i=0，内层循环变量j=array.length-1-i。

进入第二轮比较，数组状态变为7,6,5,4,3,2,1,8,9，共进行7次交换，外层循环变量i=1，内层循环变量j=array.length-1-i。

第三轮比较时，数组状态为6,5,4,3,2,1,7,8,9，执行6次交换，外层循环变量i=2，内层循环变量j=array.length-1-i。

第四轮比较中，数组状态变为5,4,3,2,1,6,7,8,9，进行5次交换，外层循环变量i=3，内层循环变量j=array.length-1-i。

第五轮比较时，数组状态为4,3,2,1,5,6,7,8,9，执行4次交换，外层循环变量i=4，内层循环变量j=array.length-1-i。

第六轮比较中，数组状态变为3,2,1,4,5,6,7,8,9，进行3次交换，外层循环变量i=5，内层循环变量j=array.length-1-i。

第七轮比较时，数组状态为2,1,3,4,5,6,7,8,9，执行2次交换，外层循环变量i=6，内层循环变量j=array.length-1-i。

第八轮比较中，数组状态变为1,2,3,4,5,6,7,8,9，仅进行1次交换，外层循环变量i=7，内层循环变量j=array.length-1-i。

以下是基础冒泡排序的代码实现示例。

基础代码实现


var temp;
var array=[9,8,7,6,5,4,3,2,1];
//外循环控制轮数
for(var i=0;i<array.length-1;i++){
//内循环控制比较次数
  for(var j=0;j<array.length-1-i;j++){
    if(array[j]>array[j+1]){
      //交换两个变量
      temp=array[j];
      array[j]=array[j+1];
      array[j+1]=temp;
    }
  }
}
console.log(array);

为了提升效率，可以对基础代码进行优化，主要思路是减少不必要的比较轮次。

基于交换标志的优化算法


var temp,bool,m=0;
var array=[9,8,7,6,5,4,3,2,1];
for(var i=0;i<array.length-1;i++){
  //开闭原则中的开关
  bool = true;
  for(var j=0;j<array.length-1-i;j++){
    if(array[j]>array[j+1]){
      //交换两个变量
      temp=array[j];
      array[j]=array[j+1];
      array[j+1]=temp;
      bool=false;//将开关关闭
    }
  }
  //如果内循环中的if没有被执行（开关关闭，执行下面的语句）;
  if(bool){
    break;
  }
  m++;
}
console.log(array+",比较"+m+"轮");

需要注意的是，比较轮数存在最好和最坏情况：最好情况下（数组已有序）为0轮额外比较，最坏情况下（数组完全逆序）为8轮。

接下来介绍另一种常见的冒泡排序算法实现方式。

原型扩展与高级应用


//javascript冒泡排序,直接添加到基础类型的原型上
  //这里用一个javascript语言精粹上的 代码，为基础类型原型添加方法，
  // 因为Array,String他们自身也是构造函数，他们创建对象也是通过new 构造函数行的,因此Array.prototype,String.prototype都指向了Function.prototype
  // Array.method的时候，先访问Array自身函数对象没有method方法，接着Array.prototype仍没有，接着Function.prototype找到了
  Function.prototype.method = function (name, func) {
    if(!this.prototype[name]){ 
      //最好先判断一下是原型中否有这个方法,如果没有再添加
      this.prototype[name] = func;
    }
    return this;
  };
  

  Array.method('bubble',function(){
    // 冒泡算法 总共循环数组的长度次，即len次，每次将最小的放最后
    
    var len = this.length;
    var i = 0, 
      j = 0, 
      tmp =0;

    
    for (i=0 ; i < len; i++) {
      for ( j = 0; (j +1) < len-i; j++) {
        console.log()
        if ( this[j] > this[j+1] ){
          tmp = this[j];
          this[j] = this[j+1];
          this[j+1] = tmp;
        }
      };
    };

    return this;
  });

  alert([21,32,1,31,22,45,68,37,].bubble());

参考前端工程师“西风瘦马”的代码，优化点在于第一层for循环中初始化一个exchange交换标志为false。当内层循环发生交换时，将该标志设为true。在第二层for循环结束后，判断该标志：若为false，说明从前往后对比没有发生交换，数组已有序，此时使用break跳出外层for循环。

其他优化实现方案


//需要排序的数组
var list = Array(23, 45, 18, 37, 92, 13, 24);
//数组长度
var n = list.length;
//交换顺序的临时变量
var tmp;//
//交换标志
var exchange;
//最多做n-1趟排序
for (var time = 0; time <n - 1; time ++) {
  exchange = false;
  for (var i = n - 1; i> time; i–-) {
    if (list[i] <list[i - 1]) {
      exchange = true;
      tmp = list[i - 1];
      list[i - 1] = list[i];
      list[i] = tmp;
    }
  }
  //若本趟排序未发生交换，提前终止算法
  if (!exchange) {
    break;
  }
}
alert(‘数组排序后为：' + list + ‘,n共排了' + time + ‘趟');

此外，还整理了一位网友提供的算法实现，其逻辑同样具备优化特性，供读者参考。


function BubbleSort(array) {  
 var length = array.length;  
 var temp; 
 var isSort=false;  
 for(var i = 1; i < length; i++) {  
  isSort = false;  
  
  for(var j = 0; j < length - i; j++) {  
   if(array[j] > array[j+1]) {  
    //交换  
    temp = array[j];  
    array[j] = array[j+1];  
    array[j+1] = temp;      
    isSort = true;  
   }  
  }  
  if(!isSort) break; //如果没有发生交换，则退出循环  
  }  
}
  var array =[10,-3,5,34,-34,5,0,9]; 
  BubbleSort(array);  
  for(var i=0;i< array.length;i++) {  
   document.write(array[i]+ " ");  
  }

以上就是关于JavaScript冒泡排序及其优化的总结，希望这些内容能对小伙伴们学习相关算法有所帮助。

JavaScript冒泡排序实现与性能优化详解

冒泡排序基本原理与过程演示

基础代码实现

基于交换标志的优化算法

原型扩展与高级应用

其他优化实现方案

实用工具推荐