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

冒泡排序概述

冒泡排序是计算机科学中极具代表性的排序算法之一。作为一种基于元素比较的排序方法，它的时间复杂度为O(n^2)。尽管在大规模数据面前效率有限，但其实现逻辑简单直观，因此在数据量n较小或教学演示场景中仍具有较好的性能表现。

算法原理与描述

1）算法原理 冒泡排序的核心思想是通过重复遍历待排序数列，依次比较相邻的两个元素。如果前一个元素大于后一个元素（针对升序排列），则交换它们的位置。经过一趟完整的遍历，最小的元素会被“冒泡”至序列的最前端；后续每一趟都遵循此规则，直至所有数据完成有序排列。

2）算法描述 <1>从头开始，依次比较相邻的两个元素。若前者大于后者，则执行交换操作； <2>对每一对相邻元素重复上述比较与交换过程，直至处理到最后一对元素。此时，序列末尾的元素应为当前未排序部分的最大值； <3>针对剩余未排序的所有元素，重复执行步骤<1>和<2>，但无需再处理已排序好的最后一个元素； <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)

以上内容涵盖了冒泡排序的核心原理、基础实现及两种优化策略。希望这些内容能为您的学习提供有益参考，也欢迎大家继续支持本站获取更多技术分享。