冒泡排序之算法

冒泡排序是一種基于比較的排序算法，每次比較，小數字在左，大數字在右。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間，大數字經過交換會慢慢“浮”到最後面。

一、定義

二、算法思想

依次比較相鄰的兩個數，如果不符合排序規則，則調換兩個數的位置。這樣一遍比較下來，能夠保證最大（或最小）的數排在最後一位。

再對最後一位以外的數組，重複前面的過程，直至全部排序完成。

三、具體實作

因為有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]));      

部落格簽名：敬畏生命，珍惜時間，熱愛生活。