插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。插入排序对于部分有序效率很高，因为扫描的时候是在已排序的基础上，默认第一个是已排序
public void insert(int[] a)
{
for(int i=1;i<a.length;i++) //n-1此扫描，依次向前插入n-1个元素
{
int temp=a[i]; //每趟将a[i]插入到前面的排序子序列中
int j;
for(j=i-1;j>=0&&temp<a[j];j--)
{
a[j+1]=a[j]; //将前面较大的元素向后移动
}
a[j+1]=temp; //temp值到达插入位置
}