社区微信群开通啦，扫一扫抢先加入社区官方微信群
社区微信群
思想和写法，要会敲代码，最好会手撕代码
一定要会手撕代码、思想要清楚。
实质是分治法，选择一个基准来分，这个分的过程是partition，它是快排的灵魂。基于以上特点，用递归的方式来描述。
#include <iostream>
using namespace std;
int partition(int arr[], int left, int right) {
int key = arr[right];
int k = left;
for(int i = left; i < right; ++i) {
if(arr[i] < key) {
swap(arr[i], arr[k++]);
}
}
swap(arr[right], arr[k]);
return k;
}
void quicksort(int arr[], int left, int right) {
if(left < right) {
int i = partition(arr, left, right);
quicksort(arr, left, i-1);
quicksort(arr, i+1, right);
}
return;
}
int main() {
int arr[10] = {2, 5, 4, 3, 1, 6, 9, 7, 8, 10};
for(int i = 0; i < 10; ++i)
cout << arr[i] << " ";
cout << endl;
quicksort(arr, 0, 9);
for(int i = 0; i < 10; ++i)
cout << arr[i] << " ";
return 0;
}
一定要会手撕代码、思想要清楚。
先递归划分子问题，然后合并结果
#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& A, vector<int> L, vector<int> R) {
int l = L.size();
int r = R.size();
int i = 0;
int j = 0;
int k = 0;
while(i < l && j < r) {
if(L[i] < R[j]) {
A[k++] = L[i++];
} else {
A[k++] = R[j++];
}
}
while(i < l) A[k++] = L[i++];
while(j < r) A[k++] = R[j++];
}
void mergesort(vector<int>& arr) {
int n = arr.size();
if(n < 2) return;
int mid = n/2;
int i;
vector<int> L(mid);
vector<int> R(n - mid);
for(i = 0; i < mid; ++i) {
L[i] = arr[i];
}
for(;i < n; ++i) {
R[i-mid] = arr[i];
}
mergesort(L);
mergesort(R);
merge(arr, L, R);
}
int main() {
int arr[10] = {2, 5, 4, 3, 1, 6, 9, 7, 8, 10};
vector<int> Arr(arr, arr + 10);
for(int i = 0; i < 10; ++i)
cout << Arr[i] << " ";
cout << endl;
mergesort(Arr);
for(int i = 0; i < 10; ++i)
cout << Arr[i] << " ";
return 0;
}
从平均时间来看，快速排序是效率最高的，但快速排序在最坏情况下的时间性能不如堆排序和归并排序
稳定性算法：基数排序，插入排序，冒泡排序，归并排序
不稳定性算法：希尔排序，快速排序，选择排序，堆排序，桶排序
时间复杂度：评估执行程序所需的时间，可以估算出程序对处理器的使用程度
空间复杂度：评估执行程序所需的存储空间，可以估算出程序对计算机内存的使用程度
由5位外国人（Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan）提出，并以他们的名首字母命名，称为 中位数的中位数算法，又称 线性查找算法。
结合不同考题侧面的去考（经典：选出第k大（第k小）的元素，）
BFS：使用队列保存未被检测的结点。结点按照宽度优先的次序被访问和进出队列。类似层次遍历
DFS：一直往深处走，直到找到解或者走不下去为止（使用栈保存未被检测的结点，结点按照深度优先的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测），类似先序遍历。
总结：最短路径用广度优先搜索BFS，全部解用深度优先搜索DFS。
结合不同考题侧面的去考
因为索引是一种优化查询的数据结构，比如MySQL中的索引是B+树实现的，而B+树就是一种数据结构，可以优化查询速度，可以利用索引快速查找数据，所以能优化查询！
字段是否是查询条件或者是排序条件。适合于查询多而添删改少的表。
不可以的
数据库分为：内连接、外连接、交叉连接
有两种，显式的和隐式的，返回连接表中符合连接条件和查询条件的数据行
没有WHERE 子句，它返回连接表中所有数据行的笛卡尔积
①原子性：事务作为一个整体被执行，要么全部执行，要么全部不执行。
②一致性：保证数据库的状态从一个一致状态转变为另一个一致状态。
③隔离性：多个事务并发执行时，一个事务的执行并不影响其他事务的执行。
④持久性：一个事务一旦提交，对数据库的修改应该永久保存。
①脏读：B事务读取到了A事务尚未提交的数据。
②不可重复读：一个事务中，两次读取的数据的内容不一致。
③幻读/虚读：一个事务中，两次读取的数据的数量不一致。
读未提交、读已提交、可重复读和序列化
①读取尚未提交的数据：哪个问题都不能解决。
②读取已经提交的数据：可以解决脏读。（oracle默认）
③重读读取：可以解决脏读，不可重复读。（mysql默认）
④串行化：都可以解决。—相当于锁表，一般没人用，效率太低。
三次握手的最主要目的是确认双方都有收发数据的能力。三次握手完成两个重要的功能，既要双方做好发送数据的准备工作(双方都知道彼此已准备好)，也要允许双方就初始序列号进行协商，这个序列号在握手过程中被发送和确认。
二次握手达不到目的，四次多余。
双方关闭连接要经过双方都同意。所以，首先是客服端给服务器发送FIN，要求关闭连接，服务器收到后会发送一个ACK进行确认。服务器然后再发送一个FIN，客户端发送ACK确认，并进入TIME_WAIT状态。等待2MSL后自动关闭。
首先，MSL即Maximum Segment Lifetime，就是最大报文生存时间，是任何报文在网络上的存在的最长时间，超过这个时间报文将被丢弃。《TCP/IP详解》中是这样描述的：MSL是任何报文段被丢弃前在网络内的最长时间。RFC 793中规定MSL为2分钟，实际应用中常用的是30秒、1分钟、2分钟等。
TCP的TIME_WAIT需要等待2MSL，当TCP的一端发起主动关闭，三次挥手完成后发送第四次挥手的ACK包后就进入这个状态，等待2MSL时间主要目的是：防止最后一个ACK包对方没有收到，那么对方在超时后将重发第三次握手的FIN包，主动关闭端接到重发的FIN包后可以再发一个ACK应答包。在TIME_WAIT状态时两端的端口不能使用，要等到2MSL时间结束才可以继续使用。当连接处于2MSL等待阶段时任何迟到的报文段都将被丢弃。
从低到高分别是：物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。
OSI七层模型是一种框架性的设计方法，设计的主要目的是为了解决异种网络互联时遇到的兼容问题，主要功能就是帮助不同类型的主机实现数据传输。最大优点是将服务，协议，接口三者明确的区分开来，通过七个层次化的结构模型使得不同的主机不同的网络之间实现可靠的通讯。服务说明下一层为上一层提供什么功能，接口说明上一层如何实现下一层提供的服务，协议涉及本层如何实现自己的服务。
电缆连线连接器，网卡等。不包括具体的物理媒体。
物理层的任务就是为它的上一层提供一个物理连接，以及它们的机械、电气、功能和过程特性。如规定使用电缆和接头的类型、传送信号的电压等。在这一层，数据还没有被组织，仅作为原始的位流或电气电压处理，单位是比特。
交换机。
控制物理层和网络层之间的通讯，把网络层的数据分割成物理层可以传输的帧。
路由器。
将网络地址翻译成对应的物理地址，并决定如何将数据从发送方路由到接收方。通过综合考虑发送优先权、网络拥塞程度、服务质量以及可选路由的花费来决定从一个网络中节点Ａ 到另一个网络中节点Ｂ 的最佳路径。
最重要的一层。OSI下3层的主要任务是数据通信，上3层的任务是数据处理。而传输层（Transport Layer）是OSI模型的第4层。因此该层是通信子网和资源子网的接口和桥梁，起到承上启下的作用。协议 和 端口号 是在传输层定义的。
该层的主要任务是：定义了一些传输数据的协议和端口号（如HTTP的端口80等），TCP（传输控制协议，传输效率低，可靠性强，可以用于传输可靠性要求高，数据量大的数据），UDP（用户数据报协议，与TCP特性恰恰相反，用于传输可靠性要求不高，数据量小的数据，如QQ聊天数据就是通过这种方式传输的）。 主要是从下层接收的数据进行分段和传输，到达目的地址后再进行重组。常常把这一层数据叫做报文段
eg:电脑如何识别某一个应用程序？
通过端口号：每一个应用程序都有很多的服务，每一个服务对应着一个端口号
负责网络中两个节点之间建立和保持通信。
会话层的功能包括：建立通信链接，保持会话过程通信链接的畅通，同步两个节点之间的对话，决定通信是否被中断以及通信中断时决定从何处重新发送。
数据的传输是在会话层完成的，而不是传输层，传输层只是定义了数据传输的协议。
应用程序和网络之间的翻译官，在表示层，数据将按照网络能理解的方案进行格式化；这种格式化也因所使用网络的类型不同而不同。表示层管理数据的解密与加密，如系统口令的处理。在网络中传输需要加密数据的时候，表示层进行加密解密。对图片的编码解码也是表示层的工作。
其主要功能是“处理用户信息的表示问题，如编码、数据格式转换和加密解密”等
负责对软件提供接口以使程序能使用网络服务。术语“应用层”并不是指运行在网络上的某个特别应用程序 ，应用层提供的服务包括文件传输、文件管理以及电子邮件的信息处理。
它是计算机用户，以及各种应用程序和网络之间的接口，其功能是直接向用户提供服务，完成用户希望在网络上完成的各种工作。是最靠近用户的OSI层。这一层为用户的应用程序（例如电子邮件、文件传输和终端仿真）提供网络服务。
消息传递方式
select：内核需要将消息传递到用户空间，需要内核的拷贝动作；
poll：同上；
epoll：通过内核和用户空间共享一块内存来实现，性能较高；
文件句柄剧增后带来的IO效率问题
select：因为每次调用都会对连接进行线性遍历，所以随着FD剧增后会造成遍历速度的“线性下降”的性能问题；
poll：同上；
epoll：由于epoll是根据每个FD上的callable函数来实现的，只有活跃的socket才会主动调用callback，所以在活跃socket较少的情况下，使用epoll不会对性能产生线性下降的问题，如果所有socket都很活跃的情况下，可能会有性能问题；
支持一个进程所能打开的最大连接数
select：单个进程所能打开的最大连接数，是由FD_SETSIZE宏定义的，其大小是32个整数大小（在32位的机器上，大小是3232,64位机器上FD_SETSIZE=3264），我们可以对其进行修改，然后重新编译内核，但是性能无法保证，需要做进一步测试；
poll：本质上与select没什么区别，但是他没有最大连接数限制，他是基于链表来存储的；
epoll：虽然连接数有上线，但是很大，1G内存的机器上可以打开10W左右的连接；
综上，在选择select，poll，epoll时要根据具体的使用场合以及这三种方式的自身特点：
1、表面上看epoll的性能最好，但是在连接数少并且连接都十分活跃的情况下，select和poll的性能可能比epoll好，毕竟epoll的通知机制需要很多函数回调。
2、select低效是因为每次它都需要轮询。但低效也是相对的，视情况而定，也可通过良好的设计改善。
软件负载均衡、硬件负载均衡、DNS负载均衡。
DNS负载均衡是地理级别的，硬件负载均衡对应的是集群级别的，软件负载均衡对应的是机器级别的。
常见的软件有 LVS、 Nginx 、HAProxy 。
软件负载负载均衡又分四层和七层负载均衡，四层负载均衡就是在网络层利用IP地址端口进行请求的转发，基本上就是起个转发分配作用。而七层负载均衡就是可以根据访问用户的HTTP请求头、URL信息将请求转发到特定的主机。 LVS为四层负载均衡。Nginx、HAProxy可四可七。Nginx是万级别的，通常只用它来做七层负载，LVS来做四层负载。LVS是十万级别的，所以如果顶不住常见的也有这样的搭配：将LVS和NGINX组合起来。
就是用一个硬件一个基础网络设备，类似我们的交换机啊这样的硬件，来实现负载均衡。 常见的硬件有F5、A10。
优点：
缺点:
这个负载均衡时通过DNS来的，因为DNS解析同一个域名可以返回不同的ip。所以例如哈尔滨的人访问百度就返回距离他近的那个机房的IP，海南的人访问百度就返回距离他近的那个机房的IP。所以主要是用来实现地理级别的负载均衡。
优点:
缺点：
分页式存储管理
分页存储管理是将一个进程的地址（逻辑地址空间）空间划分成若干个大小相等的区域，称为页，相应地，将内存空间划分成与页相同大小（为了保证页内偏移一致）的若干个物理块，称为块或页框（页架）。在为进程分配内存时，将进程中的若干页分别装入多个不相邻接的块中。
分段式存储管理
在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段是一组完整的逻辑信息，如有主程序段、子程序段、数据段及堆栈段等，每个段都有自己的名字，都是从零开始编址的一段连续的地址空间，各段长度是不等的。
两者的区别：
在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。
进程：具有独立功能的程序关于某个数据集合上的一次运行活动。
线程：进程的一个实体。
比喻：一列火车是一个进程，火车的每一节车厢是线程。
（1）粒度性分析：线程的粒度小于进程。
（2）调度性分析：进程是资源拥有的基本单位，线程是独立调度与独立运行的基本单位，出了寄存器，程序计数器等必要的资源外基本不拥有其他资源。
（3）系统开销分析：由于线程基本不拥有系统资源，所以在进行切换时，线程切换的开销远远小于进程。
简单地说：同步体现的是一种协作性，互斥体现的是一种排他性。
面向对象的理解：是一种“万物皆对象”的编程思想。面向对象的编程是以对象为中心，以消息为驱动，所以程序=对象+消息。
多态：函数多态，一个接口，多种方法。（C++以虚函数）
纯虚函数：是虚函数再加上=0（如：virtual void eat()=0；）
虚函数总是在派生类中被改写，这种改写被称为“override”（覆盖）
虚函数采用一种虚调用的办法。虚调用是一种可以在只有部分信息的情况下工作的机制，特别允许我们调用一个只知道接口而不知道其准确对象类型的函数。但是如果要创建一个对象，你势必要知道对象的准确类型，因此构造函数不能为 virtual。
不行，这是因为虚函数是有代价的。由于每个虚函数的对象都必须维护一个虚函数表，因此在使用虚函数的时候会产生一个系统开销。如果仅是一个很小的类，且不派生其他类，那么根本没必要使用虚函数。
重载：编写一个与自己已有函数同名但是参数表不同的函数
重写（覆盖）：重写的函数必须有一致的参数表和返回值
如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！
