插入排序
- 原理
- 第一步，保证([0,0])区间元素有序，因为只有一个元素，所以不需要过多考虑
- 第二步，保证([0,1])区间元素有序，如果第二个元素与前一个元素逆序，则交换位置
- 第三步，保证([0,2])区间元素有序，如果第三个元素与前一个元素逆序，则交换位置，如果前面仍有元素，继续判断是否逆序直至没有元素或者呈顺序关系
- ...
代码实现
```c++
public class Solution {
public static void insertSort(int[] arr) {
int len = arr.length;
for (int i = 1; i < len; i++) {
int newNumIndex = i;
while (newNumIndex - 1 >= 0 && arr[newNumIndex - 1] > arr[newNumIndex]) {
int temp = arr[newNumIndex];
arr[newNumIndex] = arr[newNumIndex - 1];
arr[newNumIndex - 1] = temp;