冒泡排序算法（JavaScript实现）

算法流程

比较相邻的元素，如果第一个比第二个大，就交换，从第一对元素开始到最后一对元素做同样的工作，每次都重复以上步骤，当遍历arr.length-1次后，遍历完所有的元素

复杂度

时间复杂度为：O(n^2)

代码实现

代码：

function bubbleSort(arr){
  for(var i = 0; i < arr.length-1; i++){
    for(var j = 0;j < arr.length-i;j++){
      if(arr[j] > arr[j+1]){
        var t = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = t;
      }
    }
  }
  
  return arr;
}

var arr = [1,4,2,5,3];
bubbleSort(arr); // [1 , 2 , 3 , 4 , 5]

算法优化

当待排序数组为[1, 3, 4, 5, 6, 7, 8, 9, 2]时：
第1趟排序的结果为： 1 2 3 4 5 6 7 8 9
此时其实序列已经完成，但是根据上述代码仍得继续遍历，直至第9趟排序。这显然是不合理的，如果我们能在代码中加入一个flag标记上一趟排序中是否进行过交换，如果进行过未进行交换，说明当前数组以及有序。
代码如下：

function bubbleSort(arr){
  var flag = true;
  while(true){
    flag = false;
    for(var i = 0; i < arr.length-1; i++){
      for(var j = 0;j < arr.length-i;j++){
        if(arr[j] > arr[j+1]){
          var t = arr[j];
          arr[j] = arr[j+1];
          arr[j+1] = t;
          flag = true;
        }
      }
    } 
  }
  
  return arr;
}

var arr = [1, 3, 4, 5, 6, 7, 8, 9, 2];
bubbleSort(arr);  //[1, 2, 3, 4, 5, 6, 7, 8, 9]