插入排序
输入:n个数的一个序列<a1,a2,…,an>。
输出:输入序列的一个排列<a1',a2',…,an‘>,满足a1'≤a2'≤…≤an'。
public static void insertionSort(int[] a){
int key,i;
for(int j=1;j<a.length;j++){
key=a[j];
i=j-1;
while(i>=0&&a[i]>key){
a[i+1]=a[i];
i=i-1;
}
a[i+1]=key;
}
}
j表示正准备插入的数的下标，a[0,j-1]构成了当前排序好的数组，事实上，a[0,j-1]就是原来位置a[0,j-1]的元素，但现在已按序排列。
