排序算法系列：插入排序算法JAVA版（靠谱、清晰、真实、可用、不罗嗦版）

在网上搜索算法的博客，发现一个比较悲剧的现象非常普遍：

原理讲不清，混乱
啰嗦
图和文对不上
不可用，甚至代码还出错

我总结一个清晰不罗嗦版：

原理：

和选择排序类似的是也分成“已排序”部分，和“未排序”部分，选择排序是替换最小值；
“待排序”索引i从数组索引第二位开始（如果起始下标是0，就从下标1开始）,“待排序”的值插入进已排序部分的左侧（小值往前排）；
“待排序”索引i依次+1；
逐渐把“已排序”部分占满整个数组；

完整版：

https://en.wikipedia.org/wiki/Insertion_sort

3  7  4  9  5  2  6  1
3* 7  4  9  5  2  6  1
3  7* 4  9  5  2  6  1
3  4* 7  9  5  2  6  1
3  4  7  9* 5  2  6  1
3  4  5* 7  9  2  6  1
2* 3  4  5  7  9  6  1
2  3  4  5  6* 7  9  1
1* 2  3  4  5  6  7  9

图形说明：

复杂度

直接插入排序的时间复杂度，为；

需要一个临时变量存储要插入的值，所以空间复杂度为 1 ；

直接插入排序的过程中，不需要改变相等数值元素的位置，所以它是稳定的算法。

和选择排序同样，该算法可用于小数据列排序（因为时间复杂度）。

$O (n^{2})$

void insertionSort(int[] arr) {

      int i, j, newValue;

      for (i = 1; i < arr.length; i++) {

            newValue = arr[i];
            j = i;

            while (j > 0 && arr[j - 1] > newValue) {
                  arr[j] = arr[j - 1];
                  j--;
            }
            arr[j] = newValue;
      }
}