public class Insert {
 public static void main(String[] args) {
  int a[] = {9,3,28,6,34,7,10,27,1,5,8};
  show(a);
  for (int i=1;i insertOne(a, i);
 }
 show(a);
}
static void show(int a[]){
 for (int i=0;i System.out.print(a[i]+" ");
}
System.out.println();
}
//把第k个元素融入到前面有序队列
static void insertOne(int a[],int k){
for (int i=0;i<=k;i++){
 if(a[i]>=a[k]){
  int temp = a[k];
  //移动之前先把a[k]放到一个中间变量处
  //从k位置前面的数依次往后移动，直到i位置
  for (int j=k-1;j>=i;j--){
   a[j+1] = a[j];
  }
  a[i] = temp;
  //把中间变量中的值给a[i],移动之后i处的值为空。
 }
}
}
}

package sorting;
/**
 * 插入排序
 * 平均O(n^2),最好O(n),最坏O(n^2);空间复杂度O(1);稳定;简单
 * @author zeng
 *
 */
public class InsertionSort {
 public static void insertionSort(int[] a) {
  int tmp;
  for (int i = 1; i < a.length; i++) {
   for (int j = i; j > 0; j--) {
    if (a[j] < a[j - 1]) {
     tmp = a[j - 1];
     a[j - 1] = a[j];
     a[j] = tmp;
    }
   }
  }
 }
 public static void main(String[] args) {
  int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
  insertionSort(a);
  for (int i : a)
        System.out.print(i + " ");
 }
}