一、插入排序
介绍
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。
算法适用于少量数据的排序，时间复杂度为O(n^2)。
插入排算法是稳定的排序方法。
步骤
①从第一个元素开始，该元素可以认为已经被排序
②取出下一个元素，在已经排序的元素序列中从后向前扫描
③如果该元素（已排序）大于新元素，将该元素移到下一位置
④重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⑤将新元素插入到该位置中
⑥重复步骤2
排序演示
算法实现
二、冒泡排序
介绍
冒泡排序（Bubble Sort）是一种简单的排序算法，时间复杂度为O(n^2)。
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
原理
循环遍历列表，每次循环找出循环最大的元素排在后面；
需要使用嵌套循环实现：外层循环控制总循环次数，内层循环负责每轮的循环比较。
步骤
①比较相邻的元素。如果第一个比第二个大，就交换他们两个。
②对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
③针对所有的元素重复以上的步骤，除了最后一个。
④持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
算法实现：
三、快速排序
介绍
快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想，由C. A. R. Hoare在1962年提出。
基本思想
快速排序的基本思想是：挖坑填数 + 分治法。
首先选出一个轴值(pivot，也有叫基准的)，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
实现步骤
①从数列中挑出一个元素，称为 “基准”（pivot）；
②重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）；
③对所有两个小数列重复第二步，直至各区间只有一个数。
排序演示
算法实现
四、希尔排序
介绍
希尔排序（Shell Sort）是插入排序的一种，也是缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法，时间复杂度为：O(1.3n)。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
·插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率；
·但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位。
基本思想
①希尔排序是把记录按下标的一定量分组，对每组使用直接插入算法排序；
②随着增量逐渐减少，每组包1含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法被终止。
排序演示
算法实现
五、选择排序
介绍
选择排序(Selection sort)是一种简单直观的排序算法，时间复杂度为Ο(n2)。
基本思想
选择排序的基本思想：比较 + 交换。
第一趟，在待排序记录r1 ~ r[n]中选出最小的记录，将它与r1交换；
第二趟，在待排序记录r2 ~ r[n]中选出最小的记录，将它与r2交换；
以此类推，第 i 趟，在待排序记录ri ~ r[n]中选出最小的记录，将它与r[i]交换,使有序序列不断增长直到全部排序完毕。
排序演示
选择排序的示例动画。红色表示当前最小值，黄色表示已排序序列，蓝色表示当前位置。
算法实现
六、堆排序
介绍
堆排序（Heapsort）是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。
利用数组的特点快速指定索引的元素。
基本思想
堆分为大根堆和小根堆，是完全二叉树。
大根堆的要求是每个节点的值不大于其父节点的值，即A[PARENT[i]] >=A[i]。
在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
排序演示
算法实现
七、归并排序
介绍
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
基本思想
归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
算法思想
自上而下递归法（假如序列共有n个元素）
① 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；
② 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；
③ 重复步骤②，直到所有元素排序完毕。
自下而上迭代法
① 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
② 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
③ 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
④ 重复步骤③直到某一指针达到序列尾；
⑤ 将另一序列剩下的所有元素直接复制到合并序列尾。
排序演示
算法实现
八、基数排序
介绍
基数排序（Radix Sort）属于“分配式排序”，又称为“桶子法”。
基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m) ，其中 r 为采取的基数，而m为堆数。
在某些时候，基数排序法的效率高于其他的稳定性排序法。
基本思想
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
基数排序按照优先从高位或低位来排序有两种实现方案：
MSD（Most significant digital） 从最左侧高位开始进行排序。先按k1排序分组, 同一组中记录, 关键码k1相等,再对各组按k2排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码kd对各子组排序后. 再将各组连接起来,便得到一个有序序列。MSD方式适用于位数多的序列。
LSD （Least significant digital）从最右侧低位开始进行排序。先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。LSD方式适用于位数少的序列。
排序效果
算法实现
九、总结
各种排序的稳定性、时间复杂度、空间复杂度的总结：
平方阶O(n²)排序：各类简单排序：直接插入、直接选择和冒泡排序；
从时间复杂度来说：
线性对数阶O(nlog₂n)排序：快速排序、堆排序和归并排序；
O(n1+§))排序，§是介于0和1之间的常数：希尔排序 ；
线性阶O(n)排序：基数排序，此外还有桶、箱排序。
❷ go面试题整理（附带部分自己的解答）
原文：【 http://alblue.cn/articles/2020/07/04/1593837537036.html 】
如果有解答的不对的，麻烦各位在评论写出来~
go的调度原理是基于GMP模型，G代表一个goroutine，不限制数量；M=machine，代表一个线程，最大1万，所有G任务还是在M上圆腔执行；P=processor代表一个处理器，每一个允许的M都会绑定一个G，默认与逻辑CPU数量相等（通过runtime.GOMAXPROCS(runtime.NumCPU())设置）。
go调用过程：
可以能，也可以不能。
因为go存在不能使用==判断类型：map、slice，如果struct包含这些类型的字段，则不能比较。
这两种类型也不能作为map的key。
类似栈操作，后进先出。
因为go的return是一个非原子性操作，比如语句 return i ，实际上分两步进行，即将i值存入栈中作为返回值，然后执行跳转，而defer的执行时机正是跳转前，所以说defer执行时还是有机会操作返回值的。
select的case的表达式必须是一个channel类型，所有case都会被求值，求值顺序自上而下，从左至右。如果多个case可以完成，则会随机执行一个case，如果有default分支，则执行default分支语句。如果连default都没有，则select语句会一念纤直阻塞，直到至少有一个IO操作可以进行。
break关键字可跳出select的执行。
goroutine管理、信息传递。context的意思是上下文，在线程、协程中都有这个概念，它指的是程序单元的一个运行状态、现场、快照，包含。context在多个goroutine中是并发安全的。
应用场景：
例子参考： https://www.jianshu.com/p/6def5063c1eb
waitgroup
channel
len：切片的长度，访问时间复杂度为O(1)，go的slice底层是对数组的引用。
cap：切片的容量，扩容是以这个值为标准。默认扩容是2倍，当达到1024的长度后，按1.25倍。
扩容：每次扩容slice底层都将先分配新的容量的内存空间，再将老的数组拷贝到新的内存空间，因为这个操作不是并发安全的。所以并发进行append操作，读到内存中的老数组可能为同一个，最终导致append的数据丢失。
共享：slice的底层是对数组的引用，因此如果两个切片引用了同一个数组片段，就会形成共享底层数组。当sliec发生内存的重新分配（如扩容）时，会对共享进行隔断。详细见下面例子：
make([]Type,len,cap)
map的底层是hash table(hmap类型)，对key值进行了hash，并将结果的低八位用于确定key/value存在于哪个bucket（bmap类型）。再将高八位与bucket的tophash进行依次比较，确定是否存在。出现hash冲撞时，会通过bucket的overflow指向另一个bucket，形成一个单向链表。每个bucket存储8个键值对。
如果要实现map的橘高衫顺序读取，需要使用一个slice来存储map的key并按照顺序进行排序。
利用map，如果要求并发安全，就用sync.map
要注意下set中的delete函数需要使用 delete(map) 来实现，但是这个并不会释放内存，除非value也是一个子map。当进行多次delete后，可以使用make来重建map。
使用sync.Map来管理topic，用channel来做队列。
参考：
https://studygolang.com/articles/8231
多路归并法:
<pre class="vditor-reset" placeholder="" contenteditable="true" spellcheck="false"><p data-block="0">(1)假设有K路<a href="https://ke..com/item/%E6%95%B0%E6%8D%AE%E6%B5%81/3002243">数据流</a>，流内部是有序的，且流间同为升序或降序；
</p><p data-block="0">(2)首先读取每个流的第一个数，如果已经EOF，pass；
</p><p data-block="0">(3)将有效的k(k可能小于K)个数比较，选出最小的那路mink，输出，读取mink的下一个；
</p><p data-block="0">(4)直到所有K路都EOF。
</p></pre>
假设文件又1个G，内存只有256M，无法将1个G的文件全部读到内存进行排序。
第一步：
可以分为10段读取，每段读取100M的数据并排序好写入硬盘。
假设写入后的文件为A,B，C...10
第二步:
将A，B,C...10的第一个字符拿出来，对这10个字符进行排序，并将结果写入硬盘，同时记录被写入的字符的文件指针P。
第三步：
将刚刚排序好的9个字符再加上从指针P读取到的P+1位数据进行排序，并写入硬盘。
重复二、三步骤。
go文件读写参考：
https://www.jianshu.com/p/93772ececf65
保证排序前两个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同的排序叫稳定排序。
快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法。
基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。
参考：
https://www.jianshu.com/p/abe27f16b7b5
head只请求页面的首部。多用来判断网页是否被修改和超链接的有效性。
get请求页面信息，并返回实例的主体。
参考:
https://blog.csdn.net/ysh1042436059/article/details/80985574
https://www.jianshu.com/p/ef692148a59c
401：未授权的访问。
403: 拒绝访问。
普通的http连接是客户端连接上服务端，然后结束请求后，由客户端或者服务端进行http连接的关闭。下次再发送请求的时候，客户端再发起一个连接，传送数据，关闭连接。这么个流程反复。但是一旦客户端发送connection:keep-alive头给服务端，且服务端也接受这个keep-alive的话，两边对上暗号，这个连接就可以复用了，一个http处理完之后，另外一个http数据直接从这个连接走了。减少新建和断开TCP连接的消耗。这个可以在Nginx设置，
这个keepalive_timout时间值意味着：一个http产生的tcp连接在传送完最后一个响应后，还需要hold住keepalive_timeout秒后，才开始关闭这个连接。
特别注意TCP层的keep alive和http不是一个意思。TCP的是指：tcp连接建立后，如果客户端很长一段时间不发送消息，当连接很久没有收到报文，tcp会主动发送一个为空的报文（侦测包）给对方，如果对方收到了并且回复了，证明对方还在。如果对方没有报文返回，重试多次之后则确认连接丢失，断开连接。
tcp的keep alive可通过
net.ipv4.tcp_keepalive_intvl = 75 // 当探测没有确认时，重新发送探测的频度。缺省是75秒。
net.ipv4.tcp_keepalive_probes = 9 //在认定连接失效之前，发送多少个TCP的keepalive探测包。缺省值是9。这个值乘以tcp_keepalive_intvl之后决定了，一个连接发送了keepalive之后可以有多少时间没有回应
net.ipv4.tcp_keepalive_time = 7200 //当keepalive起用的时候，TCP发送keepalive消息的频度。缺省是2小时。一般设置为30分钟1800
修改：
可以
tcp是面向连接的，upd是无连接状态的。
udp相比tcp没有建立连接的过程，所以更快，同时也更安全，不容易被攻击。upd没有阻塞控制，因此出现网络阻塞不会使源主机的发送效率降低。upd支持一对多，多对多等，tcp是点对点传输。tcp首部开销20字节，udp8字节。
udp使用场景：视频通话、im聊天等。
time-wait表示客户端等待服务端返回关闭信息的状态，closed_wait表示服务端得知客户端想要关闭连接，进入半关闭状态并返回一段TCP报文。
time-wait作用：
解决办法：
close_wait:
被动关闭，通常是由于客户端忘记关闭tcp连接导致。
https://blog.csdn.net/yucdsn/article/details/81092679
根据业务来啊~
重要指标是cardinality（不重复数量），这个数量/总行数如果过小（趋近于0）代表索引基本没意义，比如sex性别这种。
另外查询不要使用select *，根据select的条件+where条件做组合索引，尽量实现覆盖索引，避免回表。
僵尸进程：
即子进程先于父进程退出后，子进程的PCB需要其父进程释放，但是父进程并没有释放子进程的PCB，这样的子进程就称为僵尸进程，僵尸进程实际上是一个已经死掉的进程。
孤儿进程：
一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。
子进程死亡需要父进程来处理，那么意味着正常的进程应该是子进程先于父进程死亡。当父进程先于子进程死亡时，子进程死亡时没父进程处理，这个死亡的子进程就是孤儿进程。
但孤儿进程与僵尸进程不同的是，由于父进程已经死亡，系统会帮助父进程回收处理孤儿进程。所以孤儿进程实际上是不占用资源的，因为它终究是被系统回收了。不会像僵尸进程那样占用ID,损害运行系统。
原文链接： https://blog.csdn.net/Eunice_fan1207/article/details/81387417
产生死锁的四个必要条件：
（1） 互斥条件：一个资源每次只能被一个进程使用。
（2） 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
（3） 不剥夺条件：进程已获得的资源，在末使用完之前，不能强行剥夺。
（4） 循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系。
避免方法：
https://blog.csdn.net/IT_10/article/details/97301736
端口占用：lsof -i:端口号 或者 nestat
cpu、内存占用：top
发送信号：kill -l 列出所有信号，然后用 kill [信号变化] [进程号]来执行。如kill -9 453。强制杀死453进程
git log:查看提交记录
git diff ：查看变更记录
git merge：目标分支改变，而源分支保持原样。优点：保留提交历史，保留分支结构。但会有大量的merge记录
git rebase：将修改拼接到最新，复杂的记录变得优雅，单个操作变得(revert)很简单；缺点：
git revert:反做指定版本，会新生成一个版本
git reset:重置到某个版本，中间版本全部丢失
etcd、Consul
https://www.cnblogs.com/xybaby/p/10124083.html
pprof
https://www.cnblogs.com/weiweng/p/12497274.html
http://alblue.cn/articles/2020/07/07/1594131614114.html
节省空间（非叶子节点不存储数据，相对b tree的优势），减少I/O次数（节省的空间全部存指针地址，让树变的矮胖），范围查找方便（相对hash的优势）。
explain
其他的见：
https://blog.csdn.net/chengxuyuanyonghu/article/details/61431386
runtime2.go 中关于 p 的定义： 其中 runnext 指针决定了下一个要运行的 g，根据英文的注释大致意思是说：
所以当设置 runtime.GOMAXPROCS(1) 时，此时只有一个 P，创建的 g 依次加入 P， 当最后一个即 i==9 时，加入的最后 一个 g 将会继承当前主 goroutinue 的剩余时间片继续执行，所以会先输出 9， 之后再依次执行 P 队列中其它的 g。
https://studygolang.com/articles/23333?fr=sidebar
方法一：
方法二：
[图片上传失败...(image-4ef445-1594976286098)]
方法1：to_days，返回给的日期从0开始算的天数。
方法2：data_add。向日期添加指定时间间隔
[图片上传失败...(image-b67b10-1594976286098)]
https://blog.csdn.net/itcastcpp/article/details/80462619
❸ 电子专业 面试题
我也是电子专业的，主要是考察数电模电和单片机，如果你是搞通讯设备，信号与系统和数字信号处理也要准备的，以下是我搜集的一些试题和部分答案，希望对你有帮助！
模拟电路
1、 基尔霍夫定理的内容是什么？（仕兰微电子）
基尔霍夫电流定律是一个电荷守恒定律,即在一个电路中流入一个节点的电荷与流出同一个节点的电荷相等.
基尔霍夫电压定律是一个能量守恒定律,即在一个回路中回路电压之和为零.
2、平板电容公式(C=εS/4πkd)。（未知）
3、最基本的如三极管曲线特性。（未知）
4、描述反馈电路的概念，列举他们的应用。（仕兰微电子）
5、负反馈种类（电压并联反馈，电流串联反馈，电压串联反馈和电流并联反馈）；负反馈的优点（降低放大器的增益灵敏度，改变输入电阻和输出电阻，改善放大器的线性和非线性失真，有效地扩展放大器的通频带，自动调节作用）（未知）
6、放大电路的频率补偿的目的是什么，有哪些方法？（仕兰微电子）
7、频率响应，如：怎么才算是稳定的，如何改变频响曲线的几个方法。（未知）
8、给出一个查分运放，如何相位补偿，并画补偿后的波特图。（凹凸）
9、基本放大电路种类（电压放大器，电流放大器，互导放大器和互阻放大器），优缺 点
，特别是广泛采用差分结构的原因。（未知）
10、给出一差分电路，告诉其输出电压Y+和Y-,求共模分量和差模分量。（未知）
11、画差放的两个输入管。（凹凸）
12、画出由运放构成加法、减法、微分、积分运算的电路原理图。并画出一个晶体管级的
运放电路。（仕兰微电子）
13、用运算放大器组成一个10倍的放大器。（未知）
14、给出一个简单电路，让你分析输出碰局电压的特性（就是个积分电路），并求输出端某点
的 rise/fall时间。(Infineon笔试试题)
15、电阻R和电容C串联，输入电压为R和C之间的电压，输出电压分别为C上电压和R上电压，要求制这两种电路输入电压的频谱，判断这两种电路何为高通滤波器，何为低通滤波器。当RC<< period - setup ? hold
16、时钟周期为T,触发器D1的建立时间最大为T1max，最小为T1min。组合逻辑电路最大延迟晌吵知为T2max,最小为T2min。问，触发器D2的建立时间T3和保持时间应满足什么条件.（华为）
17、给出某个一般时序电路的图，有Tsetup,Tdelay,Tck->q,还有 clock的delay,写出决定最大时钟的因素，同时给出表达式。（威盛VIA 2003.11.06 上海笔试试题）
18、说说静态、动态时序模拟的优缺点。（威盛VIA
2003.11.06 上海笔试试题）
19、一个四级的Mux,其中第二级信号为关键信号 如何改善timing。（威盛VIA2003.11.06 上海笔试试题）
20、给出一个门级的图，又给了各个门的传输延时，问关键路径是什么，还问给出输入,使得输出依赖于关键路径。（未知）
21、逻辑方面数字电路的卡诺图化简，时序（同步异步差宴消异），触发器有几种（区别，优点），全加器等等。（未知）
22、卡诺图写出逻辑表达使。（威盛VIA 2003.11.06 上海笔试试题）
____________________________________________________________
信号与系统
1、的话音频率一般为300~3400HZ，若对其采样且使信号不失真，其最小的采样频率应为多大？若采用8KHZ的采样频率，并采用8bit的PCM编码，则存储一秒钟的信号数据量有多大？（仕兰微面试题目）
2、什么耐奎斯特定律,怎么由模拟信号转为数字信号。（华为面试题）
3、如果模拟信号的带宽为 5khz,要用8K的采样率，怎么办？lucent) 两路？
4、信号与系统:在时域与频域关系。（华为面试题）
5、给出时域信号，求其直流分量。（未知）
6、给出一时域信号，要求（1）写出频率分量，（2）写出其傅立叶变换级数；（3）当波形经过低通滤波器滤掉高次谐波而只保留一次谐波时，画出滤波后的输出波形。（未知）
7、sketch 连续正弦信号和连续矩形波(都有图)的傅立叶变换 。（Infineon笔试试题）
8、拉氏变换和傅立叶变换的表达式及联系。（新太硬件面题）
____________________________________________________________
DSP、嵌入式、软件等
1、请用方框图描述一个你熟悉的实用数字信号处理系统，并做简要的分析；如果没有，也可以自己设计一个简单的数字信号处理系统，并描述其功能及用途。（仕兰微面试题目）
2、数字滤波器的分类和结构特点。（仕兰微面试题目）
3、IIR，FIR滤波器的异同。（新太硬件面题）
4、拉氏变换与Z变换公式等类似东西，随便翻翻书把如.h(n)=-a*h(n-1)+b*δ(n) a.求h(n)的z变换；b.问该系统是否为稳定系统；c.写出FIR数字滤波器的差分方程；（未知）
5、DSP和通用处理器在结构上有什么不同，请简要画出你熟悉的一种DSP结构图。（信威dsp软件面试题）
6、说说定点DSP和浮点DSP的定义（或者说出他们的区别）（信威dsp软件面试题）
7、说说你对循环寻址和位反序寻址的理解.（信威dsp软件面试题）
8、请写出【－8，7】的二进制补码，和二进制偏置码。用Q15表示出0.5和－0.5.（信威dsp软件面试题）
9、DSP的结构（哈佛结构）；（未知）
10、嵌入式处理器类型(如ARM)，操作系统种类（Vxworks,ucos,winCE,linux），操作系统
方面偏CS方向了，在CS篇里面讲了；（未知）
11、有一个LDO芯片将用于对手机供电，需要你对他进行评估，你将如何设计你的测试项目？
12、某程序在一个嵌入式系统（200M CPU，50M SDRAM）中已经最优化了，换到零一个系统
（300M CPU，50M SDRAM）中是否还需要优化？ （Intel）
13、请简要描述HUFFMAN编码的基本原理及其基本的实现方法。（仕兰微面试题目）
14、说出OSI七层网络协议中的四层（任意四层）。（仕兰微面试题目）
15、A） （仕兰微面试题目）
＃i nclude
void testf(int*p)
{
*p+=1;
}
main()
{
int *n,m[2];
n=m;
m[0]=1;
m[1]=8;
testf(n);
printf("Data v alue is %d ",*n);
}
------------------------------
B)
＃i nclude
void testf(int**p)
{
*p+=1;
}
main()
{int *n,m[2];
n=m;
m[0]=1;
m[1]=8;
testf(&n);
printf(Data v alue is %d",*n);
}
下面的结果是程序A还是程序B的？
Data v alue is 8
那么另一段程序的结果是什么？
16、那种排序方法最快? （华为面试题）
17、写出两个排序算法,问哪个好？（威盛）
18、编一个简单的求n!的程序 。（Infineon笔试试题）
19、用一种编程语言写n!的算法。（威盛VIA 2003.11.06 上海笔试试题）
20、用C语言写一个递归算法求N！；（华为面试题）
描述反馈电路的概念，列举他们的应用。
反馈，就是在电子系统中，把输出回路中的电量输入到输入回路中去。
反馈的类型有：电压串联负反馈、电流串联负反馈、电压并联负反馈、电流并联负反馈。
负反馈的优点：降低放大器的增益灵敏度，改变输入电阻和输出电阻，改善放大器的线性和非线性失真，有效地扩展放大器的通频带，自动调节作用。
电压负反馈的特点：电路的输出电压趋向于维持恒定。
电流负反馈的特点：电路的输出电流趋向于维持恒定。
3、有源滤波器和无源滤波器的区别
无源滤波器：这种电路主要有无源元件R、L和C组成
有源滤波器：集成运放和R、C组成，具有不用电感、体积小、重量轻等优点。
集成运放的开环电压增益和输入阻抗均很高，输出电阻小，构成有源滤波电路后还具有一定的电压放大和缓冲作用。但集成运放带宽有限，所以目前的有源滤波电路的工作频率难以做得很高。
数字电路
1、同步电路和异步电路的区别是什么？
同步电路：存储电路中所有触发器的时钟输入端都接同一个时钟脉冲源，因而所有触发器的状态的变化都与所加的时钟脉冲信号同步。
异步电路：电路没有统一的时钟，有些触发器的时钟输入端与时钟脉冲源相连，这有这些触发器的状态变化与时钟脉冲同步，而其他的触发器的状态变化不与时钟脉冲同步。
2、什么是"线与"逻辑，要实现它，在硬件特性上有什么具体要求？
将两个门电路的输出端并联以实现与逻辑的功能成为线与。
在硬件上，要用OC门来实现，同时在输出端口加一个上拉电阻。
由于不用OC门可能使灌电流过大，而烧坏逻辑门。
3、解释setup和hold time violation，画图说明，并说明解决办法。（威盛VIA2003.11.06上海笔试试题）
Setup/hold time是测试芯片对输入信号和时钟信号之间的时间要求。建立时间是指触发器的时钟信号上升沿到来以前，数据稳定不变的时间。输入信号应提前时钟上升沿（如上升沿有效）T时间到达芯片，这个T就是建立时间-Setup time.如不满足setup time,这个数据就不能被这一时钟打入触发器，只有在下一个时钟上升沿，数据才能被打入触发器。
保持时间是指触发器的时钟信号上升沿到来以后，数据稳定不变的时间。如果hold time不够，数据同样不能被打入触发器。
建立时间(Setup Time)和保持时间（Hold time）。建立时间是指在时钟边沿前，数据信号需要保持不变的时间。保持时间是指时钟跳变边沿后数据信号需要保持不变的时间。如果数据信号在时钟沿触发前后持续的时间均超过建立和保持时间，那么超过量就分别被称为建立时间裕量和保持时间裕量。
4、什么是竞争与冒险现象？怎样判断？如何消除？（汉王笔试）
在组合逻辑中，由于门的输入信号通路中经过了不同的延时，导致到达该门的时间不一致叫竞争。
产生毛刺叫冒险。如果布尔式中有相反的信号则可能产生竞争和冒险现象。
解决方法：一是添加布尔式的消去项，二是在芯片外部加电容。
5、名词：SRAM、SSRAM、SDRAM
SRAM：静态RAM
DRAM：动态RAM
SSRAM：Synchronous Static Random Access Memory同步静态随机访问存储器。它的一种类型的SRAM。SSRAM的所有访问都在时钟的上升/下降沿启动。地址、数据输入和其它控制信号均于时钟信号相关。这一点与异步SRAM不同，异步SRAM的访问独立于时钟，数据输入和输出都由地址的变化控制。
SDRAM：Synchronous DRAM同步动态随机存储器
6、FPGA和ASIC的概念，他们的区别。（未知）
答案：FPGA是可编程ASIC。
ASIC:专用集成电路，它是面向专门用途的电路，专门为一个用户设计和制造的。根据一个用户的特定要求，能以低研制成本，短、交货周期供货的全定制，半定制集成电路。与 门阵列等其它ASIC(Application Specific IC)相比，它们又具有设计开发周期短、设计制造成本低、开发工具先进、标准产品无需测试、质量稳定以及可实时在线检验等优点。
7、什么叫做OTP片、掩膜片，两者的区别何在？
OTP means one time program，一次性编程
MTP means multi time program，多次性编程
OTP（One Time Program）是MCU的一种存储器类型
MCU按其存储器类型可分为MASK(掩模)ROM、OTP(一次性可编程)ROM、FLASHROM等类型。
MASKROM的MCU价格便宜，但程序在出厂时已经固化，适合程序固定不变的应用场合；
FALSHROM的MCU程序可以反复擦写，灵活性很强，但价格较高，适合对价格不敏感的应用场合或做开发用途；
OTP ROM的MCU价格介于前两者之间，同时又拥有一次性可编程能力，适合既要求一定灵活性，又要求低成本的应用场合，尤其是功能不断翻新、需要迅速量产的电子产品。
8、单片机上电后没有运转，首先要检查什么？
首先应该确认电源电压是否正常。用电压表测量接地引脚跟电源引脚之间的电压，看是否是电源电压，例如常用的5V。
接下来就是检查复位引脚电压是否正常。分别测量按下复位按钮和放开复位按钮的电压值，看是否正确。
然后再检查晶振是否起振了，一般用示波器来看晶振引脚的波形，注意应该使用示波器探头的“X10”档。另一个办法是测量复位状态下的IO口电平，按住复位键不放，然后测量IO口（没接外部上拉的P0口除外）的电压，看是否是高电平，如果不是高电平，则多半是因为晶振没有起振。
另外还要注意的地方是，如果使用片内ROM的话（大部分情况下如此，现在已经很少有用外部扩ROM的了），一定要将EA引脚拉高，否则会出现程序乱跑的情况。有时用仿真器可以，而烧入片子不行，往往是因为EA引脚没拉高的缘故（当然，晶振没起振也是原因只一）。经过上面几点的检查，一般即可排除故障了。如果系统不稳定的话，有时是因为电源滤波不好导致的。在单片机的电源引脚跟地引脚之间接上一个0.1uF的电容会有所改善。如果电源没有滤波电容的话，则需要再接一个更大滤波电容，例如220uF的。遇到系统不稳定时，就可以并上电容试试（越靠近芯片越好）。
1、二极管的导通时的压降。
答：0.7V。
2、三极管的工作条件。
答：B极（基极）在有一定的电压时，发射极电压应该在0.3V以上。
3、TTL电平的电压值。
答：5V上下浮动10%，即4.5V―5.5V。
4、电路分析主要讲的是什么，或者是围绕着什么讲的？
答：两个定理，即基尔霍夫电压定理，基尔霍夫电流定理。
5、数字信号处理的实质。
答：数字算法或数学算法。通过数学或数字算法实现频谱搬移，从而达到滤
波的效果。
6、单片机总线。
答：数据总线、控制总线、地址总线。P0口为I/O口，即可以是数据线，也可以是地址线，倘若都要使用时，要用锁存器将二者分开，做地址线时，充当地址线的低8位，高8位由P2口充当。
7、晶振的接法或分类。
答：内接晶振和外接晶振。晶振与口线的距离越近越好。否则，会对其他部分造成高频干扰。
8、键盘与控制器（或者是单片机）连接时时如何工作的。
答：通过控制器（或者是单片机）对键盘扫描，即：通过键盘与控制器相连导线上的电平值来判断按下的键盘，从而判断相应的键盘值，通过中断，调用相应的中断服务子程序。一般是通过键盘的行扫描和列扫描判断键盘。
9、通信的三种解调方式。
答：调频、调相、调幅。
10、语音信号的范围和传输比特。
答：语音信号的频率为300―3400赫兹，取上限频率。一般取4000赫兹，有抽样定理可知最低抽样频率为8000赫兹，中国采用PCM编码调制，即位8段，因此传输比特为64K。（顺便提一点，中国采用的是A律，与欧洲是一样的，即13折线，日本、美国用的是u律，15折线）
11、2M带宽。
答：语音传输是64K,中国用的是30/32线路系统，64K*32=2048k,即为我们所说的2M.
12、无线传输为什么都是用的高频。
答：从客观上来说，使用的频段是已经订好的，常用的是80M―120M。从专业角度上来分析，是因为在高频段上能提供较为理想的信道，达到信息良好的传输和带宽的资源有效利用，而且这样所提供的信道带宽也比较宽。
13、CDMA技术。
答：CDMA技术是码分多址技术，是无线通讯产品和服务的新时代率先开发的、用于提供十分清晰的语音效果的数字技术。通过利用数字编码"扩谱"无线电频率技术，CDMA能够提供比其他无线技术更好的、成本更低的语音效果、保密性、系统容量和灵活性，以及更加完善的服务。
14、CDMA的工作。
答：CDMA利用扩谱技术将语音分解成数字化的小片断，然后进行编码，以区别每个电话。因而，大量的用户能够共享相同的频谱，从而大大提高系统的性能。也就是说，CDMA使无线服务提供商将更多的数字化信号挤压到一定的无线网络片断中去。
15、常用的信道复用技术。
答：频分多路复用(FDM)，时分多路复用(TDM)，频分多址 (FDMA)，时分多址(TDMA)，码分多址(CDMA)。
16、单片机对系统的滤波。
答：单片机对系统只能实现数字滤波，即通过一种数字算法对系统进行滤波。常用的有中值滤波，平滑滤波，程序滤波等
❹ 有关算法快速排序的问题
先说一下快速排序中最好的排序情况，最好的情况下，每次进行一次分区，我们会把一个序列刚好分为几近相等的两个子序列，这个情况也每次段拦递归调用的是时候也就刚好处理一半大小的滑雀子序列。这看起来其实就是一个完全二叉树，树的深度为 O(logn)，所以需要做 O(logn) 次嵌套调用。但是在同一信燃早层次结构的两个程序调用中，不会处理为原来数列的相同部分。因此，程序调用的每一层次结构总共全部需要 O(n) 的时间。所以这个算法在最好情况下的时间复杂度为 O(nlogn)。
但是将递减数据调用快速排序进行递增排序，是快速排序中情况最差的，你可以试想一下，假设每次分区后都出现子序列的长度一个为 1 一个为 n-1，这会导致我们的表达式变成：
T(n) = O(n) + T(1) + T(n-1) = O(n) + T(n-1)
这是时间复杂度就是 O(n²)。
❺ 面试官常问十大经典算法排序（用Python实现）
算法是一种与语言无关的东西，更确切地说就算解决问题的思路，就是一个通用的思想的问题。代码本身不重要，算法思想才是重中之重
我们在面试的时候总会被问到一下算法，虽然算法是一些基础知识，但是难起来也会让人非常头疼。
排序算法应该算是一些简单且基础的算法，但是我们可以从简单的算法排序锻炼我们的算法思维。这里我就介绍经典十大算法用python是怎么实现的。
十大经典算法可以分为两大类：
比较排序： 通过对数组中的元素进行比较来实现排序。
非比较排序： 不通过比较来决定元素间的相对次序。
算法复杂度
冒泡排序比较简单，几乎所有语言算法都会涉及的冒泡算法。
基本原理是两两比较待排序数据的大小 ，当两个数据的次序不满足顺序条件时即进行交换，反之，则保持不变。
每次选择一个最小（大）的，直到所有元素都被输出。
将第一个元素逐个插入到前面的有序数中，直到插完所有元素为止。
从大范围到小范围进行比较-交换，是插入排序的一种，它是针对直接插入排序算法的改进。先对数据进行预处理，使其基本有序，然后再用直接插入的排序算法排序。
该算法是采用 分治法 对集合进行排序。
把长度为n的输入序列分成两个长度为n/2的子序列，对这两个子序列分别采用归并排序，最终合并成序列。
选取一个基准值，小数在左大数在在右。
利用堆这种数据结构所设计的一种排序算法。
堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。利用最大堆和最小堆的特性。
采用字典计数-还原的方法，找出待排序的数组中最大和最小的元素，统计数组中每个值为i的元素出现的次数，对所有的计数累加，将每个元素放在新数组依次排序。
设置一个定量的数组当作空桶；遍历输入数据，并且把数据一个一个放到对应的桶里去；对每个不是空的桶进行排序；从不是空的桶里把排好序的数据拼接起来。
元素分布在桶中：
然后，元素在每个桶中排序：
取得数组中的最大数，并取得位数；从最低位开始取每个位组成新的数组；然后进行计数排序。
上面就是我整理的十大排序算法，希望能帮助大家在算法方面知识的提升。看懂之后可以去试着自己到电脑上运行一遍。最后说一下每个排序是没有调用数据的，大家记得实操的时候要调用。
参考地址：https://www.runoob.com/w3cnote/ten-sorting-algorithm.html
❻ 面试经典数据结构和算法汇总
如果说数据结构是骨架，那么算法就是灵魂。没了骨架，灵魂没有实体寄托；没了灵魂，骨架也是个空壳。两者相辅相成，缺一不可，在开发中起到了砥柱中流的作用。
现在我对各种数据结构和算法做一总结，对比一下它们的效率
1.数据结构篇
1. 如果让你手写个栈和队列，你还会写吗？
2. 开发了那么多项目，你能自己手写个健壮的链表出来吗？
3. 下次面试若再被问到二叉树，希望你能对答如流！
4. 面试还在被红-黑树虐？看完这篇轻松搞定面试官 ！
2.排序算法篇
1. 几个经典的基础排序算法，你还记得吗？
2. 手把手教你学会希尔排序，很简单！
3. 快速排序算法到底有多快？
4. 五分钟教你学会归并排序
5. 简单说下二叉树排序
6. 学会堆排序只需要几分钟
7. 图，这个玩意儿竟然还可以用来排序！
掌握了这些经典的数据结构和算法，面试啥的基本上没什么问题了，特别是对于那些应届生来说。接下来再总结一下不同数据结构和算法的效率问题，做一下对比，这也是面试官经常问的问题。
数据结构常用操作效率对比：
常用排序算法效率的对比：
关于经典的数据结构和算法，就总结到这，本文建议收藏，利用等公交、各种排队之时提升自己。这世上天才很少，懒蛋却很多，你若对得起时间，时间便对得起你。
❼ O(n) 排序算法
第一：一共多少个数？？是不是一共只有有限个数
第二：数据范围是什么闭绝？如果橡乱只有有限轿如姿歌曲之的话可以向楼上说的那样桶排
对于一般情形，O(n)是不可能的
❽ 十五道海量数据处理面试题
给定 a b 两个文件 各存放 亿个 url 每个 url 各占 字节 内存限制是 G 让你找出 a b 文件共同的 url ？
方案 可以估计每个文件安的大小为 G× = G 远远大于内存限制的 G 所以不可能将其完全加载到内存中处理 考虑采取分而治之的方法
方案 如果允许有一定的错误率 可以使用Bloom filter G内存大概可以表示 亿bit 将其中一个文件中的url使用Bloom filter映射为这 亿bit 然后挨个读取另外一个文件的url 检查是否与Bloom filter 如果是 那么该url应该是共同的url（注意会有一定的错误率）
读者反馈 @crowgns
有 个文件 每个文件 G 每个文件的每一行存放的都是用户的 query 每个文件的 query 都可能重复 要求你按照 query 的频度排序
方案
方案
一般query的总量是有限的 只是重复的次数比较多而已 可能对于所有的query 一次性就可以加入到内存了 这样 我们就可以采用trie树/hash_map等直接来统计每个query出现的次数 然后按出现次数做快速/堆/归并排序就可以了
（ 读者反馈 @店小二 原文第二个例子中 找一台内存在 G左右的机器 依次对用hash_map(query query_count)来统计每个query出现的次数 由于query会重复 作为key的话 应该使用hash_multimap hash_map不允许key重复 此反馈是否正确 待日后考证）
方案
与方案 类似 但在做完hash 分成多个文件后 可以交给多个文件来处理 采用分布式的架构来处理（比如MapRece） 最后再进行合并
有一个 G 大小的一个文件 里面每一行是一个词 词的大小不超过 字节 内存限制大小是 M 返回频数最高的 个词
方案 顺序读文件中 对于每个词x 取 然后按照该值存到 个小文件（记为）中 这样每个文件大概是 k左右 如果其中的有的文件超过了 M大小 还可以按照类似的方法继续往下分 知道分解得到的小文件的大小都不超过 M 对每个小文件 统计每个文件中出现的词以及相应的频率（可以采用trie树/hash_map等） 并取出出现频率最大的 个词（可以用含 个结点的最小堆） 并把 词及相应的频率存入文件 这样又得到了 个文件 下一步就是把这 个文件进行归并（类似与归并排序）的过程了
海量日志数据 提取出某日访问网络次数最多的那个 IP
方案 首先是这一天 并且是访问网络的日志中的IP取出来 逐个写入到一个大文件中 注意到IP是 位的 最多有 ^ 个IP 同样可以采用映射的方法 比如模 把整个大文件映射为 个小文件 再找出每个小文中出现频率最大的IP（可以采用hash_map进行频率统计 然后再找出频率最大的几个）及相应的频率 然后再在这 个最大的IP中 找出那个频率最大的IP 即为所求
在 亿个整数中找出不重复的整数 内存不足以容纳这 亿个整数
方案 采用 Bitmap（每个数分配 bit 表示不存在 表示出现一次 表示多次 无意义）进行 共需内存 ^ * bit= GB内存 还可以接受 然后扫描这 亿个整数 查看Bitmap中相对应位 如果是 变 变 保持不变 所描完事后 查看bitmap 把对应位是 的整数输出即可
方案 也可采用上题类似的方法 进行划分小文件的方法 然后在小文件中找出不重复的整数 并排序 然后再进行归并 注意去除重复的元素
海量数据分布在 台电脑中 想个办法高效统计出这批数据的 TOP
方案
（更多可以参考 第三章 寻找最小的 k 个数 以及第三章续 Top K 算法问题 的实现）
读者反馈 @QinLeopard
第 题的方法中 是不是不能保证每个电脑上的前十条 肯定包含最后频率最高的前十条呢？ 比如说第一个文件中 A( ) B( ) C( ) D( ) 第二个文件中 A( ) B( ) C( ) D( ) 第三个文件中: A( ) B( ) C( ) D( ) 如果要选Top( ) 选出来的结果是A 但结果应该是B
@July 我想 这位读者可能没有明确提议 本题目中的 TOP 是指最大的 个数 而不是指出现频率最多的 个数 但如果说 现在有另外一提 要你求频率最多的 个 相当于求访问次数最多的 个IP地址那道题 即是本文中上面的第 题 特此说明
怎么在海量数据中找出重复次数最多的一个？
方案 先做hash 然后求模映射为小文件 求出每个小文件中重复次数最多的一个 并记录重复次数 然后找出上一步求出的数据中重复次数最多的一个就是所求（具体参考前面的题）
上千万或上亿数据（有重复） 统计其中出现次数最多的钱 N 个数据
方案 上千万或上亿的数据 现在的机器的内存应该能存下 所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数 然后就是取出前N个出现次数最多的数据了 可以用第 题提到的堆机制完成
万字符串 其中有些是重复的 需要把重复的全部去掉 保留没有重复的字符串 请怎么设计和实现？
方案 这题用trie树比较合适 hash_map也应该能行
一个文本文件 大约有一万行 每行一个词 要求统计出其中最频繁出现的前 个词 请给出思想 给出时间复杂度分析
方案 这题是考虑时间效率 用trie树统计每个词出现的次数 时间复杂度是O(n*le)（le表示单词的平准长度） 然后是找出出现最频繁的前 个词 可以用堆来实现 前面的题中已经讲到了 时间复杂度是O(n*lg ) 所以总的时间复杂度 是O(n*le)与O(n*lg )中较大的哪一个
一个文本文件 找出前 个经常出现的词 但这次文件比较长 说是上亿行或十亿行 总之无法一次读入内存 问最优解
方案 首先根据用hash并求模 将文件分解为多个小文件 对于单个文件利用上题的方法求出每个文件件中 个最常出现的词 然后再进行归并处理 找出最终的 个最常出现的词
w 个数中找出最大的 个数
寻找热门查询
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来 每个查询串的长度为 字节 假设目前有一千万个记录 这些查询串的重复读比较高 虽然总数是 千万 但是如果去除重复和 不超过 百万个 一个查询串的重复度越高 说明查询它的用户越多 也就越热门 请你统计最热门的 个查询串 要求使用的内存不能超过 G
( ) 请描述你解决这个问题的思路
( ) 请给出主要的处理流程 算法 以及算法的复杂度
方案 采用trie树 关键字域存该查询串出现的次数 没有出现为 最后用 个元素的最小推来对出现频率进行排序
关于此问题的详细解答 请参考此文的第 节 第三章续 Top K 算法问题的实现
一共有 N 个机器 每个机器上有 N 个数 每个机器最多存 O(N) 个数并对它们操作 如何找到 N^ 个数中的中数？
方案 先大体估计一下这些数的范围 比如这里假设这些数都是 位无符号整数（共有 ^ 个） 我们把 到 ^ 的整数划分为N个范围段 每个段包含（ ^ ）/N个整数 比如 第一个段位 到 ^ /N 第二段为（ ^ ）/N到（ ^ ）/N … 第N个段为（ ^ ）（N ）/N到 ^ 然后 扫描每个机器上的N个数 把属于第一个区段的数放到第一个机器上 属于第二个区段的数放到第二个机器上 … 属于第N个区段的数放到第N个机器上 注意这个过程每个机器上存储的数应该是O(N)的 下面我们依次统计每个机器上数的个数 一次累加 直到找到第k个机器 在该机器上累加的数大于或等于（N^ ）/ 而在第k 个机器上的累加数小于（N^ ）/ 并把这个数记为x 那么我们要找的中位数在第k个机器中 排在第（N^ ）/ x位 然后我们对第k个机器的数排序 并找出第（N^ ）/ x个数 即为所求的中位数的复杂度是O（N^ ）的
方案 先对每台机器上的数进行排序 排好序后 我们采用归并排序的思想 将这N个机器上的数归并起来得到最终的排序 找到第（N^ ）/ 个便是所求 复杂度是O（N^ *lgN^ ）的
最大间隙问题
给定n个实数 求着n个实数在实轴上向量 个数之间的最大差值 要求线性的时间算法
方案 最先想到的方法就是先对这n个数据进行排序 然后一遍扫描即可确定相邻的最大间隙 但该方法不能满足线性时间的要求 故采取如下方法
将多个集合合并成没有交集的集合
给定一个字符串的集合 格式如 要求将其中交集不为空的集合合并 要求合并完成的集合之间无交集 例如上例应输出
( ) 请描述你解决这个问题的思路
( ) 给出主要的处理流程 算法 以及算法的复杂度
( ) 请描述可能的改进
方案 采用并查集 首先所有的字符串都在单独的并查集中 然后依扫描每个集合 顺序合并将两个相邻元素合并 例如 对于 首先查看aaa和bbb是否在同一个并查集中 如果不在 那么把它们所在的并查集合并 然后再看bbb和ccc是否在同一个并查集中 如果不在 那么也把它们所在的并查集合并 接下来再扫描其他的集合 当所有的集合都扫描完了 并查集代表的集合便是所求 复杂度应该是O(NlgN)的 改进的话 首先可以记录每个节点的根结点 改进查询 合并的时候 可以把大的和小的进行合 这样也减少复杂度
最大子序列与最大子矩阵问题
数组的最大子序列问题 给定一个数组 其中元素有正 也有负 找出其中一个连续子序列 使和最大
方案 这个问题可以动态规划的思想解决 设b[i]表示以第i个元素a[i]结尾的最大子序列 那么显然 基于这一点可以很快用代码实现
最大子矩阵问题 给定一个矩阵（二维数组） 其中数据有大有小 请找一个子矩阵 使得子矩阵的和最大 并输出这个和
lishixin/Article/program/sjjg/201405/30744
❾ X分之3.6等于3分之二节比例
排序算法第一篇-排序算法介绍
在面试中，现在无论大小公司都会有算法的。其中排序算法也是一种很常见的面试题。比如冒泡，快排等。这些，排序算法自己看了一次又一次，可是过一段时间，又忘掉了。所以，这次就把算法是怎么推导出来的，详细记录下来。看看这次多久还会忘记。
本文主要介绍排序算法的分类、时间复杂度、空间复杂。为了后面的学习做准备的。
通过本文学习，将收获到：排序算法分几类？什么是算法的时间复杂度？是怎么算出来的？什么是算法的空间复杂度？常见的时间复杂度比较。
如果这些您都已经知道了，可以不用耽误时间看了。
约定：
文中的n2表示的是n的2次方(n²),n^2也是表示n的2次方；
n3表示的是n的3次方；
n^k表示的是n的k次方；
long2n表示的是以2为底的对数。
本文出自：凯哥java(微信：kaigejava)学习Java版数据结构与算法笔记。
一：介绍
排序又称排序算法(Sort Algorithm),排序是将一组数据，依据指定的顺序进行排序的过程。
二：分类
排序的分类分为两大类
2.1：内部排序
内部排序是指将需要处理的所有数据一次性都加载到内存中进行排序的。
如：冒泡、快排等这些算法都是内部排序的
2.2：外部排序
数据量过大，无法全部加载到内存中，需要借助于外部存储进行排序的。
如：数据库中数据8个G，内存只有4个G的这种。
2.3：参加分类如下图：
三：算法的时间复杂度
3.1：分类
衡量一个程序(算法)执行时间有两种方法
3.1.1：事后统计的方法
所谓的事后统计方法，顾名思义，就是程序(算法)已经写完了，运行后得到的结果。
这种方法虽然是可行的，但是有两个问题：
①：要想对设计的算法运行的性能进行评估，需要实际运行该程序(浪费时间)；
②：运行所得的时间统计严重依赖于机器的硬件、软件等环境因为。
这种方法有个严苛的要求：要在同一台机器在相同状态(软硬件)下运行，才能比较哪个算法更快。
3.1.2：事前估算的方法
通过分析某个算法的时间复杂度来判断哪个算法更优。
3.2：时间频度
概念：一个算法花费的时间与算法中语句执行的次数成正比。哪个算法中语句执行次数多，那么这个算法所花费的时间就多(这不废话吗)。
一个算法中语句执行次数称为语句频度或时间频度。记为：T(n).
(复杂的概念是，时间频度：一个算法执行所消耗的时间，从理论上是 不能算出来的，想要具体数值，必须要将程序上机运行测试才能知道。但是我们不可能也没必要对每个算法都上机进行测试的，只需要知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句执行的次数成正比的，哪个算法中语句执行次数多，那么这个程序花费的时间就多。一个算法中的语句执行次数称为语句频度或者时间频度，即为：T(n))
例如：我们知道的技术从1到100所有数字的和。这个就有两种算法。分别如下：
①：使用for循环，从1到100循环出来，然后累加出来。代码如下：
根据上面概念(注意对概念的理解,total和end这两行相对于for循环来说，可以忽略。后面我们还会详细讲解还会忽略哪些)，我们来看下这个算法的时间频度是多少呢？
在for循环中，实际需要执行101次(+1的原因是因为，在for循环的时候，需要做最后一次判断，才能推出。因此n个数的计算一共是n+1次操作)。所以其时间频度就是：T(n)=n+1;
我们再来看看第二种算法：
是不是很简单，只要一行代码就执行完成了。所以第二种算法的T(n)=1了。是不是很快呢？
时间频度是不是一眼就看出来了？是不是不用在代码运行下来比较运行时间了？
(ps：从上面简单地从1到100求和算法中，我们是不是感受到算法的魅力了？感受到编程之美了？)
3.3：时间复杂度
在上面3.2中提到的时间频度中,n称为问题的规模，当n不断变化的时候，时间频度T(n)也会不断变化。但是有时我们想知道它在变化的时候呈现什么样的规律呢？为此，我们引入了时间复杂度概念。
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示。若有某个辅助函数f(n)，是的当n趋近于无穷大的时候，T(n)/f(n)的极限值为不等于零的参数，则称为f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))为算法的渐进的时间复杂度。简称时间复杂度。这就是大O法。
在计算时间复杂度的时候，我们会忽略以下几个数据值
3.3.1：忽略常数项
比如上面，我们计算1到100的第一种算法中，有两行int total=0；和 int end = 100;这两行代码，这个数值是2，我们一般计算时间复杂度的时候，会忽略这个常数项的。为什么呢？请看下面四个函数，随着n的增大而增大运行时间。
T(n) = 2n+20
T(n) = 2*n
T(n)=3n+10
T(n)=3*n
请看下图随着n的增大所呈现的规律：
我们来看看，把这些数据使用折线图展示：
图例说明：上面两个是3*n及3n+10的，下面两个是2n及2n+10的
从上面两个图表中我们可以得到以下结论：
①：2n+20和2*n随着n的增加，执行曲线无限接近(折线图中下面两个)，常量值20可以忽略了
②：3n+10和3*n随着n的增加，执行曲线无限接近(折线图中上面两个)，常量值10可以忽略了
所以，综上所述，在计算程序(算法)时间复杂度的时候,常量值是可以忽略的
3.3.2：忽略低次项
请看下面四个函数，随着n的增大又会呈现什么规律吗？
T(n)=2n^2+3n+10
T(n)=2n^2
T(n)=n^2+5n+20
T(n)=n^2
说明：n^2表示n的2次方
我们来看看随着n的增加，运行所消耗的时间。如下图：
把上面数据，用折线图表示，如下图：
图例说明：上面两个是2n^2及2n^2+3n+10，下面两个是n^2及 n^2+5n+20
从上面两个图中我们可以得到如下结论：
①：2n^2+3n+10和2n^2随着n的增大，执行曲线无限接近，可以忽略低次项及常量项：3n+10
②：n^2+5n+20和n^2随着n的增大，执行曲线无限接近，可以忽略低次项及常量项：5n+20
综上所述，我们可以得到结论：在计算程序(算法)时间复杂度的时候，低次项(3n=3*n^1比n^2项数少)是可以忽略的
3.3.3：忽略系数
我们再来看看下面四个函数，看看它们随着n的增大呈现出什么样的规律
T(n)=3n^2+2n
T(n)=5n^2+7n
T(n)=n^3+5n
T(n)=6n^3+4n
随着n的增加，运行时间所消耗耗时如下图：
折线图如下：
从上图可以得到如下：
①：随着n值变大，5n^2+7n和3n^2+2n，执行曲线重合，说明这种情况下，系数5和3可以忽略；
②：n^3+5n和6n^3+4n，执行曲线分离，说明多少次方是关键
3.3.4：总结：
计算时间复杂度的时候忽略常数项、忽略低次项、忽略系数
T(n)不同，但时间复杂度可能相同。
如：T(n)=n2+7n+6与T(n)=3n^2+2n+2它们的T(n)不同，但时间复杂相同，都为O(n^2).
计算时间复杂度的方法用常数1代替运行时间中的所有加法常数T(n)=n^2+7n+6 =>T(n)=n^2+7n+1修改后的运行次数函数中，只保留最高阶项T(n)=n^2+7n+1 => T（n）=n^2去除最高阶项的系数T(n)=n^2 =>T(n)=n^2 => O(n^2)
3.4：常见的时间复杂度
常数阶O(1)
对数阶O(log2n)
线性阶O(n)
线性对数阶O(nlog2n)
平方阶O(n^2)
立方阶O(n^3)
K次方阶(n^k)
指数阶O(2^n)
各个时间复杂度复杂度折线图如下图：
总结：
常见算法时间复杂度由小到大依次为：
O(1)
从上图折线图中，我们可以看出，程序(算法)尽可能的避免使用指数阶段的算法。
3.5：常见算法时间复杂度举例
3.5.1：常数阶O(1)
无论代码执行多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就是O(1)
(计算时间复杂度的时候，忽略常数项)
代码demo:
上述代码在执行的时候，消耗的时间并不是随着某个变量的增长而增长，那么无论这类代码有多长，即使有有几万几十万行，都是可以用O(1)来表示它的时间复杂度。
3.5.2：对数阶O(log2n)
代码敬上：
说明：
在while循环里面，每次都是将i*2的。n的值是固定的，所以在i乘完之后，i距离n就越来越近了。假设循环x次之后，i就大于n了，此时这个循环就退出了。也就是说2的x次方等于n了。那么x=log2n。也就是说当循环了log2n次以后，代码就结束了。因此这个代码的时间复杂度就是
O(log2n)。
O(log2n)的这个2时间上是随着代码变化的。如果i = i*3，那么时间复杂度就是O(log3n)
回顾下log的理解(这是初中知识点)：
如果a的x次方等于N（a>0,且a≠1），那么熟x就叫做以a为底的对数(logarithm)，记作x=logaN.
其中，a叫做对数的底数，N叫做真数，x叫做“以a为底N的对数”。
3.5.3：线性阶O(n)
代码如下：
说明：
这段代码，for循环里面的代码会执行n次。因此它所消耗的时间随着n的变化而变化的，因此这类代码都是可以用O(n)来表示它的时间复杂度。
3.5.4：线性对数阶O(nlogn)
代码如下：
说明：
线性对数阶O(nlogN)其实非常容易理解的。将时间复杂度为O(logn)的代码循环了N次的话，那么它的时间复杂度就是n*O(logn)，也就是O(nlogN)
3.5.5：平方阶O(n2)
代码：
说明：
平方阶O(n2)就容易理解了。如果把O(n)的代码再嵌套循环一遍，它的时间复杂度就是O(n2)，
上图中的代码起始就是嵌套了2层n循环，它的时间复杂度就是O(n*n)，即时O(n2)。如果将其中一层循环的n修改成m，那么它的时间复杂度就变成了O(m*n).
3.5.6：立方阶O(n3)、K次方阶O(n^k)
说明：参考上面的O(n2)去理解就好了。O(n3)起始就相当于是三层n循环了。其他的一次类推。
3.6：平均时间复杂度和最坏时间复杂度
平均时间复杂度：
是指所有可能的输入实例均以概率出现的情况下，该算法的运行时间
最坏时间复杂度：
是指在最坏情况下的时间复杂度称为最坏时间复杂度。一般讨论时间复杂度均是最坏情况下的时间复杂度。
这样做的原因：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限。这就保证了算法的运行时间不会比最坏情况更长了。
平均时间复杂度和最坏时间复杂度是否一致，和算法有关。具体如下图：
四：算法的空间复杂度
空间复杂度介绍
类似于时间复杂度的讨论。一个算法的空间复杂度(Space Complexity)定义为该算法所消耗的存储空间，它也是问题规模n的函数；
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用临时工作单元数与解决问题的规模n有关。它们随着n的增大而增大，当n较大的时候，将占用较多的存储单元(存储空间)。例如：在快排(快速排序)和归并排序算法就属于这种情况。
在做算法分析的时候，主要讨论的是时间的复杂度。因为从用户的使用体验上来看，更看重的是程序执行的速度的快慢。一般缓存产品(比如Redis)和技术排序算法本质就是拿空间换时间的。
下节预告：
下节我们将讲讲冒泡排序和选择排序。使用的是图解+代码一步一步推导出来演示的。欢迎大家一起学习
❿ 腾讯面试题整理及经验技巧
本人IT屌丝一枚，毕业4年，5年经验(大四在腾讯实习一年，实习生工资，工作内容同正式员工一样)。非常幸运，先后收到过腾讯、网络和阿里的offer，在这里跟大家分享下腾讯面试经验，同诸君共勉。
本人职业生涯的起点开始于腾讯，能入职腾讯其实非常偶然。09年腾讯校招的时候，在本人的学校(学校是2本就不说名字了)开宣讲会，学院很多同学都去了，因为当时对腾讯兴趣不大所以没去，当时希望去中软金蝶这样的传统软件公司。一个宿舍的兄弟要去参加腾讯校招的笔试，我作为亲友团陪他一起去。腾讯的hr很nice给了我一张笔试题和意愿表让我填。本来我想从学校北门直接坐车回家，既然来了反正也没什么事就写了，算是为以后找工作热身。腾讯面试笔试内容主要是编程基础和排序查找算法之类的题，还有用程序实现递归这样的，具体的忘记了。
笔试题感觉很简单，附加题也答上了(本人专业课学霸、其他科学渣)。答完也没检查就坐车回家了，吃饭的时候收到腾讯叫我第二天去一面的短信，刚好我爸爸妈妈在南山的同学去我家做客，就乘阿姨的顺风车回学校准备第二天的面试。
腾讯一面的面试官非常的nice也是我后来的组长，非常有人格魅力的一个人，我去的时候还特意给我倒了一杯水。腾讯面试官员主要问我了解的技术，我就介绍了下在大学期间做的C++、.Net和J2EE项目，规则引擎、财务系统、学业预警系统、爬虫引擎这些。因为完全没准备所以回忆起来有点吃力，还好面试官没有刁难，发挥还可以。问了Java的内存机制，会不会导致内存泄漏，这个答的不太好;问了下hibernate的机制和作用都回答上了，让写了下爬虫程序的核心代码和正则表达式。
一面整整面了30分钟感觉有戏，就回去好好准备2面的内容，把当年工程代码翻出来复习以免再出现忘记的尴尬。很快第二天就通知去进行技术二面。技术二面就是传说中的压力面，被好一顿虐待。项目中的问题一个没问，问的全是操作系统、数据结构的问题。还好专业都是A+，大多数题都回答上了。问了下我树转二叉树，这个小意思。还问了Java内存机制和是否会有内存泄漏什么情况下会泄漏，good这个在一面回去之后就看了，回答的完美。最后一题是问的查找QQ号。小case，写了个二分查找;他说你认为我会满意吗，我想了想又写了一个哈希查找，他说还是不满意。这个时候我已经有点小不爽了，就说不知道。在有点尴尬的气氛中结束了面试。当时觉得没戏了，有点失落。回家看了下算法导论，原来有一个极为高效的算法是二叉查找，腾讯面试，唉，人家已经提示了，但是还没想到，有点小遗憾。
过了一周收到腾讯的hr面试邀请的时候，说实话非常的意外。听说我们学校本科生全军覆没，就我一个过了2面，研究生只有3个过了2面。hr面没问什么特别的，此处不表。一周后收到腾讯的正式offer，还是有点小激动的。薪水方面超过了我的预期，但最主要的是一面的面试官看起来很厉害的样子，感觉腾讯也是一家很厉害的公司。
在腾讯干了四年，正式三年，实习一年。后来开始负责招聘，我们部门在选择求职者的时候主要看聪明程度、视野、大局观、气场等软实力。当时我负责面了一个孩子，各方面挺不错的，组长觉得也还行，但是被总监毙掉了，原因是太软不够霸气。还有一个哥们技术和基础感觉都还行，但是被组长毙掉了，原因是视野和聪明度不够。
所以准备面试腾讯的同学，建议多留意近期的互联网的最新动态，多练练表达。如果能在面试中批判一下近期腾讯的决策失误和产品缺陷，无论对错都会认为这个孩子不错，那么一定会加分的;但是也不能过了，完全说的不对还侃侃而谈会让人觉得你这个人很浮夸也是会被毙掉的。尺度的拿捏很重要。还有一点，语速快而且语气坚决目光坚毅自信的比语速慢表达不流畅的同学成功几率高。我面过一个哥们，后来他顶替了我领域负责人的位置，这是后话。他在面试的时候就非常的自信，如果问一些“弱智”问题会被他反讽，当时大家就觉得这个人很厉害，面试也很顺利，1天连续面了5面，当天就发了offer。腾讯面试，腾讯社招是电话面、技术一面、组长面、平台总监面、部门经理面、hr面。总共6面，面谈是5面。
面试的时候首先要自信，如果能做到不卑不亢其实就已经成功了一半。我感觉大多数程序员都不太自信，给人感觉有点文弱，如果你自己都对自己不自信，怎么能奢求公司对你自信呢。但是也不能太自信，自信心爆棚就是自大，面过一个2年开发经验的问他技术都不知道，就谈项目。腾讯面试，问他项目中做了什么就谈项目是什么。在我这就被毙掉了还问你们能不能开到30w，我只能让他回家等消息了。
腾讯面试题整理——并附有网友的解答，感兴趣的同学参考下
一不定项选择题(共25题，每题4分，共100分，少选、错选、多选均不得分)
1已知一棵二叉树，如果先序遍历的节点顺序是：ADCEFGHB，中序遍历是：CDFEGHAB，则后序遍历结果为：(D)
A.CFHGEBDAB.CDFEGHBAC.FGHCDEBAD.CFHGEDBA
根据先序遍历和中序遍历能唯一确定二叉树：
注意：要想唯一确定一颗二叉树，必须已知两种遍历，并且其中必须有中序，因为先序和后序不能确定左右子树，如下图所示：
从上图中我们可以看出，没有中序是不能确定一颗树的!
2下列哪两个数据结构，同时具有较高的查找和删除性能?(CD)
A.有序数组B.有序链表C.AVL树D.Hash表
数组的删除性能比较差，而链表的查找性能比较差!
3下列排序算法中，哪些时间复杂度不会超过nlogn?(BC)
A.快速排序B.堆排序C.归并排序D.冒泡排序
快排和冒泡排序在最坏情况下的时间复杂度是O(n^2);
4初始序列为18625473一组数采用堆排序，当建堆(小根堆)完毕时，堆所对应的二叉树中序遍历序列为：(A)
A.83251647
B.32851467
C.38251674
D.82351476
建立小根堆的过程如下图所示：
5当n=5时，下列函数的返回值是：(A)
intfoo(intn){
if(n<2){
returnn;
}
else
returnfoo(n-1)+foo(n-2);
}
A.5B.7C.8D.10
6S市A，B共有两个区，人口比例为3：5，据历史统计A的犯罪率为0.01%，B区为0.015%，现有一起新案件发生在S市，那么案件发生在A区的可能性有多大?(C)
A.37.5%B.32.5%C.28.6%D.26.1%
3*0.01%/(3*0.01%+5*0.015%)=28.6%
7Unix系统中，哪些可以用于进程间的通信?(ABCD)
进程间通信主要包括管道,系统IPC(包括消息队列,信号量,共享存储),SOCKET.
A.SocketB.共享内存C.消息队列D.信号量
8静态变量通常存储在进程哪个区?(C)
A.栈区B.堆区C.全局区D.代码区
栈区一般用于存储比较小的临时变量;
堆区一般用于存储比较大的临时变量;
代码区用于存储代码;
全局区用于存储全局变量，静态变量等。
9查询性能(B)
A.在Name字段上添加主键
B.在Name字段上添加索引
C.在Age字段上添加主键
D.在Age字段上添加索引
如果经常依据特定的字段搜索表或对表的记录进行排序，则可以通过创建该字段的索引来加快执行这些操作的
10IP地址131.153.12.71是一个(B)类IP地址。
A.AB.BC.CD.D
A类：0打头
B类：10打头
C类：110打头
D类：1110打头
11下推自动识别机的语言是：(C)
A.0型语言B.1型语言C.2型语言D.3型语言
参考：维基网络
12下列程序的输出是：(D)
#defineadd(a+b)a+b
intmain()
{
printf("%d\n",5*add(3+4));
return0;
}
5*3+4=19
A.23B.35C.16D.19
13浏览器访问某页面，HTTP协议返回状态码为403时表示：(B)
A找不到该页面
B禁止访问
C内部服务器访问
D服务器繁忙
14如果某系统15*4=112成立，则系统采用的是(A)进制。
A.6B.7C.8D.9
逐个带入即可：
对于6进制而言：15的十进制就是11;112的十进制就是44，11*4=44。
15某段文本中各个字母出现的频率分别是{a:4，b:3，o:12，h:7，i:10}，使用哈夫曼编码，则哪种是可能的编码：(A)
Aa(000)b(001)h(01)i(10)o(11)
Ba(0000)b(0001)h(001)o(01)i(1)
Ca(000)b(001)h(01)i(10)o(00)
Da(0000)b(0001)h(001)o(000)i(1)