插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
步骤： 设数组为a[0…n-1]。
初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1
将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。
i++并重复第二步直到i==n-1。排序完成。
public static int[] insertionSort(int[] A, int n) { /*int now,i; for(i=1; i<n; i++){ now = i; while (now>0){ if (A[now-1]>A[now]){ swap(A,now-1,now); now--; } else { break; } } } return A;*/ int i, j; for (i=1; i<n; i++) for (j=i-1; j>=0&&A[j]>A[j+1]; j--) swap(A, j, j+1); return A; } private static void swap(int[] array ,int first ,int second){ int temp; temp = array[first]; array[first] = array[second]; array[second] = temp; }