插入排序

思路

1.首先对于a[0]这个单个元素来说其自己就是有序的，所以要从a[1]开始
2.第二步是把a[1]这个元素插入a[0]这个列表中
3.如果a[0]比a[1]大的话，a[0]应该给a[1]位置，a[1]=a[0]，那么a[0]朝后面移动了一个位置,这样a[1]就可以放到它应有的位置也就是a[0]这个位置了，也就是a[0]=a[1]
4.之后呢，[a[1],a[0]]是有序的了，那么只需要把a[2]插入[a[1],a[0]]这个有序序列使其有序也就可以了
5.按照这个思路依次插入第1到n-1下标对应的元素最终整个数组就有序了

代码

package sort;

public class InsertSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a= {7,6,5,4,3,2,1};
        insertSort(a);
        for (int i = 0; i < a.length; i++)
        {
            System.out.printf("%d ",a[i]);
        }
        System.out.println();
    }
    
    //插入排序
    
    public static void insertSort(int[] arr) 
    {
        int len=arr.length;//获取数组的长度
        for(int i=1;i<len;i++)//因为第一个元素单独来看肯定是有序的,依次把2,3,4,...n-1下标的元素依次插入
        {
            int insertValue=arr[i];//要插入的值
            int insertIndex=i-1;//要插入的位置的下标
            while(insertIndex>=0&&arr[insertIndex]>insertValue)//insertIndex>=0是防止下标越界
            {
                arr[insertIndex+1]=arr[insertIndex];//元素后移一位，给要插入的位置腾出位置
                insertIndex--;//继续向前比对
            }
            arr[insertIndex+1]=insertValue;
            //为什么是InsertIndex+1呢，因为假如列表只有两个元素，1,2两个，2插入1这个有序列表，其不进行循化，不可以a[0]=a[1]，2的位置无需改变，应该是a[1]=a[1]
            
        }
    }

}

插入排序

原文：https://www.cnblogs.com/mengxiaoleng/p/11668504.html