插入排序的思想是循环数组中每一个元素，然后将这些元素依次插入到一个有序的数列中去，实现数组的排序，也就是说循环到的当前元素索引的左侧都是已经排好序的，针对当前元素，将它依次与相邻的左侧元素比较，小于左侧就两个交换，循环比较和交换的过程，直至元素大于左侧相邻元素，或者是该元素已被交换至最左侧。
代码实现如下：
public class Insertion { //插入排序 public static void sort(Comparable[] a) { //方法适用于任何实现了Comparable接口的数据类型 int N = a.length; for (int i = 1; i < N ; i++) { for (int j = i; j > 0&&less(a[j],a[j-1]); j--) { exch(a,j,j-1); } } } private static void exch(Comparable[] a, int i, int j) { //交换数组a中第i和j两个元素 Comparable c =a[i]; a[i] =a[j]; a[j] =c; } private static boolean less(Comparable c1, Comparable c2) { //判断c1是否小于c2 return c1.compareTo(c2)<0; } public static void main(String[] args) { Integer[] a ={1,2,3,2,1,6,7,8,5,3,2,5,3,6,3}; sort(a); for (int i : a) { System.out.println(i); } } }输出结果如下，按升序排列：
1 1 2 2 2 3 3 3 3 5 5 6 6 7 8
