Lucy's Note of Coding

package utitled;


import static java.util.Collections.swap;

import java.util.ArrayList;
import java.util.List;

public class Test {

  public static void main(String[] args) {

    List<Integer> aa = new ArrayList<>();
    aa.add(23);
    aa.add(12);
    aa.add(32);
    aa.add(11);
    aa.add(6);
    aa.add(77);

    int n = aa.size();
    for (boolean sorted = false; sorted = !sorted; n--) {
      // 外層循環的判斷條件不成立，就結束整個循環
      for (int i = 1; i < n; i++) {
        if (aa.get(i-1) > aa.get(i)) {// ※i必小於n，不能用i與i+1相比
          // 進判斷為逆序
          swap(aa, i-1, i); // 兩兩index交換
          sorted = false; // 有一對逆序，不能保證整體有序
        }
      }
    }
  }
}



=============================================================================
// 尚硅谷教學影片版
import java.text.SimpleDateFormat;
import java.util.Date;

public class BubbleSort {



  public static void main(String[] args) {
//   int[] array = {-1,3,2,10,9,-2};
//
//   System.out.println("排序前：");
//   System.out.println(Arrays.toString(array));
//   doBubbleSorting(array);
//   System.out.println("排序後：");
//   System.out.println(Arrays.toString(array));

    int n = 80000;
    int[] randomArr = new int[n];
    for (int i = 0; i < n; i++) {
      randomArr[i] = (int)(Math.random() * 800000);
    }
    Date beforeSorting = new Date();
    SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String beforeStr = sdf.format(beforeSorting);
    System.out.println("排序前時間："+beforeStr);
    doBubbleSorting(randomArr);
    Date afterSorting = new Date();
    String afterStr = sdf.format(afterSorting);
    System.out.println("排序後時間："+afterStr);
  }

  /**
   * 氣泡排序
   * 外層迴圈循環次數array.lenth-1
   * @param array
   */
  public static void doBubbleSorting(int[] array) {

    int temp = 0;
    boolean flag = false;
    for (int i = 0; i < array.length-1; i++) {
    
	// 隨著陣列後面的位置確定下來，由後向前縮小比較範圍 
      for (int j = 0; j < array.length-1-i; j++) {
        // 若兩值比較為逆序，則倆倆交換
        if (array[j] > array[j+1]) {
          flag = true;
          temp = array[j];
          array[j] = array[j+1];
          array[j+1] = temp;
        }
      }
      // 若內層迴圈兩兩比較都沒出現逆序，代表排序早已完成，可提早退出
      if (!flag) {
        break;
      } else {
        // 至少有出現過一次兩兩比較逆序，重新把flag設為false供下次循環使用
        flag = false;
      }
    }
  }
}

---

• 時間複雜度(Time Complexity)
  • Best Case：Ο(n)
    • 當資料的順序恰好為由小到大時
    • 第一次執行後，未進行任何swap ⇒ 提前結束(因為內層迴圈不會跑，僅跑了外層迴圈而已)。
  • Worst Case：Ο(n²)
    • 當資料的順序恰好為由大到小時
    • 每回合分別執行：n-1、n-2、...、1次
    • (n-1) + (n-2) + ... + 1 = n(n-1)/2 ⇒ Ο(n²)
  • Average Case：Ο(n²)
    • 第n筆資料，平均比較(n-1)/2次
• 
  參考資料：http://notepad.yehyeh.net/Content/Algorithm/Sort/Bubble/1.php

如有敘述錯誤，還請不吝嗇留言指教，thanks!