算法笔记（一）—— 认识复杂度和简单排序算法
时间复杂度是在一个算法流程中，常数操作的数量级指标。（最差情况下的算法表现）
比较两个算法的优劣，在足够的空间下，看时间复杂度指标，若相同，需要在大数据运行下来判断两个算法的“常数项指标”。
选择排序：每次循环将待排序的所有数中最小数放到这些数开头位置，依次循环即可。
冒泡排序：每次循环通过邻近位置交换，将所有待排序数中最大数交换至数组末尾位置，依次循环即可。
异或
异或其实相当于无进位相加，并且异或操作满足结合律和交换律。
通过异或操作完成两个变量值交换：
a = a^b;
b = a^b;
a = a^b;注意：要求a和b指向的内存不同，否则会出错（将数值抹零）。
Question 一个数组中已知只有一种数出现奇数次，其余所有数都出现偶数次，怎么找到出现奇数次的数？如果有两个数奇数次，其余数偶数次，如何找到？要求时间复杂度O（N），空间复杂度O（1）
1. 将所有数异或，最后的值为要寻找的奇数。
2. 将所有数异或，得到a^b的值，又因为a!=b，那么a^b不等于0，那么c=a^b，c一定有一位不等于0（a,b在该位上不一样），那么将该位上不为1的数全部异或，得到a,b中的一位，再将c异或该数得到a,b中的另一个数。
使用下方代码，可以找到c中最右边的1位置。
rightone = c&(~c+1) //提取出c最右处的1插入排序（时间复杂度O（N^2） 空间复杂度O（1））
1. 保证0~0有序
2. 保证0~1有序，若无序，则交换
3. 依次下去，如果无序就将该数与前数交换，直到有序为止。
二分查找
1. 有序数组中找某个数是否存在。O（logN）
2. 有序数组找到大于等于某个数最左侧位置
一直二分到结束，找到大于等于num的最小位置即可。
3. 局部最小值
一个无序数组中，但是任何两个相邻数不等，找到一个极小值。
3.1. 判断0位置是否局部最小，若是直接返回。
3.2. 判断N-1位置是否局部最小，若是直接返回。
3.3. 这时0~N-1之间一定存在局部最小，则取中点位置M，若为极小值返回，若不是，如果M>M-1，那么0~M之间存在局部最小，一直二分即可找到。
下一篇：Webug4.0靶场通关