/**

 * 功能：插入排序法

 * 基本思想：把n个待排序的元素看成一个有序和无序表，开始时有序表中只包含一个元素，

 * 无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码

 * 依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有

 * 序表。

 * 作者：徐守威

 */

package com.xushouwei;

public class T6
{

   /**

    * @param args

    */

   public static void main(String[] args) {

      // TODO Auto-generated
method stub

      //定义需要排序的数组

      int arr1[]={1,6,0,-1,9,-100,90,10,15,-10};

      //开始排序,创建一个Select类

      InsertSort insertsort=new InsertSort();

      //调用方法开始排序

      insertsort.sort(arr1);

      //输出最后结果

      for(int i=0;i<arr1.length;i++)

      {

        System.out.print(arr1[i]+"
");

      }

   }

}

//定义一个InsertSort类

class InsertSort

{

   //插入排序法

   public void sort(int arr[])

   {

      for(int i=1;i<arr.length;i++)

      {

        //定义一个准备被插入的数

        int insertVal=arr[i];

        //定义插入的位置，即要准备和前一个数比较

        int index=i-1;

         //判断如果插入的位置>=0并且被插入的数<arr[index]

        while(index>=0&&insertVal<arr[index])

        {

           //将把arr[index]向后移动一位

           arr[index+1]=arr[index];

           //让index向前移动一位

           index--;

        }

        //将insertVal插入到适当位置

        arr[index+1]=insertVal;

      }

   }

}