排序算法之插入排序

思路：

将数组的第一个元素作为有序数组，其余的作为无序数组，从无序数组中取一个跟有序数组比较，将其放在合适的位置。那么有序数组就有两个元素，无序数组就减少一个元素。

 依此类推，每一轮从无序数组里取一个放到有序数组里面排序，共arr.length - 1轮

代码：

 1     /**
 2      * 插入排序
 3      * @param arr
 4      */
 5     public static void insertSort(int[] arr) {
 6         if (arr == null || arr.length == 0) {
 7             return;
 8         }
 9         //待插入有序数组的值
10         int insertValue;
11         //与insertValue做比较的值的下标
12         int index;
13         //无序数组的下标范围是 [1, arr.length - 1]
14         for (int i = 1; i < arr.length; i++) {
15             insertValue = arr[i];
16             index = i - 1;
17             //insertValue与有序数组依次比较
18             while (index >= 0 && insertValue < arr[index]) {
19                 //如果insertValue比arr[index]小，arr[index]后移一位
20                 arr[index + 1] = arr[index];
21                 index--;
22             }
23             arr[index + 1] = insertValue;
24         }
25     }