排序：冒泡、選擇、插入

※冒泡排序

元素會像泡泡一樣，往左或往右移動，取決於使用升序或降序，做法是判斷相鄰的元素

綠排為 index，藍排為值
以升序為例，先判斷 index 0和1，然後 index 1和2，一直到最後
每判斷一次，如果左值 > 右值就交換
內迴圈跑完就會產生最大的數在後面，所以內迴圈跑完就會少一次外迴圈


※

int count = 0;
int[] intArray = new int[] { 5, 4, 3, 2, 1 };
int len = intArray.length - 1;
    
for (int i = 0; i < len; i++) {

    boolean finish = true;
    for (int j = 0; j < len - i; j++) {
        count++;
        if (intArray[j] > intArray[j + 1]) {
            int temp = intArray[j];
            intArray[j] = intArray[j + 1];
            intArray[j + 1] = temp;
            finish = false;
        }
    }

    if (finish) break;
}
System.out.println("迴圈跑幾次=" + count);
System.out.println(Arrays.toString(intArray));

※外迴圈只有控制內迴圈跑完一次減少一次

※如果要排序的值有一些已經排好順序了，那 finish 變數就會看出效果

※選擇排序

選擇、插入 都是將資料分成已排序和未排序兩個部分
從未排序的元素選擇一個最大或最小值放入排序的元素裡，和插入排序相反

以最上面的圖為例
以升序為例，以 index 0為基底，判斷 index 1、index2…到最後
每判斷一次，如果左值 > 右值就交換
內迴圈跑完就會產生最小的數在前面，所以內迴圈跑完就會少一次外迴圈

※

int count = 0;
int[] intArray = new int[] { 5, 4, 3, 2, 1 };
int len = intArray.length - 1;
    
for (int i = 0; i < len; i++) {

    boolean finish = true;
    for (int j = 0; j < len - i; j++) {
        count++;
        if (intArray[i] > intArray[j + 1 + i]) {
            int temp = intArray[i];
            intArray[i] = intArray[j + 1 + i];
            intArray[j + 1 + i] = temp;
            finish = false;
        }
    }

    if (finish) break;
}
System.out.println("迴圈跑幾次=" + count);
System.out.println(Arrays.toString(intArray));

※和冒泡排序只差在 if 而已

※外迴圈是抓基底的來判斷

※插入排序

從未排序的元素取第一個插入到排序的元素裡，和選擇排序相反

以最上面的圖為例
以升序為例：
第一次判斷 index 0和1
第二次判斷 index 1和2，再判斷 index 0和1
第三次判斷 index 2和3，再判斷 index 1和2，再判斷 index 0和1
依此類推...
每判斷一次，如果左值 > 右值就交換


※

int count = 0;
int[] intArray = new int[] { 3, 9, 4, 6, 1, 7, 2, 5, 8 };
    
for (int i = 0; i < intArray.length - 1; i++) {

    for (int j = i; j >= 0; j--) {

        boolean finish = true;
        count++;
        if (intArray[j] > intArray[j + 1]) {
            int temp = intArray[j];
            intArray[j] = intArray[j + 1];
            intArray[j + 1] = temp;
            finish = false;
        }

        if (finish) break;
    }

}
System.out.println("迴圈跑幾次=" + count);
System.out.println(Arrays.toString(intArray));

※外迴圈 i 值給內迴圈 j