是道好题，会了这道就能举一反三

void InsertSort(int* arr, int sz) { for (int i = 0; i < sz - 1; i++) { int end = i; int tmp = arr[end + 1]; while (end >= 0) { if (arr[end] > tmp) { arr[end + 1] = arr[end]; end--; } else break; } arr[end + 1] = tmp; } } 假如按照升序进行排序，在排序之前序列已经有序，则每次只需要 arr[end + 1] = tmp; 相当于只遍历了一遍序列，不需要进行移动。此时就是最好的情况时间复杂度为O(N)  

插入排序第二个for循环默认从后往前比较的

当待排序序列递增有序时，时间复杂度最小。此时需要遍历n个元素，且元素直接插入到已排序序列最后，时间复杂度为O(N)

概念： 每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。