算法♥笔记

排序算法 时间复杂度n²的排序算法

• 冒泡排序（升级版-鸡尾酒排序[钟摆式]）
• 选择排序
• 插入排序
• 希尔排序

时间复杂度n㏒n的排序算法

• 快速排序：分治法（数列在每一轮都拆分两部分，直到不可再分为止）。选一个基准元素，大的放一边，小的放另一边。“最坏n²”
  

• 归并排序

• 堆排序：需要从小到大排序，则构建成最大堆；反之最小堆；循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶。
  

时间复杂度n的排序算法

• 计数排序：利用数组下标来确定元素的正确位置（下标是值，数组值是出现次数）。

适用于一定范围内的整数排序。数组长度=max-min+1；最小值做偏移量。
如果对象（如学生成绩），需要增加一个sortedArray长度是有效人数。值就是第一数组下标（如95分在第一个计数数组是下标，在第二个就是数组值）

• 桶排序：计数排序补充，用每一个桶代表一个区间范围，里面承载一个或多个元素

桶长度=一般等于原元素长度；区间跨度=（max-min）/（桶数量-1）.元素放入桶num=（int）((array[i]-min)*(bucketNum-1)/d)。类似hashmap数组+链

• 基数排序
  

面试算法 链表中的“环”–（追及问题） n

追击方法（p1一步一步走，p2间隔走），有环p2追上p1. 时间复杂度n，空间复杂度1。

扩展问题

• 求环的长度？继续到下次回合就是环长。环长=速度差*前进次数
• 入环节点？一个在相遇点，一个回开头，每次一步，到相遇时候就是入点。D= (n-1)(S1+S2)+ S2（p2是p1距离2倍） D是到入点距离；环被相遇点划分S1与S2。

最小栈的–（增加备用栈）

每个元素入栈A，就比较栈B第一个元素大小（第一个元素必进），是否进栈。栈A出栈，比较栈B，如果相同出栈B。

最大公约数–（更相减损术升级版） log

• 辗转相除法（欧几里得算法）：两个正整数a和b（a>b），它们最大公约数等于a除以b得余数c和b之间得最大公约数。c=a%b; d=b%c一直到整除或为1为止。
• 更相减损术”（出自《九章算术》：c=a-b; d=b-c 直到差0（两个数相等）为止。

避免大整数取模，又能尽可能减少运算次数，采用在更相减损术的基础上使用移位运算。偶数a>>1 ,奇数不变。272页

为2的整数次幂 – （n&(n-1)=0） 时间复杂度1 无序数组排序后的最大相邻差 – （桶）

采用桶的算法，不需要桶内部排序，只需要记录桶内最大、最小值。0(n)

栈实现队列–（运用两个栈，交互位置） 寻找全排列的下一个数

1. 从后向前查看逆序区域，找到逆序区域的前一位，也就是数字置换的边界。
2. 让逆序区域的前一位和逆序区域中大于它的最小的数字交换位置。
3. 把原来逆序区域转为顺序状态。

12354 --> 12453 --> 12435

删去K个数字后的最小值–（运用栈，入栈，大于出栈）

把原整数的所有数字从左到右进行比较，如果发现某一个数字大于它右边的数字，剔除掉这个数字。然后继续往下执行到K次。

541270936 5与4是入栈后出栈；127，7出栈；120936

实现大整数相加–（双数组元素相加）

需要说明的是， 为两个大整数建立临时数组， 是一种直观的解决方案。 若想节省内存空间， 也可以不创建这两个临时数组

优化，拆分到可以被直接计算的程度就够了（参考BigDecimal底层）。

金矿问题、背包问题

假设5个金矿，10个工人。f(4,10)与另外一个分支+父节点谁大。

二叉树遍历是2ⁿ,采用备忘录（自顶向下）或者动态规划（自底向上）避免重复计算。原理都是创建一个集合，保存计算过的结果。er0(nw)

除了第一行，剩下行数结果都是由上一行数据推导出来的。Math.max(results[j],resultes[j-p[i-1]]+g[i-1])。当前金矿+上一个满足人数金矿数

寻找缺失的整数