java 插入排序

插入排序原理很简单，将一组数据分成两组，我分别将其称为有序组与待插入组。每次从待插入组中取出一个元素，与有序组的元素进行比较，并找到合适的位置，将该元素插到有序组当中。就这样，每次插入一个元素，有序组增加，待插入组减少。直到待插入组元素个数为0。当然，插入过程中涉及到了元素的移动。

public static void InsertSort(int[] arr)
{
    int i, j;
    int n = arr.length;
    int target;
 
    //假定第一个元素被放到了正确的位置上
    //这样，仅需遍历1 - n-1
    for (i = 1; i < n; i++)
    {
        j = i;
        target = arr[i];
 
        while (j > 0 && target < arr[j - 1])
        {
            arr[j] = arr[j - 1];
            j--;
        }
 
        arr[j] = target;
    }
 }

在简单的理解：就是取第n个元素，和左边的元素进行对比，找到合适的位置互换就可以了