直接插入排序在最好情况下的时间复杂度为()
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)
概念： 每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。
某公园内有个奇怪的摊主小周，他只在星期一、星期二、星期三、星期五和星期六工作，而且他只出售4种商品：玩具汽车、充气气球、橡皮泥和遥控飞机。<
北京有一条1公里长的街道，你认为一天能收多少钱的停车费？
cookies，sessionStorage 和 localStorage 的区别？
怎么理解产品经理与技术研发之间的关系？
是道好题，会了这道就能举一反三
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)
概念： 每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。