漫画算法-小灰的算法之旅
魏梦舒（@程序员小灰）著
“学习算法，我们不需要死记硬背那些冗长复杂的背景知识、底层原理、指令语法......需要做的是领悟算法思想、理解算法对内存空间和性能的影响，以及开动脑筋去寻求解决问题的最佳方案。相比编程领域的其他技术，算法更纯粹，更接近数学，也更具有趣味性。” -- 作者说
看完全书，感慨良多，特别是看完最后两章，算法面试与职场应用算法部分，这是全书的精华部分，值得深入研读。同时也感慨，面试中的算法真是灵活多变，若没有广博的数学知识与计算机相关知识，光知道概念，不能深入思考，真的很难应对，真的就是山外山，云外云，永远有你不知道的。也羡慕小灰有大黄这么一个领路人，帮助他学习成长，少走弯路。工作中，算法在实际应用中也是无处不在的，比如发红包，100元如何才能均衡分配。学习，永无止境。面试结束不代表学习结束，仍需钻研深入，方能应对工作中出现的更多业务场景，更好的解决实际问题。
上篇，我记录了前三章内容的相关笔记。关于算法与数据结构相关概念及相关的时间、空间复杂度，以及基础数据结构：数组、链表、栈、队列、散列表，还有复杂数据结构：树。
本篇记录剩下几章的内容：排序算法、面试算法、职场算法。
第4章 排序算法
根据时间复杂度的不同，主流的排序算法可以分为3大类。
- 时间复杂度为O(n²)的排序算法
- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序
- 时间复杂度为O(n㏒n)的排序算法
- 快速排序
- 归并排序
- 堆排序
- 时间复杂度为线性的排序算法
- 计数排序
- 桶排序
- 基数排序
根据稳定性，分为稳定排序和不稳定排序。
如果值相同的元素在排序后仍然保持着排序前的顺序，则这样的排序算法是稳定排序。反之，为不稳定排序。
冒泡排序
一种基础的交换排序。把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置，当一个元素小于或等于右侧相邻元素时，位置不变。
一种稳定的排序，值相等的元素并不会打乱原本的顺序。
由于该排序算法的每一轮都要遍历所有元素，总共遍历（元素数据-1）轮，所以时间复杂度是O(n²)。
优化：以 {5,8,6,3,9,2，1,7} 为例，经过第6轮排序后，整个数列已然是有序的了。可排序算法仍然执行了第7轮。
优化1：利用布尔变量作为标记，如果在本轮排序中，元素有交换，则说明数列无序；如果没有元素交换，则说明数列有序，直接跳出大循环。
优化2：对数列有序区进行界定，若后面的元素实际上已经有序了，则后面的元素比较是没有意义的。在每一轮排序后，记录下最后一次元素交换的位置，该位置即为无序数列的边界，再往后就是有序区了。
function sort(arr) {
for (let i = 0; i < arr.length - 1; i++) {
// 有序标记，每一轮的初始值都是true
let isSorted = true
// 无序数列的边界，每次比较只需要比到这里为止
let sortBorder = arr.length - 1
for (let j = 0; j < sortBorder; j++) {
let tmp
if (arr[j] > arr[j + 1]) {
tmp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = tmp;
// 因为有元素进行交换，所以不是有序的，标记变为false
isSorted = false
// 把无序数列的边界更新为最后一次交换元素的位置
sortBorder = j
}
}
if (isSorted) {
break
}
}
return arr
}
// 测试
console.log(sort([3, 4, 2, 1, 5, 6, 7, 8])) // [1, 2, 3, 4, 5, 6, 7, 8]
优化3：鸡尾酒排序-元素比较和交换过程是双向的。实现：外层的大循环控制着所有排序回合，大循环内包含2个小循环，第1个小循环从左向右比较并交换元素，第2个小循环从右向左比较并交换元素。劣势：代码量增加了1倍，优势：大部分有序的场景下能发挥优势。
快速排序
同冒泡排序，也属性交换排序，不同的是，冒泡排序在每一轮只把一个元素冒泡到数列的一端，而快速排序则在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分。这种思路叫分治。
基准元素的选择及元素的交换是快速排序的核心问题。
元素的交换有两种实现方法：双边循环法、单边循环法。
// 快速排序-双边循环法-需要基准元素、左右指针
function quickSort (arr, startIndex, endIndex) {
// 递归结束条件：startIndex >= endIndex时
if (startIndex >= endIndex) {
return
}
// 得到基准元素位置
let pivotIndex = partition(arr, startIndex, endIndex)
// 根据基准元素，分成两部分进行递归排序
quickSort(arr, startIndex, pivotIndex - 1)
quickSort(arr, pivotIndex + 1, endIndex)
}
// 元素交换，双边循环法
function partition (arr, startIndex, endIndex) {
// 取第一个位置，也可以选择随机位置的元素作为基准元素
let pivot = arr[startIndex]
let left = startIndex
let right = endIndex
while (left != right) {
// 控制 right 指针比较并左移
while(left < right && arr[right] > pivot) {
right--
}
// 控制 left 指针比较并右移
while (left < right && arr[left] <= pivot) {
left++
}
// 交换 left 和 right 指针所指向的元素
if (left < right) {
let p = arr[left]
arr[left] = arr[right]
arr[right] = p
}
}
// pivot 和指针重合点交换
arr[startIndex] = arr[left]
arr[left] = pivot
return left
}
// 测试
var arr = [4, 4, 6, 5, 3, 2, 8, 1];
quickSort(arr, 0, arr.length-1)
console.log(arr)
堆排序
利用最大堆和最小堆的特性：
- 最大堆：堆顶是整个堆中最大元素
- 最小堆：堆顶是整个堆中最小元素
堆排序算法的步骤：
- 把无序数组构建成二叉树，需要从小到大排序，则构建成最大堆，需要从大到小排序，则构建成最小堆。
- 循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶。
计数排序
局限性：
- 当数列最大和最小值差距过大时，并不适合用计数排序
- 当数列元素不是整数时，也不适合用计数排序
弥补算法：桶排序
第5章 面试中的算法
问题1：如何判断链表有环
题目：有一个单向链表，链表中有可能出现“环”，如何用程序来判断该链表是否为有环链表？
应用数学中的追击问题的解决方法。环形跑道上，速度快的远动员必然会追上速度慢的运动员。
首先创建两个指针p1、p2，让它们同时指向这个链表的头节点，然后开始一个大循环，在循环体中，让指针p1每次向后移动1个节点，让指针p2每次向后移动2个节点，然后比较两个指针指向的节点是否相同，若相同，则可以判断出链表有环，若不同，则继续下一轮循环。
问题扩展：
- 如果链表有环，如何求出环的长度？
- 如果链表有环，如何求出入环节点？
问题2：最小栈的实现
题目：实现一个栈，该栈带有出栈，入栈，取最小元素3个方法。要保证这3个方法的时间复杂度都是O(n)。
技巧：利用2个栈实现
问题3：如何求出最大公约数
题目：写一段代码，求出两个整数的最大公约数，要尽量优化算法的性能。
数学知识：
- 辗转相除法，也称欧几里得算法。两个正整数a,b(a>b),它们的最大公约数等于a除以b的余数c和b的最大公约数。
- 更相减损术
最优：更相减损术结合位移
问题4：如何判断一个数是否为2的整数次幂
题目：实现一个方法，来判断一个正整数是否是2的整数次幂（如16是2的4次方，返回true；18不是2的整数次幂，返回false）。要求性能尽可能高。
计算机知识：0 和 1 按位与运算的结果是0，所以凡是2的整数次幂和它本身减1的结果进行与运算，结果都必定是0。反之，如果一个整数不是2的整数次幂，结果一定不是0！
问题4：无序数组排序后的最大相邻差
题目：有一个无序整型数组，如何求出该数组排序后的任意两个相邻元素的最大差值？要求时间和空间复杂度尽可能低。比如：
无序数组：2 6 3 4 5 10 9
排序结果：2 3 4 5 6 9 10
最大相邻差=3
思路：
- 利用计数排序的思想，先找出原数组最大值max和最小值min的区间长度k（max-min+1），以及偏移量d=min
- 创建一个长度为k的新数组Array
- 遍历原数组，每遍历一个元素，就把新数组Array对应下标的值+1。遍历结束后，Array的一部分元素值变成了1或更高的数值，一部分元素值仍然是0。
- 遍历新数组Array，统计出Array中最大连续出现0值的次数+1，即为相邻元素最大差值。
升级：利用桶排序思想
问题5：如何用栈实现队列
题目：用栈来模拟一个队列，要求实现队列的两个基本操作：入队、出队。
思路：利用两个栈，让其中一个栈作为队列的入口，负责插入新元素；另一个栈作为队列的出口，负责移除老元素。
问题6：寻找全排列的下一个数
题目：给出一个正整数，找出这个正整数所有数字全排列的下一个数。就是在一个整数所包含数字的全部组合中，找到一个大于且仅大于原数的新整数。举例：
如果输入12345，返回12354。
如果输入12354，返回12435。
如果输入12435，返回12453。
思路：为了和原数接近，需要尽量保持高位不变，低位在最小范围内变换顺序。至于变换顺序的范围大小，则取决于当前整数的逆序区域。
- 从后往前查看逆序区域，找到逆序区域的前一位，也就是数字置换的边界。
- 让逆序区域的前一位和逆序区域中大于它的最小数字交换位置。
- 把原来的逆序区域转为顺序状态。
问题7：删去k个数字后的最小值
题目：给出一个整数，从该整数中去掉k个数字，要求剩下的数字形成的新整数尽可能小。应该如何选取被去掉的数字？举例：
假设给出一个整数1593212，删去3个数字，新整数最小的情况是1212。
思路：把原整数的所有数字从左到右进行比较，如果发现某一位数字大于它右面的数字，那么在删除该数字后，必然会使该数位的值降低，因为右面比它小的数字顶替了它的位置。
问题8：如何实现大整数相加
题目：给出两个很大的整数，要求实现程序求出两个整数之和。
思路：用数组存储，数组的每一个元素，对应着大整数的每一个数位。
问题9：如何求解金矿问题
题目：很久很久以前，有一位国王拥有5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不同。例如有的金矿储量是500g黄金，需要5个工人来挖掘...
如果参与挖矿的工人总数是10。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半的金矿。要求用程序求出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
总共10名工人，200kg黄金/3人，300kg黄金/4人，350kg黄金/3人，400kg黄金/5人，500kg黄金/5人。
典型的动态规划题目，和著名的“背包问题”类似。
动态规划：把复杂的问题简化成规模较小的子问题，再从简单的子问题字底向上一步一步递推，最终得到复杂问题的最优解。
问题10：寻找缺失的整数
题目：在一个无序数组里有99个不重复的正整数，范围是1100，唯独缺少1个1100中的整数。如何求出这个缺失的整数？
看完这些题目，你心中有答案了吗？书中有图解哦
最后一章
场景1：bitmap的巧用
用户标签统计
场景2：LRU算法的应用
用户信息查询，在哈希表中缓存查询数据，提高效率，缓存数据较多后如何优化。
LRU：最近最少使用的意思。基于假设：长期不被使用的数据，在未来被用到的几率也不大。因此，当数据占用内存达到一定阈值时，移除掉最近最少被使用的数据。
场景3：A星寻路算法
“迷宫寻路”益智游戏。在迷宫游戏中，有一些小怪物会攻击主角，现在希望你给这些小怪物加上聪明的AI，让它们可以自动绕过迷宫中的障碍物，寻找到主角的所在。
场景4：如何实现红包算法
例如一个人在群里发了100块钱红包，群里有10个人一起来抢红包，每人抢到的金额随机分配。规则：
- 所有人抢到的金额之和要等于红包金额，不能多也不能少。
- 每个人至少抢到1分钱。
- 要保证红包拆分的金额尽可能分布均衡，不要出现两极分化太严重的情况。
面对这些场景，你想到如何设计与编码才能最优了吗？
总结
第1-4章，是关于算法与数据结构基础知识，算法、数据结构、数组、链表、栈、队列、树，图也是数据结构中的一种，但未被本书收纳，可能是作者认为相对于其他数据结构更复杂，也确实是。还有常见的排序算法,比如最基础的冒泡排序。
看完理论与概念，仿佛刚出大学大门，以为懂了一切。可是当踏入职场时，才知道远远不够。
第5-6章，是关于面试与职场算法，面试题详解，从暴力破解法（性能最差）到最优解（性能最优）。如何运用算法解决工作问题。
面试，考验能力的地方，决定了你是否能进入心仪职场。永远有你不知道的面试题在等着你，所能做的就是永不满足，多汲取，多学习深思，才能在面试时随机应变，过关斩将，最终进入职场。
工作，更是如此，到处都是挑战，满足现状只会落后，需要不断学习，才能满足多变的业务场景。
学无止境，方能不断接近最优。