数据结构： 排序（插入排序）

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] + " ");
        }
    }
}