public class Test {
    public static void sort(int[] data) {
        for (int i = 1; i < data.length; i++) {
            int temp = data[i];
            int j;
            for (j = i-1; (j >= 0) && (data[j] < temp); j--) {
                data[j+1] = data[j];
            }
            data[j+1] = temp;
        }
    }

    public static void main(String[] args) {
        int[] b = { 9, 5, 6, 1, 3, 3 };
        sort(b);
        System.out.print(Arrays.toString(b));
    }
}

------解决方案--------------------
public class Demo {
    public static void insert(int[]y)
	{
		int i=0,j=0;
		//定义一个数组长度比y大一，z[0]为哨兵
	    int []z=new int[y.length+1];
	    for(i=1;i<=y.length;i++)
	    {
	    	z[i]=y[i-1];
	    }
	//基本操作，将一个记录插入到已排好序的有序表中，先将序列中的第一个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入
	for( i=2;i<=y.length;i++)
	{
		//如果y[i]比它前一个小则把它前面的那个移到y[i]的位置,并将y[i]给a，将a看做哨兵
		if(z[i]<z[i-1])
		{
			z[0]=z[i];
			z[i]=z[i-1];
		
		for(j=i-2;z[j]>z[0];j--)
		z[j+1]=z[j];//记录后移
		z[j+1]=z[0];//插入到正确位置
		}
		
	}
	for(i=1;i<=y.length;i++)
	{
		System.out.println(z[i]);
	}
	}
	public static void main(String[] args) {
		int []y={9,5,6,1,3};
	insert(y);
	

	}

}


------解决方案--------------------
http://blog.csdn.net/zhaom_916/article/details/7433066   这里有各种排序 自己改成Java就OK
C/C++ code

void insertSort(int Arr[],int n)  
{  
    int i,j;  
    //从数组的第二位开始进行插入  
    for(i = 1 ; i < n ; i ++)  
    {  
        int temp = Arr[i];//记录当前的值  
        j = i - 1;//把j赋值成待插入数据的前一位的索引  
        while(j >= 0 && temp < Arr[j])  
        {//如果temp小于前面的值，前面的值就向后移位  
            Arr[j + 1] = Arr[j];  
            j --;  
        }  
        //最后把值赋给该值的适当位置  
        Arr[j + 1] = temp;  
    }  
}