資料結構： 排序（插入排序）

i# 算法思想

• 算法思想： 就好比我們抓紙牌，每次新抓入一張紙牌，從右到左尋找它的位置。
• 第一次 看第一個元素，顯然左邊沒有比他更小的元素了，是以它目前的位置就是0
• 第二次 看第二個元素，和第一個元素比較，如果它小于第一個元素，則它的位置放到第一個元素的位置，否則就在原位置
• 第三次 在這時，其實講過前兩次的排序i=0, i=1上的兩個元素已經是有序的了。那麼第三個元素首先和第二個元素相比較，如果它小于第二個元素則和第二個元素進行交換；然後再和第一個元素比較，如果小于第一個元素則繼續和第一個元素交換。
• 第i次排序，此時第0個元素和第i-1個元素已經是有序的了。是以第i個元素一次從第i-1到0去比較直到找到自己合适的位置。
• 直到第n次

代碼

package sort;

/**
 * 插入排序
 * 算法思想： 就好比我們抓紙牌，每次新抓入一張紙牌，從右到左尋找它的位置。
 * 第一次 看第一個元素，顯然左邊沒有比他更小的元素了，是以它目前的位置就是0
 * 第二次 看第二個元素，和第一個元素比較，如果它小于第一個元素，則它的位置放到第一個元素的位置，否則就在原位置
 * 第三次 在這時，其實講過前兩次的排序i=0, i=1上的兩個元素已經是有序的了。那麼第三個元素首先和第二個元素相比較，如果它小于第二個元素則和的個元素進行交換
 * 然後再和第一個元素比較，如果小于第一個元素則繼續和第一個元素交換。
 * 第i次排序，此時第0個元素和第i-1個元素已經是有序的了。是以第i個元素一次從第i-1到0去比較直到找到自己合适的位置。
 * 直到第n次
 */

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 4, 1, 11, 2, 37, 2};
        InsertSort sort = new InsertSort();
        sort.sort(arr);
        sort.show(arr);
    }


    public void sort(int[] a){
        for(int i = 0; i < a.length; i++){
            for (int j = i; j > 0; j--){
                /**
                 * 如果目前元素已經比i上的元素小了，則不再需要繼續比較了，目前的位置就是它需要的位置
                 */
                if (a[j-1] < a[j]){
                    continue;
                }
                swap(j-1, j, a);
            }
        }
    }

    /**
     * 使用移位法
     *
     * @param a
     */
    public void sort2(int[] a) {
        for (int i = 0; i < a.length; i++) {
            int temp = a[i];
            int j = i;
            while (j > 0) {
                if (temp < a[j - 1]) {
                    // 将j-1位置的值指派給j， 相當于j-1位置的元素後移一位
                    a[j] = a[j - 1];
                    j--;
                }else{
                    //如果目前的值，大于j-1位置上的值，則說明該位置就是目前值應該在的位置
                    break;
                }

            }
            //最終j就是temp值應該存在的位置
            a[j] = temp;

        }
    }




    public void swap(int i, int j, int[] arr) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }


    public void show(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}