为了给插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位，这种算法叫做插入排序。我的理解就是要插入的元素与其左边的每一个元素比较，使左数组有序。
算法实现 public class InsertSort { public static void sort(int[] array) { int temp; for(int i=1;i<array.length;i++)//从array[1]开始，进行n-1次排序 { for(int j=i;j>0&&j<array.length;j--)//将数组索引的左边排好序 { if(array[j]<array[j-1]) { temp=array[j]; array[j]=array[j-1]; array[j-1]=temp; } } } } public static boolean isSorted(int[] array)//判断排序是否正确 { for(int i=1;i<array.length;i++) { if(array[i]<array[i-1]) { System.out.println("false"); return false;//在排序有错时跳出循环 } } System.out.println("排序结果正确,输出结果为:"); return true; } public static void show(int[] array) //排序之后输出结果 { for(int i=0;i<array.length;i++) { System.out.print(array[i]+" "); } } public static void main(String[] args) { int[] array={5,13,3,7,4,16,18,11,2,3,9}; sort(array); isSorted(array); show(array); } } 算法特点： 排序所需时间取决于输入中元素的初始顺序最坏情况需要N²/2次比较和N²/2次交换，最好情况N-1次比较，0次交换