一、基本思想

• 依次比較相鄰兩個(gè)數(shù)的大小，較小的數(shù)下沉，較大的數(shù)冒起來(lái)

  
  
  冒泡排序.gif

二、算法實(shí)質(zhì)

• 從第一個(gè)數(shù)開(kāi)始遍歷數(shù)組，每一次遍歷都找出此次遍歷的最大值，放到隊(duì)伍的末尾
• 第2次遍歷，最后一項(xiàng)不必再比較，數(shù)組長(zhǎng)度減一，最大值放到此次數(shù)組的末尾
• 第3次再減一......直到最后，所有數(shù)字都按從小到大排列

三、基礎(chǔ)算法

• 優(yōu)先選出大的放右邊

for (let i = 0; i < arr.length - 1; i++) {
  for (let j = 0; j < arr.length - 1 - i; j++) {
    if (arr[j] > arr[j + 1]) { // 相鄰的比較大小，大的放右邊
      let temp = arr[j]; // [arr[j], arr[j + 1]] = [arr[j+1], arr[j]]
      arr[j] = arr[j + 1];
      arr[j + 1] = temp;
    }
  }
}

四、復(fù)雜度

• 空間上只用了一個(gè)輔助單元，所以為 O(1)
• 第1次遍歷為n-1次，第2次n-2次......第i次n-i次，總次數(shù)=1/2n(n-1)，則時(shí)間復(fù)雜度為O(n2)

五、算法改進(jìn)

1、外層減少循環(huán)次數(shù)

let flag = true; // 表示在一次循環(huán)中是否發(fā)生了數(shù)據(jù)交換
for (let i = 0; i < arr.length - 1; i++) {
  // flag為false時(shí)，上一次循環(huán)已經(jīng)沒(méi)有發(fā)生數(shù)據(jù)交換，證明順序已經(jīng)排完了
  if (!flag) {
    break;
  }
  flag = false; // 每次循環(huán)都先置為false，即認(rèn)為不會(huì)發(fā)生交換
  for (let j = 0; j < arr.length - 1 - i; j++) {
    if (arr[j] > arr[j + 1]) {
      flag = true; // 發(fā)生數(shù)據(jù)交換，則要繼續(xù)比較
      let temp = arr[j];
      arr[j] = arr[j + 1];
      arr[j + 1] = temp;
    }
  }
}

2、內(nèi)層減少循環(huán)次數(shù)

let k = arr.length -1; // 動(dòng)態(tài)k，記錄上一次內(nèi)循環(huán)的上界值，因?yàn)閗以后的數(shù)沒(méi)有再發(fā)生數(shù)據(jù)交換，證明k以后的數(shù)順序正確，則下一次的內(nèi)循環(huán)只需比較截止到位置k的數(shù)
for (let i = 0; i < arr.length - 1; i++) {
  let lastFlag = 0; // 用于記錄內(nèi)循環(huán)交換數(shù)據(jù)的位置，每次循環(huán)初始化為0
  for (let j = 0; j < k - i; j++) {
    if (arr[j] > arr[j + 1]) {
      lastFlag = j; // 記錄最后一次交換數(shù)據(jù)的位置
      let temp = arr[j];
      arr[j] = arr[j + 1];
      arr[j + 1] = temp;
    }
  }
  if (lastFlag === 0) { // 內(nèi)循環(huán)不再交換，則排序結(jié)束，外循環(huán)也可break掉
    break;
  }
  k = lastFlag; // 讓下一次循環(huán)的上界值變成此次循環(huán)的最后一次交換的位置
}

六、算法變形

1、優(yōu)先選出小的放右邊

for (let i = 0; i < arr.length - 1; i++) {
  for (let j = 0; j < arr.length - 1 - i; j++) {
    if (arr[j] < arr[j + 1]) { // 相鄰的比較大小，小的放右邊
      let temp = arr[j];
      arr[j] = arr[j + 1];
      arr[j + 1] = temp;
    }
  }
}

2、由大到小排列，但無(wú)法引入內(nèi)循環(huán)標(biāo)志位

• 跟冒泡基礎(chǔ)算法的查找次數(shù)是一樣的，本質(zhì)上就是一個(gè)兩層循環(huán)（每循環(huán)一次找出最大值放到第一個(gè)，并下一次循環(huán)次數(shù)減一）。

for (let i = 0; i < arr.length - 1; i++) {
  for (let j = i + 1; j < arr.length; j++) {
    if (arr[i] < arr[j]) { // 優(yōu)先選出大的放左邊
      let temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }
}