從這篇開始會在程式碼當中加入一些註釋，讓整題內容更淺顯易懂

選擇排序法

• 使用選擇排序法進行陣列元素由小到大的排序，我們需要從未排序的元素中找到最小值將之與前面的值做交換。

程式範例試做:

import java.util.Arrays;

public class Alex1008_1 {
    public static void main(String[] args) {

        int arr[] = {72, 83, 24, 33, 27, 132, 47};
        int min; //紀錄本輪最小值
        int index = 0; //紀錄最小值位置索引

        for(int i = 0; i < arr.length - 1; i++) { //總共比 陣列大小-1 輪
            min = arr[i]; //將當前數設為最小
            for(int j = i+1; j <= arr.length - 1; j++) {//對剩下的元素進行比較
                if(arr[j] < min) { //若有比當前數還小的元素
                    min = arr[j]; //紀錄最小值
                    index = j; //紀錄最小值索引
                }
            }
            if(index != i) {
                arr[index] = arr[i]; //將當前值放到最小值位置完成交換
                arr[i] = min; //把最小值與當前值做交換
            }
            System.out.println("第"+(i+1)+" 輪結果為: "+Arrays.toString(arr));
        }
    }
}

程式執行結果:

第1 輪結果為: [24, 83, 72, 33, 27, 132, 47]
第2 輪結果為: [24, 27, 72, 33, 83, 132, 47]
第3 輪結果為: [24, 27, 33, 72, 83, 132, 47]
第4 輪結果為: [24, 27, 33, 47, 83, 132, 72]
第5 輪結果為: [24, 27, 33, 47, 72, 132, 83]
第6 輪結果為: [24, 27, 33, 47, 72, 83, 132]

時間複雜度

假設今天要對一陣列使用選擇排序法由小到大排序。
最佳：O(n²)
平均：O(n²)
最差：O(n²)
無論資料順序如何，都會執行兩個迴圈。

插入排序法

• 把 n 個待排序的元素看成為一個有序表和一個無序表，開始時有序表只包含一個元素，無序表中包含 n-1 個元素，排序過程中每次從無序表中取出第一個元素。

import java.util.Arrays;

public class Alex1009_1 {
public static void main(String[] args) {
    int []arr = {77, 32, 41, 56, 82, 71, 22};
    Alex1009_1(arr);
    }

    public static void Alex1009_1(int [] arr) {
        for(int i = 1; i < arr.length; i++) {
        // 定義待插入的數
            int insertVal = arr[i];
            int insertIndex = i-1; // 即 arr[i] 前面這個數的索引

        // 給insertVal找到插入的位置
        // 1.保證在insertVal找插入位置, 不越界
        // 2.insertVal < arr[insertIndex]待插入的數還沒找到插入位置
        // 3.就需要將arr[insertIndex] 後移
            while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
            arr[insertIndex + 1] = arr[insertIndex];
            insertIndex--;
            }
        // 當退出while循環時,說明插入的位置找到,insertIndex + 1
            arr[insertIndex + 1] = insertVal;

            System.out.println("第"+(i+1)+"輪插入排序後 "+Arrays.toString(arr));
        }
    }
}

程式執行結果:

第2輪插入排序後 [32, 77, 41, 56, 82, 71, 22]
第3輪插入排序後 [32, 41, 77, 56, 82, 71, 22]
第4輪插入排序後 [32, 41, 56, 77, 82, 71, 22]
第5輪插入排序後 [32, 41, 56, 77, 82, 71, 22]
第6輪插入排序後 [32, 41, 56, 71, 77, 82, 22]
第7輪插入排序後 [22, 32, 41, 56, 71, 77, 82]

時間複雜度

最佳：O(1)
當資料順序恰好為由小到大時，每輪只需比較 1 次。

平均：O(n2)
第 n 筆資料，平均需要比較 n/2 次。

最差：O(n2)
當資料順序恰好為由大到小時，第 k 回合需比 k 次。