插入排序
工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。就是将数组第一个值看做有序的，从后每一个值放进来的时候，找放的位置。这里边就需要一些已经排好的数据可能会整体左移或者右移，所以用插入排序的算法也可以找到新数据存放到有序数组中的位置
用java代码实现：
public static void insertSort(int[] arr) {
//定义循环控制变量
int i, j;
//定义哨兵
int guard;
for (i = 1; i < arr.length; i++) {
if (arr[i] < arr[i - 1]) {
guard = arr[i];
j = i - 1;
do {
arr[j + 1] = arr[j];
j--;
} while (j != -1 && guard < arr[j]);
arr[j + 1] = guard;
}
}
}