上一篇简单的实现了一下选择排序，这里再次复习一下选择排序的两个特点
运行时间和输入无关！
为了找出最小的元素而扫描一遍数组并不能为下一遍的扫描提供任何信息，这种性质在某种情况下可以说是缺点。因为使用选择排序，你会发现，一个已经有序的数组或是主键全部相等的数组和一个元素随机排列的数组所用的排序时间，是等长的。
数据移动是最少的！
每次交换都会改变两个数组元素的值，因此选择排序用了N多次的交换，交换次数和数组的大小是线性关系。
插入排序思想
将一个数目插入该占据的位置，，就是检查第i个数字，如果在它的左边的数字比它大，进行交换，这个动作一直继续下去，直到这个数字的左边数字比它还要小，就可以停止了。
举例：
假设我们输入的是 “5，1，4，2，3” 我们从第二个数字开始，这个数字是1，我们的任务只要看看1有没有正确的位置，我们的做法是和这个数字左边的数字来比，因此我们比较1和5，1比5小，所以我们就交换1和5，原来的排列就变成了“1，5，4，2，3 ”
接下来，我们看第3个数字有没有在正确的位置。这个数字是4，它的左边数字是5，4比5小，所以我们将4和5交换，排列变成了 “1，4，5，2，3 “我们必须继续看4有没有在正确的位置，4的左边是1，1比4小，4就维持不动了。
再来看第四个数字，这个数字是2，我们将2和它左边的数字相比，都比2大，所以就将2一路往左移动，一直移到2的左边是1，这时候排序变成了 “1，2，4，5，3 ” 最后，我们检查第五个数字，这个数字是3，3必须往左移，一直移到3的左边是2为止，所以我们的排列就变成了 “1，2，3，4，5 ”排序因此完成了。
插入排序代码
/** * 类描述：插入排序 * 创建人：gjl * 创建时间：2017/9/4 13:31 * 修改人： * 修改时间：2017/9/4 13:31 * 修改备注： */ public class InsertSorting { public static void sort(Comparable[] a) { //将a[i]按升序排列 int N = a.length; for (int i = 1; i < N; i++) { //将a[i]插入到a[i-1]、a[i-2]、a[i-3]...之中 for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) { exch(a, j, j - 1); } } } private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } private static void exch(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; } private static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { Log.i("learn", a[i] + "====a.length==="); } } public static boolean isSorted(Comparable[] a) { for (int i = 1; i < a.length; i++) { if (less(a[i], a[i - 1])) { return false; } } return true; } }less，exch(),isSorted()方法主要查看我之前的博客排序模板
