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)