以下笔记根据b站视频【一周刷爆LeetCode】-马士兵 总结。为个人学习记录笔记，特与各位学习者分享
现实比较算法流程的好坏，先看时间复杂度，时间复杂度无法比较的时候，需要根据实际运行时间来比较好坏
这两个的复杂度都是O（N^2），比较的轮数也一样，但区别是选择排序时每次把最小（或最大）的下标选出来，与最后一位进行交换。而冒泡排序是每一次比较的时候都进行交换，使最小（或最大）的逐步移位到后面
注意
不可以再数组中对相同下标的元素使用异或，因为上面的例子中，虽然值相同，但地址不同，指向的还是不同的值。而在数组中，下标相同就是同一个地址，相当于自己和自己做异或运算，而异或运算具有特性：与自身异或的结果是0，因此所有的内容都将抹为0
【使用刚才知识点的典型例题】
题目一：只有一个奇数次数的数，其余都是偶数次数
思路：让数组中所有的数异或
得到的结果就是那个奇数次的数
题目二：有两个奇数次数的数，其余是偶数次数
思路：让所有数异或，得到结果是：eor=a⊕b
假如eor的第八位是1，代表a和b在第八位一定是不一样的。
此时只异或第八位不是1的，最后得到的结果eor2是：
eor2=a 或者b
【核心思想：把a和b以某种方式分在两个堆里】
插入排序在有序数组 中的操作如下：
- 第一步， 是默认排好序的，不需要任何操作。
- 第二步， 与前面的 进行比较，由于 ，比较只进行一次，直接确认 的位置。
- 第三步， 与前面的 比较，，只进行一次比较，确定 的位置。
- 以此类推，每个新元素只需要进行 一次比较，因为每次比较时，新的元素总是大于前面的元素，不需要继续往前找插入位置。
因此，对于有序数组，插入排序的每次比较只需要与前一个元素比较一次，总的比较次数是 N−1次（这里 N 是数组的长度），即 线性时间复杂度 O(N)。
插入排序在逆序数组 中的操作如下：
在完全逆序数组（如 ）中，插入排序的每个新元素需要与前面的所有元素进行比较，直到找到它应该插入的最前面位置。这导致每次插入操作都需要做大量比较，总的比较次数是 1+2+3+…+(N−1)，即形成了等差数列，总的比较次数是 O(N²)。
经典二分法
在一个有序数组中，找某个数是否存在？
答：每次都分成两部分，和这个数进行比对。时间复杂度O(log₂N)
有序数组，找>=number的最小的位置
如
每次二分的时候，先进行判断，若符合，就存下这个符合的二分的位置，若不符合，就不存，二分法把整个数组都分完的时候，箭头所指（即存下的位置）就是符合条件的值。
【经典二分法和这个的最大区别就是，前者，只要找到这个数就不再二分了，而后者，==要一直分到最后为止==】
局部最小：比如有个数i，比i-1小，也比i+1小，不用考虑其他的，它就是一个局部最小的数。
【解题思路为：二分法变形】
解答：先看第一个，如果第一个是局部最小，那直接返回了，如果不是，那么它的趋势一定是降低的。
再看N-1项，如果它是局部最小，也直接返回。如果不是，证明N-1往前的趋势也是降低的。
如果0与N-1都不是局部最小，那么直接二分法取中间，如果是局部最小，就返回。如果不是（比如M比M-1要大）那么在0到M中间，必有局部最小。二分到最后，一定能找到至少一个局部最小的值。
【不一定必须有序才要用到二分，根据题目的状况与策略，有时也是会用到二分。左右两侧和策略有关，并且确定可以甩掉一边，就可以使用二分】
版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/43057.html