直接插入排序

直接插入排序的基本思想是：

　　每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

　　第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。
初始序列：

　　i=1 [46] 58 15 45 90 18 10 62

　　↓

　　i=2 [46 58] 15 45 90 18 10 62

　　┌——┘

　　↓

　　i=3 [15 46 58] 45 90 18 10 62

　　┌——┘

　　↓

　　i=4 [15 45 46 58] 90 18 10 62

　　↓

　　i=5 [15 45 46 58 90] 18 10 62

　　┌—————┘

　　↓

　　i=6 [15 18 45 46 58 90] 10 62

　　┌————————┘

　　↓

　　i=7 [10 15 18 45 46 58 90] 62

　　┌—┘

　　↓

　　i=8 [10 15 18 45 46 58 62 90]
JAVA实现代码：

 

public static void insertSort(int[] arr){
   //用于循环插入比较
   for(int i=1;i<arr.length;i++){
    //把即将入列的数据保存起来，便于以后插入
    int insertVal = arr[i] ;
    //保存有序数列的尾坐标
    int index = i - 1 ;
    //下面两条语句用于交换两个数的位置(while循环和其下方的一条语句)
    while(index>=0&&insertVal<arr[index]){
     //将较大的数依次向后移动
     arr[index+1] = arr[index] ;
     //此变量用于找到没有比将要插入的数还大的位置
     index-- ;
    }
    //将即将入列的数据插入到指定位置
    arr[index+1] = insertVal ;
   }
   //输出排序结果
   for(int i=0;i<arr.length;i++){
    System.out.print(arr[i] + " ") ;
   }
}