直接插入排序在最好情况下的时间复杂度为()
A.O(logn)
B.O(n)
C.O(nlogn)
D.O(n2)
正确答案是 B
最好情况下，每次都插入在最后。 因为至少对每个数都要遍历一次， 所以是O（n）
是道好题，会了这道就能举一反三
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)
概念： 每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。
列举一款你常用的移动APP，并分析他的最核心功能、满足的需求、超预期的功能以及竞争优势和发展趋势
从浏览器输入URL到展示页面的全流程是怎么样的？
分析一下，小程序为什么不能分享朋友圈？
基于TCP协议建立连接和结束连接的过程
是道好题，会了这道就能举一反三
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)
概念： 每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。