插入排序的思想： 从第二个元素开始往后，依次选择哨兵元素和前面的元素比较，如果前一个元素大于该哨兵元素（从小到大排序），则把前面那个元素移动到后一个位置；继续往前比较，直到找某个元素不大于该哨兵元素，则把哨兵元素插入到位置上；
插入排序的步骤： 1、第二个元素开始外后选择一个哨兵元素； 2、让哨兵元素和前面的元素进行比较，找到合适的位置插入； 3、循环上面两步，直到选择完所有元素； /** * Created by shuxing on 2017/7/11. */ public class insertSort { public static void main(String[] args){ int[] array = {8,3,5,7,3,8,9,1,2,6}; array=sort(array); for (int i = 0; i < array.length; i++) { System.out.println(array[i]); } } public static int[] sort(int[] array){ int j;int temp; for(int i=1;i<array.length;i++){ temp=array[i]; for( j=i-1;j>=0&&temp<array[j];j--){ array[j+1]=array[j]; } array[j+1]=temp; } return array; } }结果： 1 2 3 3 5 6 7 8 8 9 插入排序的时间复杂度： 在最好的情况下（元素已经排好顺序）：那么只需要循环 n-1 次就可以了，时间复杂度 O（n） 在最差的情况下 （元素是逆序的）：要循环调整次数： [ n * (n-1) ] / 2 ，时间复杂度为 O（n ^ 2） 平均时间复杂度为：O（n ^ 2） 空间复杂度是：O（1）
