算法笔记（一）—— 认识复杂度和简单排序算法

时间复杂度是在一个算法流程中，常数操作的数量级指标。（最差情况下的算法表现）

比较两个算法的优劣，在足够的空间下，看时间复杂度指标，若相同，需要在大数据运行下来判断两个算法的“常数项指标”。

选择排序：每次循环将待排序的所有数中最小数放到这些数开头位置，依次循环即可。

冒泡排序：每次循环通过邻近位置交换，将所有待排序数中最大数交换至数组末尾位置，依次循环即可。

异或

异或其实相当于无进位相加，并且异或操作满足结合律和交换律。

通过异或操作完成两个变量值交换：

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之间存在局部最小，一直二分即可找到。