版权声明：本文源自简书tianma，转载请务必注明出处：http://www.jianshu.com/p/8d4b55986106
概念
插入排序是插入类的排序算法，基本原理：将一个记录插入到已经排好序的有序表中，从而得到一个新的记录数增加1的有序表。
具体算法：
整个序列分为两部分，左边部分为已排序的子序列，右边部分为未排序的子序列，取出第1个未排序元素存放在临时变量tmp中，在已经排序的元素序列中从后往前遍历，逐一比较，如果遍历到的元素大于tmp，则将该元素替换下一个位置的元素，直至遍历到的元素小于或等于tmp为止。相当于将未排序的第一个元素插入到已排序的数组中，故以插入排序为名。
演示
比如我们待排序的数组是 {0, 5, 3, 4, 6, 2}
第1趟排序，5大于0，无需插入： 0 5 3 4 6 2
第2趟排序，3小于5，需要插入： 0 3 5 4 6 2
第3趟排序，4小于5，需要插入： 0 3 4 5 6 2
第4趟排序，6大于5，无需插入： 0 3 4 5 6 2
第5趟排序，2小于6，需要插入： 0 2 3 4 5 6
Java实现#####
// 定义接口
interface Sorter {
/**
* 将数组按升序排序
*/
int[] sort(int[] arr);
/**
* 交换数组arr中的第i个位置和第j个位置的关键字
*/
default void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
//插入排序
class InsertSorter implements Sorter {
@Override
public int[] sort(int[] arr) {
insertSort(arr);
return arr;
}
private void insertSort(int[] arr) {
int len = arr.length;
int i, j;
int tmp;
for (i = 1; i < len; i++) { // 从下标1开始遍历,因为下标0的已经排好序
if (arr[i] < arr[i - 1]) {
// 如果当前下标对应的记录小于前一位记录,则需要插入,否则不需要插入，直接将记录数增加1
tmp = arr[i]; // 记录下标i对应的元素
for (j = i - 1; j >= 0 && arr[j] > tmp; j--) {
arr[j + 1] = arr[j]; // 记录后移
}
arr[j + 1] = tmp; // 插入正确位置
}
}
}
}
复杂度
时间复杂度：
最好情况：当待排序的序列为顺序表时，会进行n-1次比较，0次替换，复杂度为O(n)；
最坏情况：当待排序的序列为逆序表时，会进行2+3+...+n=(n+2)*(n-1)/2次比较，2+3+...+n = (n+2)*(n-1)/2次替换，复杂度为O(n^2)；
平均情况：平均比较次数约为n^2/2, 平均移动次数为n2/2，复杂度为O(n2)。
空间复杂度：
最好情况=最坏情况=平均情况=O(1)
