簡單插入排序（Insertion Sort）——插入類排序法（Java實作）

所謂插入排序，就是将無序序列中的各個元素插入到已經有序的線性表中。

線上性表中，隻包含第一個元素的子表顯然可以看作有序表。接下來，我們需要将第2個開始和以後的每一個元素插入到隻包含第一個元素的子表中。我們假設将第j個元素進行插入，j-1之前的元素都已經有序。插入過程如下：

設temp = 第j個元素。從有序子表的最後一個元素(j-1)開始，依次向前（--）與temp進行比較，如果前者大于後者，将大于temp的元素都向後移動一個位置，直到不大于temp的元素位置。最後将temp插入到移出的空位上。這樣線性表中的j長度就排序完畢了，同理進行下一個元素的插入排序。

*插入類排序法的效率與初始排序狀态有關。
最壞情況下，簡單插入排序需要比較n(n-1)/2次，最壞時間複雜度為O(n²)
           

public class SimpleInsertionSort {
    public static void main(String args[]){
        int arr[] = {,,,,,,};
        simpleinsertsort(arr);
        for(int a : arr)
            System.out.print(a+",");
    }

    public static void simpleinsertsort(int arr[]){
        //從數組的第二個元素開始查找
        for(int i =  ; i < arr.length ; i++){
            int j;
            int temp = arr[i];
            //将元素與前一個元素進行比較，從後往前，将小的元素放在前面。
            for(j = i ; j >  && temp < arr[j-] ; j--){ //注意比較條件的順序。 用temp是因為，arr[i]在變化。
                arr[j] = arr[j-];
            }
            arr[j] = temp; //将arr[i]按照順序插入到j位置。
        }
    }

}