插入排序

排序介绍

插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

借用网上一张动图来表示该过程： 很显然，插入排序的核心就是：每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。

大家可以把该过程想象为：许多人排序一手扑克牌。

开始时，我们的左手为空，并且桌子上的牌面向下。 然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。 为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。 拿在左手上的牌总是排序好的，而原来这些牌是桌子上牌堆中顶部的牌。

代码实现

使用扑克牌思想来实现

public static void Insertion_Sort(int[] arr){
        int i,j,temp;
        //先判断，如果为空或者长度小于2就直接不用排序。
        if (arr==null ||  arr.length<2){
            return ;
        }

        //从下标为1的开始遍历，默认第一张为排序好了的
        for (i=1;i<arr.length;i++){
            //将该下标值保存下来
            temp=arr[i];
            for (j=i;j>0 && arr[j-1]>temp;j--){//如果arr[j-1]>a[j],依次交换值。
                arr[j]=arr[j-1];
            }
            arr[j]=temp;
        }
 }

第二种方式：

public static void insertSort(int[] arr){
        if (arr.length==2||arr==null){
            return;
        }
        //从下标为1开始。
        for (int i = 1; i < arr.length; i++) {
            for (int j = i-1; j >=0 && arr[j]>arr[j+1] ; j--) {
                int temp=arr[j+1];
                arr[j+1]=arr[j];
                arr[j]=temp;
            }

        }
    }