插入排序的基本思想：

将未被排序的数字依次从已排序好的数字的一端开始比较然后交换两个数的位置，

依次比较直到找到合适的位置然后插入。

public static void sort(Comparable[] arr) {

　　for(int i = 1; i < arr.length; i ++) {
　　　　for(int j = i; j > 0; j --) {
　　　　　　if(arr[j].compareTo(arr[j-1]) < 0)
　　　　　　　　swap(arr,j,j-1);//交换数组arr中索引值为j和j-1的元素的位置
　　　　}
　　}
}

插入排序的改进：

每一次比较过程后如果需要交换操作，可以转化为赋值操作，

用减少操作步骤的方式来提高效率。

public static void sort(Comparable[] arr) {

　　int n = arr.length;
　　for(int i = 0; i < n; i ++) {
　　　　Comparable e = arr[i];//先保存将要插入的元素的值
　　　　int j = i;

　　　　//此循环用来找到新来元素应该插入的位置
　　　　for(; j > 0 && arr[j-1].compareTo(e) > 0 ; j --)
　　　　　　arr[j] = arr[j-1];
　　　　arr[j] = e;
　　}
}

------------------------------------------------------------------------------

学习来源：慕课网《算法与数据结构》