JavaScript实现经典排序算法之冒泡排序

站长资源 2024/11/28 佚名

77 1538 77

DDR爱好者之家 Design By 杰米

冒泡排序可谓是最经典的排序算法了，它是基于比较的排序算法，时间复杂度为O(n^2)，其优点是实现简单，n较小时性能较好。

1）算法原理
相邻的数据进行两两比较，小数放在前面，大数放在后面，这样一趟下来，最小的数就被排在了第一位，第二趟也是如此，如此类推，直到所有的数据排序完成。

2）算法描述
       <1>比较相邻的元素。如果第一个比第二个大，就交换它们两个；
       <2>对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
       <3>针对所有的元素重复以上的步骤，除了最后一个；
       <4>重复步骤1~3，直到排序完成。
3）javascript代码实现

function bubbleSort(arr){  
  var len = arr.length;  
  for (var i = 0; i < len; i++) {  
    for(var j = 0; j < len - i -1; j++){  
      if(arr[j]>arr[j+1]){ //相邻元素进行对比  
        var temp = arr[j+1];//交换元素  
        arr[j+1] = arr[j];  
        arr[j] = temp;  
      }  
    }  
  }  
  return arr;//返回数组  
}  
  
var arr=[1,45,37,5,48,15,37,26,29,2,46,4,17,50,52];//调用排序算法  
console.log(bubbleSort(arr));//控制台输出结果

这个算法是最基本的实现方法，接着进行改进这个算法，通过设置一个标志性的变量position，用于记录每趟排序中最后一次进行交换的位置。因为position位置之后的记录都已经排序好了，所以进行下一趟排序时只需要扫描到position的位置就好。
改进之后的算法如下：

function bubbleSort2(arr){  
  var i = arr.length -1;//开始时，扫描的最后位置  
  while(i>0){  
    var position = 0;//标志性变量，表示当前排序中交换的位置  
    for(var j = 0; j < i; j ++){  
      if(arr[j]>arr[j+1]){  
        position = j;  
        var temp = arr[j+1];  
        arr[j+1] = arr[j];  
        arr[j] = temp;  
      }  
    }  
    i = position;  
  }  
  return arr;  
}  
  
var arr=[1,45,37,5,48,15,37,26,29,2,46,4,17,50,52];  
console.log(bubbleSort2(arr));

传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。
改进之后的算法如下：

function bubbleSort3(arr){  
  var low = 0;  
  var high = arr.length-1;  
  var temp;  
  while(low < high){//找到最大值  
    for(var j = low ; j < high ; j++){  
      if (arr[j]> arr[j+1]) {       
        temp = arr[j+1];  
        arr[j+1] = arr[j];  
        arr[j] = temp;  
       }  
    }  
    --high;//修改high值，向前移一位  
  }  
  while(low > high){//找到最小值  
    for(var j = high ;j > low; j--){  
      if (arr[j]> arr[j+1]) {       
        temp = arr[j+1];  
        arr[j+1] = arr[j];  
        arr[j] = temp;  
       }  
    }  
    ++low;//修改low值，往后移动一位  
  }  
  return arr;  
}  
var arr=[1,45,37,5,48,15,37,26,29,2,46,4,17,50,52];  
console.log(bubbleSort3(arr));

4）算法分析

      最佳情况：T(n) = O(n)
      最差情况：T(n) = O(n2)
      平均情况：T(n) = O(n2)

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

js,冒泡排序

DDR爱好者之家 Design By 杰米

广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！

DDR爱好者之家 Design By 杰米

评论“JavaScript实现经典排序算法之冒泡排序”

暂无评论...

JavaScript实现经典排序算法之冒泡排序

详解js中常规日期格式处理、月历渲染和倒计时函数

BootStrap Tooltip插件源码解析

评论“JavaScript实现经典排序算法之冒泡排序”

P70系列延期，华为新旗舰将在下月发布

更新日志

友情链接