冒泡排序之算法

冒泡排序是一种基于比较的排序算法，每次比较，小数字在左，大数字在右。比较是相邻的两个元素比较，交换也发生在这两个元素之间，大数字经过交换会慢慢“浮”到最后面。

一、定义

二、算法思想

依次比较相邻的两个数，如果不符合排序规则，则调换两个数的位置。这样一遍比较下来，能够保证最大（或最小）的数排在最后一位。

再对最后一位以外的数组，重复前面的过程，直至全部排序完成。

三、具体实现

因为有2层循环，所以有4种实现方式。

//交换元素
function swap(arr,i,j){
  var temp = arr[j];
  arr[j] = arr[i];
  arr[i] = temp;
}      

1、外循环正序遍历，内循环正序遍历，结果靠后的元素位置先确定。

function bubbleSort1(arr) {
  var len = arr.length;
  for (var i = 0; i < len; i++) {
    for (var j = 0,stop = len - 1 - i; j < stop; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
      }
    }
  }
  return arr;
}
console.log(bubbleSort1([3,5,9,2,11,6,3,5]));      

2、外循环正序遍历，内循环逆序遍历，结果靠前的元素位置先确定。

function bubbleSort2(arr) {
  var len = arr.length;
  for (var i = 0; i < len; i++) {
    for (var j = len - 1; j >= i+1; j--) {
      if (arr[j] < arr[j - 1]) {
        swap(arr, j, j - 1);
      }
    }
  }
  return arr;
}
console.log(bubbleSort2([3,5,9,2,11,6,3,5]));      

3、外循环逆序遍历，内循环正序遍历，结果靠后的元素位置先确定。

function bubbleSort3(arr) {
  var len = arr.length;
  for (var i = len - 1; i >= 0; i--) {
    for (var j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
      }
    }
  }
  return arr;
}
console.log(bubbleSort3([3,5,9,2,11,6,3,5]));      

function bubbleSort4(arr) {
  var len = arr.length;
  for (var i = len - 1; i >= 0; i--) {
    for (var j = len - 1; j >= len - 1 - i; j--) {
      if (arr[j] < arr[j - 1]) {
        swap(arr, j, j - 1);
      }
    }
  }
  return arr;
}
console.log(bubbleSort4([3,5,9,2,11,6,3,5]));      

function bubbleSort5(arr) {
  var tail = arr.length -1;
  for (var i = 0; i < tail; tail--) {
    for (var j = tail; j > i; j--) {//第一轮, 先将最小的数据冒泡到前面
      if (arr[j] < arr[j - 1]) {
        swap(arr, j, j - 1);
      }
    }
    i++;
    for (var j = i; j < tail; j++) {//第二轮, 将最大的数据冒泡到后面
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
      }
    }
  }
  return arr;
}
console.log(bubbleSort5([3,5,9,2,11,6,3,5]));      

博客签名：敬畏生命，珍惜时间，热爱生活。