左程云老师算法课笔记（一）

前言

仅记录学习笔记，如有错误欢迎指正。
最近，有点忙，也有点懈怠，还是要加油加油，共勉。

一、排序

异或 ^:

• 交换律：a^ b = b^a
• 结合律:(a^ b) ^ c = (a ^ c)^ b
  1^ 1 = 0 0^ 0=0 1^ 0=1 0^1=1 (不进位相加!)

所以交换a b 的值 可以这样写：
（前提 a b指向的内存不一样 值可以一样）
a = a^b;
b= a^b;
a= a^b;

例子：
已知一个int[] arr 里面只有一种数字出现了奇数次，其他数字都出现了偶数次，怎么找出奇数次的数字?

若是有两种数都出现了奇数次，其他数均为偶数次，，怎么找出这两组数? O(n) O(1)

思路：
(1) int eor = 0 , for循环异或数组 eor最后的值 就是一组出现奇数次的数字 偶数次的数字都为0了
(2) int eor = 0 , for循环异或数组 得到的结果 eor = a ^b ;eor 一定有一位为1
再定义 rightOne = eor &(~eor +1)，找出这个数字 最右侧的1 eor’ = 0去异或这一位不为1的数组
得到的 eor’ = a 或者 b 然后 eor ^ eor ’ = b 或者 a

代码如下：

插入排序:

O(n2) 每次和前一个数字比较 比前数小就交换

二分排序：O（logN）

拓展：

在有序数组中找一个数，二分到找到数据结束就好了；
如果在有序数据中找到一个大于等于某个数字的最左侧的数字，那就需要一直二分到结束。记录最左侧数字。
局部最小值问题：
给定一个无序数据，任意两个相邻的数字不相同，求局部最小值。

如：
求l-r里的最大值（递归方式）

归并排序：

左右比较 小的放入新数组 （外排序 两个指针 一个数据）
时间复杂度 nlogn 因为每次比较后排序后的数据都能被下次排序所使用 效率++

拓展：：
小和问题 1 3 4 2 5 小和为 0+1+1+3+1+1+3+4+2 = 16

荷兰国旗：把数组的小于 等于 大于某个数分为3个区域
思路：代码在算法篇

快速排序：

基准值随机选择 时间复杂度就是nlogn

堆排序：

大根堆：每个父节点的值都比子节点的值大，小根堆反之

heapInsert: 每一个插入的节点都与自己的父节点（i-1/2）比较，大于父节点的值则交换。O(logN)

heapify：
如果需要去除最大值，则把最后一个位置的值赋值给第一个位置，heapSize–,然后新的父节点与子节点比较大小，若是比二者中最大的小，就与最大者交换位置，直到满足大根堆。O(logN)

堆排序：

先大根堆 然后从根开始heapify O(NlogN)

题目：数据是一个几乎有序的 就是排好序移动的位置不超过k个位置，排序

小根堆就是优先级队列 PriorityQueue(java) 扩容为2n

小根堆变为大根堆：

桶排序：

例如给员工年龄排序 定义一个 0-200的数组 下标表示年龄 值表示人数 排序的结果就是
下标*人数个数的数组（只适用于不基于比较的情况 ）

基数排序：

maxbit,统计最大值有多少位

注意是相同值的相对顺序不变！！就是稳定的