*

  * @author zhangtao

  */

 public class StraightInsertionSort

 {

     public static void main(String[] args)

     {

         int arr[]={3,1,5,7,2,4,9,6};

         insertSort(arr);

     }

     //直接插入排序

     static void insertSort(int[] a)

     {

         int Arrlength=a.length;

         for(int i= 1; i<Arrlength; i++){

             if(a[i] < a[i-1]){                   //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入

                 int j= i-1;

                 int temp = a[i];                 //复制为哨兵，即存储待排序元素  

                 while(temp<a[j]){                //查找在有序表的插入位置

                     a[j+1] = a[j];

                     j--;                         //元素后移

                     if(j<0)

                     {

                         break;

                     }

                 }

                 a[j+1] = temp;                  //插入到正确位置

             }

             printLine(a,i);                     //打印每趟排序的结果

         }

     }

     //打印每次的排序结果

     static void printLine(int[] arr,int i)

     {

         System.out.println(i+":");

         int Arrlength=arr.length;

         for(int j=0;j<Arrlength;j++)

         {

             System.out.print(arr[j]+"  ");

         }

         System.out.println();

     }

 }