插入排序最差是N^ 选择排序和冒泡排序严格是N^ 所以插入排序的算法性能要优于选择排序和冒泡排序 0～0范围是有序的 所以从下标1位置开始 第一个for循环 表示想在0~1范围有序，想在0～2范围有序，想在0~3范围有序... 第二个for循环 比如第i的位置 此时想让0~i位置有序 已经做到了在0~i-1范围上有序了
比如第i位置上的数是Y j=i-1 j+1就是i j位置上的数和j+1位置上的数比较 前一个要小了 这个时候要交换
交换完了之后 Y就来到了i-1位置 接下来往左移动再比较j--位置上的数即i-2 j+1位置上的数就是i-1 如果j位置上的数大于j+1位置上的数 还是往左移 j就是当前数的前一个数,当前数在j+1位置
所以第二个for循环就是在做： 一直往前看如果一直都小的话就一直往前换 换到越界停或者换到不比左边位置小了停
二分法
1、在一个有序的数组中，找某个数是否存在
如果从左往右遍历找的话 就是一个O(N)的算法 每个数只碰一次 通过二分法找最快 先找到中点位置的数
如果x > num 所以x右边一定不会有num 就可以在x左边继续二分 如果x < num 所以x左边是不需要看的 只在x右边二分
这个算法的时间复杂度怎么估计？一次砍一半 一共砍几次 时间复杂度是
比如数组中一定有8个数 砍一半4个 再砍2个 再砍1个 如果还找不到就是不存在这个数
如果找到了就是砍3次就是
2、在一个有序数组中，找>=某个数最左侧的位置
是否满足大于等于num
4是满足的 所以左侧有可能还存在大于等于3的数 所以继续二分
假设中点是箭头所指的2
次是不满足大于等于num
所以右边去二分
再找中点位置 上图箭头3
比之前记录的t的位置更靠左 所以放弃之前t的位置记 上图箭头3的位置为t
满足大与等于3 再往左分
也满足 再分就没有数据可分了
二分法找一个数存不存在 当找到了 就不需要二分了
而找大于等于num最左侧的位置一定是二分到结束的 即二分到某一个范围上没有数才停
3、局部最小值问题
在数组中 无序 任何2个相邻的数不相等
局部最小定义
如果0位置上的数小于1位置上的数 那么0位置就是局部最小的位置 如果N-1位置上的数 小于 N-2位置上的数 那么N-1就是局部最小位置 如果中间位置i即比左边i-1位置小同时也比i+1位置小 那么i位置就是局部最小 i位置必须同时小于左边和右边的数 才叫局部最小
在这样一个数组中 找出一个局部最小即可
能不能求的过程 时间复杂度好于O(N)
最好二分 ？
这道题目的解析 请看下文讲解哟
