程序员面试宝典

一、C++ 基础

1. 位运算

返回x二进制数中的1的个数?

while(x){
x = x&(x-1);
num++;
}

返回x,y的平均值?

res = (x&y)+((x^y)>>1);

返回绝对值?

ave = (x^y)-y;

2. 宏定义

#define MIN(A,B) ((A)<(B)?(A):(B))

3. const

3.1 const 修饰变量

int b = 100;
const int* a = &b; // 无法通过a修改b的值，但其他方法可以
int const *a = &b; // 同上
int* const a = &b; // 常量指针，必须初始化,不能改指其他，可以指非常量

3.2 const修饰成员函数

int Polic::GetY() const{ // 不会通过该函数改变成员变量，除非那个变量声明为：mutable
    return Y;
}

4. sizeof()& strlen的区别

指针	4
字符数组	字符个数+1（\0）
int数组	int个数*4
结构体A（元素的最大值小于处理器位数）	以最大元素大小为对齐单位
结构体B（元素的最大值大于处理器位数）	以处理器位数为对齐单位
class	除静态变量，虚函数，结合数据对齐, 空类、继承空类为1，虚继承为4（虚指针）
string	4

sizeof()和strlen的区别：

sizeof()	strlen()
运算符	函数
编译时计算，占内存大小	运行时计算，字符串长度
数组名不退化为指针	退化为指针
	只能用char*

字节对齐:

1. 结构体变量的首地址能被最大基本类型成员的大小整除
2. 每个成员的偏移量都是成员大小的整数倍
3. 总的大小为最快基本类型成员的整数倍

5. STL

5.1 深拷贝和浅拷贝

一个类拥有资源,在复制过程中,如果资源重新分配,则深拷贝,否则为浅拷贝.

函数的形参为常量引用类型，这样做能够避免在传参时调用拷贝构造函数；又因为 printArray() 函数不会修改任何数组元素，所以我们添加了 const 限制，以使得语义更加明确。

到底是浅拷贝还是深拷贝？

如果一个类拥有指针类型的成员变量，那么绝大部分情况下就需要深拷贝，因为只有这样，才能将指针指向的内容再复制出一份来，让原有对象和新生对象相互独立，彼此之间不受影响。如果类的成员变量没有指针，一般浅拷贝足以。

另外一种需要深拷贝的情况就是在创建对象时进行一些预处理工作，比如统计创建过的对象的数目、记录对象创建的时间等。

5.2泛型编程

5.2.1 泛型函数

template<typename T>
const T* My_find(T *array,T n,T x){
...
}

5.2.2 模板-函数指针

int jug(int a,int b){
    ...
    return a;
}
int sub(int a,int b){
    ...
    return a;
}
void test(int (*p)(int, int),int a, int b){
    int1 = (*p)(a,b);
}
int main(void ){
    ...;
    test(sub,a,b);
    ...;
}

5.3 容器

数据结构	描述	头文件
向量vector	连续存储的元素	vector
列表list	双向链表	list
双队列deque	连续存储的 指向不同元素的指针 所组成的数组	deque
集合set	红黑树，查找效率O(logN)、有序不重复，	set
多重集合multiset	可重复	set
stack	FILO	stack
queue	FIFO	queue
优先队列priority_queue		queue
映射		map

6.OOV

先基类构造,再派生类构造,先派生类析构,再基类析构

6.1 继承封装多态

继承：里氏代换原则，子类必须能够替换他们的基类

封装：开闭原则，对扩展开放，对修改关闭

多态：

6.2 空类成员函数

构造函数、析构函数、复制构造函数、赋值函数

6.4 扩展：虚函数和纯虚函数和抽象类

如果想通过基类指针访问派生类的成员函数，则需要将待访问的函数定义为虚函数。

多态又分为 编译时多态和运行时多态。
编译时多态：比如重载
运行时多态：比如重写

C++的虚函数主要作用是“运行时多态”，父类中提供虚函数的实现即为子类提供默认的函数实现。

子类可以重写父类的虚函数实现子类的特殊化。

一旦某个函数被声明成虚函数，则所有派生类中它都是虚函数。如果派生类没有覆盖其基类中某个虚函数，则该虚函数的行为类似于其他的普通成员，

动态绑定

当我们使用基类的引用（或指针）调用一个虚函数时将发生动态绑定。因为我们直到运行时才能知道到底调用了哪个版本的虚函数，可能是基类中的版本也可能是派生类中的版本，判断的依据是引用（或指针）所绑定的对象的真实类型。

6.5 重载、重写、重定义

重载overload：是函数名相同，参数列表不同。重载只是在类的内部存在。但是不能靠返回类型来判断。

重写override：也叫做覆盖。子类重新定义父类中有相同名称和参数的虚函数。

重写需要注意：

1 被重写的函数不能是static的,必须是virtual的

2 重写函数必须有相同的类型，名称和参数列表

3 重写函数的访问修饰符可以不同。例如：尽管virtual是private的，派生类中重写改写为public,protected也是可以的

为了满足里式替换原则，重写有以下三个限制：

1. 子类方法的访问权限必须大于等于父类方法；

2. 子类方法的返回类型必须是父类方法返回类型或为其子类型。

3. 子类方法抛出的异常类型必须是父类抛出异常类型或为其子类型。

重定义 (redefining)也叫做隐藏:

子类重新定义父类中有相同名称的非虚函数 ( 参数列表可以不同 ) 。

如果一个类，存在和父类相同的函数，那么，这个类将会覆盖其父类的方法，除非你在调用的时候，强制转换为父类类型。

总结：关于虚函数、纯虚函数、重写、与重定义的理解：

① 任何类，无论是基类，还是子类，都可以用关键字virtual来声明虚函数。其中，只进行了定义，没有实现，称为纯虚函数。只要有一个纯虚函数的类，就是虚类，虚类只能用于被继承，不能实例化。
② 如果用vitual声明了虚函数，同时还进行了实现，则这个类就是实类，其子类如果重新定义了同名函数，这个叫做重写
③ 如果父类没有用virtual关键字，子类还是重新定义了同名函数，则这个子类的函数就叫做重定义了，重定义后会有两个函数，这种场景下，如果用父类指针指向子类对象，无法调用到子类的函数。

6.6复制构造函数和赋值函数

复制构造函数：

MyString s1("hello");
MyString s2 = s1;

赋值函数：

MyString s1("hello");
MyString s2;
s2 = s1;//赋值

区别:

复制构造函数生成新的类对象,赋值不能;

赋值函数要先检查是不是同一个内存,而且,赋值时要先释放原来的内存

6.7 派生类的三种继承方式

公有继承、私有继承、保护继承

父类私有成员不会被继承

关键字	修饰符	作用
public	公有成员	父类成员在子类中保持原有的访问属性
private	私有成员，只能被内部访问	父类成员在子类中成为私有成员
protected	只能被内部或者继承类访问	父类成员public在子类中变成protected

6.8 多态

什么是多态?

一个接口,多种方法,接口重用

在程序运行过程中决定调用哪个函数,父对象可以以不同的方式运作,即允许将子类类型的指针赋值给父类类型的指针,使用虚函数实现.

多态的作用?

封装可以隐藏实现细节,使代码模块化

继承可以扩展已有的代码块,目的是代码重用

多态目的是接口重用,

多态举例?

TObject类中有一个虚Destroy函数,和一个非虚拟的Free函数,Free函数中调用Destroy函数,

当对任何子类调用free函数时,都会执行TObject的free函数,这个函数调用我们所使用的对象的析构函数Destroy(),保证了任何子类对象都能正确的被析构

多态的种类?

参数多态, 引用多态, 过载多态, 强制多态

虚函数的底层实现

使用虚表指针vptr和虚函数表vtbl来实现,虚函数表的首地址储存在每一个对象的起始地址之中，称为虚表指针vptr，通过虚指针和偏移量计算出虚函数的真实地址实现调用

虚函数按照其声明顺序放于表中,父类的虚函数在子类的虚函数前面,覆盖的f()函数被放到了虚表中原来父类虚函数的位置

多继承则有多个虚函数表

虚继承

虚继承将共同基类设置为虚基类，从不同途径继承来的同名数据成员在内存中就只有一个拷贝，同一个函数名也只有一个映射。从而解决了二义性问题、节省了内存，避免了数据不一致的问题。菱形问题.

虚析构函数

C++中规定：当子类对象通过一个基类指针被删除时，而该基类带有一个非虚的析构函数时，其结果会出现未定义。

实际执行过程中，通过发生的情况是子类对象中仅销毁了基类成分，而子类成分并没有被销毁，从而出现一个“局部销毁”对象，造成内存泄漏。

解决方法：给基类中的析构函数增加virtual关键字修饰，使其成为虚析构函数。这样子类就允许拥有自己的析构函数，从而保证被占用的所有资源都会被释放。

实现多态的基类析构函数一般被声明成虚函数，如果不设置成虚函数，在析构的过程中只会调用基类的析构函数而不会调用派生类的析构函数，从而可能造成内存泄漏。

抽象类

如果一个类从抽象类派生而来，它必须实现了基类中的所有纯虚函数，才能成为非抽象类，否则仍然为抽象类。

抽象类和虚析构函数的完美结合

对于抽象类(abstract class)，抽象类是包含至少一个纯虚函数的类(pure virtual function)，不能被实例化，只能通过指针来操作，是纯粹被用来当做多态基类的。因为多态基类需要有虚析构函数，抽象类又需要有纯虚函数，那么在抽象类中就要把析构函数声明为纯虚函数。

注意：你必须为这个纯虚的析构函数提供一个定义。这是因为析构函数的运行机制是：最深层的子类中的析构函数最先被调用，然后在再调用基类中的析构函数。因此，编译器会在AWSL的子类的析构函数中创建一个对~AWSL的调用动作，所以必须为这个纯虚的析构函数提供一个定义。否则，链接器会报错。

class AWSL{
public:
  virtual ~AWSL() =0;     // 声明纯虚函数
};
AWSL::~AWSL(){}                     // 基类的析构函数要有一个空的定义

C++中为多态基类声明虚析构函数

6.9 初始化列表

class fruit{
public:
    fruit(int x,int y):a(x),b(y){} // 初始化列表
private:
    int a;
    int b;
};

只能用初始化列表的情况:

1. 类中含有const,引用时
2. 基类
3. 成员类型没有默认构造函数的类

6.10空类的成员函数

默认构造函数

拷贝构造函数

析构函数

赋值运算符

取址和取址函数

7. 智能指针

所有的智能指针类（包括 std::unique_ptr）均包含于头文件 <memory> 中。

std::unique_ptr、std::shared_ptr 和 std::weak_ptr

std::unique_ptr 禁止复制语义，为了达到这个效果，std::unique_ptr 类的拷贝构造函数和赋值运算符（operator =）被标记为 delete。但可以移动构造和移动赋值,执行完成后变为空指针

内存空间: std_unique_ptr 的大小总是和原始指针大小一样，std::shared_ptr 和 std::weak_ptr 大小是原始指针的一倍。

智能指针的作用是防止忘记调用delete释放内存和程序异常的进入catch块忘记释放内存。

//初始化
#include <iostream>
#include <memory>

int main() {
    {
        int a = 10;
        std::shared_ptr<int> ptra = std::make_shared<int>(a);
        std::shared_ptr<int> ptra2(ptra); //copy
        std::cout << ptra.use_count() << std::endl;

        int b = 20;
        int *pb = &a;
        //std::shared_ptr<int> ptrb = pb;  //error
        std::shared_ptr<int> ptrb = std::make_shared<int>(b);
        ptra2 = ptrb; //assign
        pb = ptrb.get(); //获取原始指针

        std::cout << ptra.use_count() << std::endl;
        std::cout << ptrb.use_count() << std::endl;
    }
}

#include <iostream>
#include <memory>

int main() {
    {
        std::unique_ptr<int> uptr(new int(10));  //绑定动态对象
        //std::unique_ptr<int> uptr2 = uptr;  //不能賦值
        //std::unique_ptr<int> uptr2(uptr);  //不能拷貝
        std::unique_ptr<int> uptr2 = std::move(uptr); //轉換所有權
        uptr2.release(); //释放所有权
    }
    //超過uptr的作用域，內存釋放
}

weak_ptr像旁观者那样观测资源的使用情况。使用weak_ptr的成员函数use_count()可以观测资源的引用计数，另一个成员函数expired()的功能等价于use_count()==0,但更快，表示被观测的资源(也就是shared_ptr的管理的资源)已经不复存在。

weak_ptr可以使用一个非常重要的成员函数lock()从被观测的shared_ptr获得一个可用的shared_ptr对象， 从而操作资源。

#include <iostream>
#include <memory>

int main() {
    {
        std::shared_ptr<int> sh_ptr = std::make_shared<int>(10);
        std::cout << sh_ptr.use_count() << std::endl;

        std::weak_ptr<int> wp(sh_ptr);
        std::cout << wp.use_count() << std::endl;

        if(!wp.expired()){
            std::shared_ptr<int> sh_ptr2 = wp.lock(); //get another shared_ptr
            *sh_ptr = 100;
            std::cout << wp.use_count() << std::endl;
        }
    }
    //delete memory
}

循环引用的解决

#include <iostream>
#include <memory>

class Child;
class Parent;

class Parent {
private:
    //std::shared_ptr<Child> ChildPtr;
    std::weak_ptr<Child> ChildPtr;
public:
    void setChild(std::shared_ptr<Child> child) {
        this->ChildPtr = child;
    }

    void doSomething() {
        //new shared_ptr
        if (this->ChildPtr.lock()) {

        }
    }

    ~Parent() {
    }
};

class Child {
private:
    std::shared_ptr<Parent> ParentPtr;
public:
    void setPartent(std::shared_ptr<Parent> parent) {
        this->ParentPtr = parent;
    }
    void doSomething() {
        if (this->ParentPtr.use_count()) {

        }
    }
    ~Child() {
    }
};

int main() {
    std::weak_ptr<Parent> wpp;
    std::weak_ptr<Child> wpc;
    {
        std::shared_ptr<Parent> p(new Parent);
        std::shared_ptr<Child> c(new Child);
        p->setChild(c);
        c->setPartent(p);
        wpp = p;
        wpc = c;
        std::cout << p.use_count() << std::endl; // 2
        std::cout << c.use_count() << std::endl; // 1
    }
    std::cout << wpp.use_count() << std::endl;  // 0
    std::cout << wpc.use_count() << std::endl;  // 0
    return 0;
}

实现一个智能指针

1 #include <iostream>
 2 #include <memory>
 3 
 4 template<typename T>
 5 class SmartPointer {
 6 private:
 7     T* _ptr;
 8     size_t* _count;
 9 public:
10     SmartPointer(T* ptr = nullptr) :
11             _ptr(ptr) {
12         if (_ptr) {
13             _count = new size_t(1);
14         } else {
15             _count = new size_t(0);
16         }
17     }
18 
19     SmartPointer(const SmartPointer& ptr) {
20         if (this != &ptr) {
21             this->_ptr = ptr._ptr;
22             this->_count = ptr._count;
23             (*this->_count)++;
24         }
25     }
26 
27     SmartPointer& operator=(const SmartPointer& ptr) {
28         if (this->_ptr == ptr._ptr) {
29             return *this;
30         }
31 
32         if (this->_ptr) {
33             (*this->_count)--;
34             if (this->_count == 0) {
35                 delete this->_ptr;
36                 delete this->_count;
37             }
38         }
39 
40         this->_ptr = ptr._ptr;
41         this->_count = ptr._count;
42         (*this->_count)++;
43         return *this;
44     }
45 
46     T& operator*() {
47         assert(this->_ptr == nullptr);
48         return *(this->_ptr);
49 
50     }
51 
52     T* operator->() {
53         assert(this->_ptr == nullptr);
54         return this->_ptr;
55     }
56 
57     ~SmartPointer() {
58         (*this->_count)--;
59         if (*this->_count == 0) {
60             delete this->_ptr;
61             delete this->_count;
62         }
63     }
64 
65     size_t use_count(){
66         return *this->_count;
67     }
68 };
69 
70 int main() {
71     {
72         SmartPointer<int> sp(new int(10));
73         SmartPointer<int> sp2(sp);
74         SmartPointer<int> sp3(new int(20));
75         sp2 = sp3;
76         std::cout << sp.use_count() << std::endl;
77         std::cout << sp3.use_count() << std::endl;
78     }
79     //delete operator
80 }

8. 类型转换

RTTI

RTTI(Run-Time Type Information)运行时类型检查的英文缩写，它提供了运行时确定对象类型的方法。

typeid:利用 运算符 typeid 可以获取与某个对象关联的运行时类型信息

#include <typeinfo> // typeid 需要的头文件
　void menu::build(const File * pfile)
　{
　　if (typeid(*pfile)==typeid(TextFile))
　　{
　　add_option("edit");
　　}
　　else if (typeid(*pfile)==typeid(MediaFile))
　　{
　　add_option("play");
　　}
　}

dynamic_cast 常用于从多态编程基类指针向派生类指针的向下类型转换

void menu::build(const File * pfile)

{
　　if (dynamic_cast <MediaFile *> (pfile))
　　{
　　// pfile 是 MediaFile 或者是MediaFile的派生类 LocalizedMedia
　　add_option("play");
　　}
　　else if (dynamic_cast <TextFile*> (pfile))
　　{
　　// pfile 是 TextFile 或者是 TextFile 的派生类
　　add_option("edit");
　　}
}

1、static_cast

父类和子类指针之间的转换。如果父类指针指向一个对象，此时将父类指针转换为子类指针是不安全的，子类指针转换为父类指针是安全的。

static_cast 不能进行无关类型转换（如非基类和子类）

2、dynamic_cast

dynamic_cast 只能用于对象指针之间的转换，

在类层次间进行上行转换时，dynamic_cast 和 static_cast 的效果是一样的；是安全的。

在进行下行转换时，dynamic_cast 具有类型检查的功能，比 static_cast 更安全。

注：父子类指针之间转换时，该父类中必须包含一个虚函数。

3、const_cast

去掉类型的 const 或者 volatile 属性，将 const 类型的指针变为非 const 类型的指针。

4、reinterpret_cast

一般用在函数指针类型之间进行转换。

10.内存分配

堆\栈\静态区\常量区\代码区

const char str1[] = "abc";
const char str2[] = "abc";
const char* str3 = "abc";
const char* str4 = "abc";
//str1!=str2,str3 == str4

堆栈的区别:

堆:动态分配,分配方式类似于链表

栈:静态的,函数调用时的参数,{}内的变量,内存有限

11.优先级

符号运算符>>单目运算符>>算术>>移位运算>>关系运算符>>逻辑运算符>>三目运算符

12.new/delete和malloc/free的区别

1. new自动计算字节数,malloc需要手动计算

2. new返回对应类型的指针,malloc返回空类型指针

3. new会进行类型检查,malloc不会

4. new分配空间+构造,malloc分配空间

5. malloc需要stdlib.h的支持

13.指针和引用的区别

• 指针在声明时可以暂时不初始化,指针在生命周期内随时都可能是空指针，所以在每次使用时都要做检查，防止出现空指针异常问题，而引用却不需要做检查，因为引用永远都不会为空，它一定有本体，一定得代表某个对象，引用在创建的同时必须被初始化。

• 指针存放的是地址，指针可以被重新赋值，可以在初始化时指向一个对象，在其它时刻也可以指向另一个对象，而引用非常专一，它会从一而终，它总是指向它最初代表的那个对象。

野指针:free(p),后p没有让p指向null

14. 函数调用有哪几种方式

cdecl:C/C++的默认调用方式,调用方维护传送参数的内存栈

_stdcall:被调用方维护,但如果可变参数来说,会自动变回cdecl

_thiscall:类的非静态成员函数的调用约定,被调用方维护,this指针存放在CPU寄存器上,不在堆栈上

_fastcall:实参直接存放在CPU寄存器上,所以不存在入栈出栈和栈释放

15.strcpy和memcpy的区别:

strcpy(a,b);//b+i->a+i,直到b+i=='\0'
memcpy(a,b,c);//b开始的c个字节复制到a

16. 编译和链接

一个C++程序从源码到exe，大致可以分为四个部分，分别为预处理，编译，汇编和链接，这四个流程由一个叫GCC（GNU Compiler Collection，GNU编译器套件）的编译器驱动程序执行操作。这四个流程共同组成了编译系统（compilation system）

预处理器是在真正的编译开始之前由编译器调用的独立程序。预处理器可以删除注释、包含其他文件以及执行宏（宏macro是一段重复文字的简短描写）替代。

编译本质上是个翻译过程，即将高级语言翻译成低级语言的过程。

从中间代码到目标程序，即是汇编器（as）要做的部分。这个阶段中，编译器会将标准的语言集合转换成特定CPU指令集的语言集合。

链接是将各种代码和数据片段收集并组合成为一个单一文件的过程。

链接器有两个步骤

• 重定位

• 解析引用

当执行链接时，会将多个文件的相同段布局放置到同一个部分，如图示，此为重定位

放置之后，引用的库就存在了具体地址，此时就会将之前暂时填补的伪地址重定位为实际地址，此为解析引用

二、数据结构与算法

1. 排序算法

十大经典排序算法可以分为两大类：
0、非线性时间排序：通过比较来决定元素间的相对次序。时间复杂度最快为O(logN)
1、线性时间排序：通过创建有序的空间，将元素按照一定的规则放入有序空间，再依次取出。以空间来换取时间，可以突破O(logN)

• 非线性时间排序
  1. 比较排序
     • 冒泡排序
     • 快速排序
  2. 插入排序
     • 插入排序
     • 希尔排序
  3. 选择排序
     • 选择排序
     • 堆排序
  4. 归并排序
     • 二路归并排序
     • 多路归并排序
• 线性时间排序
  1. 计数排序
  2. 堆排序
  3. 基数排序

[图片上传失败...(image-ce345a-1595293109591)]

思考一个排序时候，考虑时间复杂度中的指标和常数项，空间复杂度，稳定性.

代码规模，一定程度上说明了常数项的大小。（最终常数项的大小是看发生常数操作的次数）

系统的sort 方法，发现传进来的值为数值型，会使用快排，如果发现传的还有比较器，会使用归并排序

归并和快排哪种更快？
快排比归并排序的常数项要低，所以要快。

为什么会有归并和快排两种呢？
在比较的时候，使用比较器的时候，要追求一个稳定性，使用 归并排序 可以达稳定性的效果；使用快排不能够实现稳定性的效果

面对大规模的时候，当排序量是小于等于60的时候，sort方法 会在内部使用插入排序的方法（不一定是60，是一定的规模）当数据量很低的时候，插入排序的常数项低。

1、冒泡排序

比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
重复步骤1~3，直到排序完成。

for (int i = 1 ; i<length; i++) { // i = 1...len-1
        for (int j = 0 ; j<length - i; j++) { // j = 0...len-i-1
            if(arr[j]>arr[j+1]){ //j>j+1
                exchangee(arr, j, j+1);
            }
        }
    }

/*
        如果用一个flag来判断一下，当前数组是否已经有序,
      有序就退出循环，可以提高冒泡排序的性能。
*/
    for (int i = 1; i<length; i++) {
        bool flag = true;
        for (int j = 0; j < length -i; j++) {
            if (arr[j]>arr[j+1]) {
                exchangee(arr, j, j+1);
                flag  =false;
            }
        }
        if (flag) {
            break;
        }
    }

2、快速排序

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法流程如下：
从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

作者：opooc
链接：https://www.nowcoder.com/discuss/85719?type=5&order=4&pos=4&page=1?from=%20GZHhljdx
来源：牛客网

int* separate(int arr[],int left,int right){
    int first  = left -1;
    int Second = right;
    while (left < Second) {
        if(arr[left]<arr[right]){
            exchangee(arr, ++first, left++);
        }else if(arr[left]>arr[right]){
            exchangee(arr, --Second, left);
        }else if(arr[left]==arr[right]){
            left++;
        }
    }
    exchangee(arr, Second, right);
    int firstAndSecond[2] = {first+1,Second};
 
    return firstAndSecond;
}
 
void quickSort(int arr[],int left, int right){
    if (left<right) {
        int randomC = (int)((rand()%100/(double)100) * (right - left +1));//产生各随机数
        exchangee(arr,left+ randomC, right); // 和最右交换
        int* curArr  = separate(arr, left, right); // 分离
        quickSort(arr, left,curArr[0] -1 );
        quickSort(arr, curArr[1]+1, right);
    }
}
void quickSort(int arr[],int length){
    if (length < 2) {
        return;
    }
    quickSort(arr,0,length-1);
}
int main(){
    int arr[9]={99,11,72,62,53,4,44,21,14};
    int length = len(arr);
    quickSort(arr,length);
return 0;
}

3、插入排序

一般来说，插入排序都采用in-place在数组上实现。具体算法流程如下：
从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。

作者：opooc
链接：https://www.nowcoder.com/discuss/85719?type=5&order=4&pos=4&page=1?from=%20GZHhljdx
来源：牛客网

//方法一、在对比的时候不交换；
    for (int i =1; i < length;i++ ) {
        int current = arr[i];
        int preIndex = i-1;
        while (preIndex >= 0&& arr[preIndex]>current) {
            /*
            可以直接交换。因为current记录了最后一个值，
            所以这里使用向后移动思想。
            exchangee(arr, preIndex, current);
            */
            arr[preIndex+1] = arr[preIndex];
            preIndex --;
        }
        arr[preIndex+1] = current;
    }
     //方法二、在对比的时候进行交换；
    for(int i = 1 ; i<length ;i++){
        for (int j = i - 1; j>=0 && arr[j]>arr[j+1]; j--) {
            exchangee(arr, j, j+1);
        }
    }

4、希尔排序

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法流程：
选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

作者：opooc
链接：https://www.nowcoder.com/discuss/85719?type=5&order=4&pos=4&page=1?from=%20GZHhljdx
来源：牛客网

/*
    (又称缩小增量排序)
    通过实验，大量本表现出，平均时间复杂度为N^1.3
*/
    int gap = length;
    while (gap>1){
        gap = gap/3 +1;
        for (int i = gap; i<length; i+=gap) {
            int current = arr[i];
            int preIndex = i - gap;
            while (preIndex >= 0 && arr[preIndex]>current) {
                arr[i]  = arr[preIndex];
                preIndex -= gap;
            }
            arr[preIndex+gap] = current;
        }
    }

5、选择排序

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法流程如下：
初始状态：无序区为R[1..n]，有序区为空；
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
n-1趟结束，数组有序化了。

作者：opooc
链接：https://www.nowcoder.com/discuss/85719?type=5&order=4&pos=4&page=1?from=%20GZHhljdx
来源：牛客网

for(int i =0 ;i<length-1;i++)
    {   int minIndex =i;
        for(int j= i+1;j<length;j++){
 
            if(arr[minIndex]>arr[j]){
                minIndex = j;
            }
        }
        exchangee(arr, minIndex, i);
    }

6、堆排序

作者：opooc
链接：[https://www.nowcoder.com/discuss/85719?type=5&order=4&pos=4&page=1?from=%20GZHhljdx](https://www.nowcoder.com/discuss/85719?type=5&order=4&pos=4&page=1?from= GZHhljdx)
来源：牛客网

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

作者：opooc
链接：https://www.nowcoder.com/discuss/85719?type=5&order=4&pos=4&page=1?from=%20GZHhljdx
来源：牛客网

/*
        堆的概念：对于大根堆，其子树下的所有节点，
     包括它自己在内的最大值为头结点。
        时间复杂度为0+log1+log2+……数学上可以证明
     这个值收敛于O(N)
*/
//向上走
void heapInsert(int arr[],int index){
    while (arr[index] > arr[(index-1)/2]) {
        exchangee(arr,index, (index-1)/2);
        index = (index -1)/2;
    }
}
//向下走
//size为最右的边界，size是取不到的.
void heapify(int arr[],int index ,int size){
    int leftChild = index*2 + 1;
    while (leftChild < size) {
        int maxChild = leftChild + 1 < size && arr[leftChild+1] >arr[leftChild] ? leftChild+1 : leftChild;
        int maxAll = arr[maxChild] > arr[index] ? maxChild: index;
        if (maxAll  == index) {
            break;
        }
        exchangee(arr, maxAll, index);
        index = maxAll;
        leftChild = index*2 +1;
    }
}  
int main(){
    for(int i = 0;i <length;i++){
        heapInsert(arr, i);
    }
    int size = length;
    exchangee(arr, 0, --size);
    while (size > 0){
        //heapify时间复杂度为O(logN)
        heapify(arr, 0, size);
        exchangee(arr, 0, --size);
    }
 
    return 0;
}

7、归并排序

找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对所有的计数累加(从桶中的第0个元素开始，每一项和前一项相加);
反向填充目标数组：将每个元素i放在新数组的第C(i)项,
每放一个元素就将C(i)减去1，是为了保证算法的稳定性。

作者：opooc
链接：https://www.nowcoder.com/discuss/85719?type=5&order=4&pos=4&page=1?from=%20GZHhljdx
来源：牛客网

/*    输入的元素是 n 个 0到 k 之间的整数
      当k不是很大并且序列比较集中时，计数排序是一个很有效的
   排序算法。
      下面算法是输入的数组中的最小值大于等于0的情况，
   可以根据需求更改。   
  */
 
void countSort(int arr[] ,int length){
    int max = arr[0];
    int lastIndex=  0;
    for (int i = 1; i<length; i++) {
        max = arr[i]>max ? arr[i]:max;
    }
    int* sortArr  = new int[max+1]();
    for (int j = 0; j< length; j++) {
        sortArr[arr[j]]++;
    }
    for (int k = 0; k<max+1; k++) {
        while (sortArr[k]>0) {
            arr[lastIndex++] = k;
            sortArr[k]--;
        }
    }
}

8、计数排序

找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对所有的计数累加(从桶中的第0个元素开始，每一项和前一项相加);
反向填充目标数组：将每个元素i放在新数组的第C(i)项,
每放一个元素就将C(i)减去1，是为了保证算法的稳定性。

作者：opooc
链接：https://www.nowcoder.com/discuss/85719?type=5&order=4&pos=4&page=1?from=%20GZHhljdx
来源：牛客网

/*    输入的元素是 n 个 0到 k 之间的整数
      当k不是很大并且序列比较集中时，计数排序是一个很有效的
   排序算法。
      下面算法是输入的数组中的最小值大于等于0的情况，
   可以根据需求更改。   
  */
 
void countSort(int arr[] ,int length){
    int max = arr[0];
    int lastIndex=  0;
    for (int i = 1; i<length; i++) {
        max = arr[i]>max ? arr[i]:max;
    }
    int* sortArr  = new int[max+1]();
    for (int j = 0; j< length; j++) {
        sortArr[arr[j]]++;
    }
    for (int k = 0; k<max+1; k++) {
        while (sortArr[k]>0) {
            arr[lastIndex++] = k;
            sortArr[k]--;
        }
    }
}

9、桶排序

设置一个定量的数组当作空桶；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶进行排序；
从不是空的桶里把排好序的数据拼接起来。

作者：opooc
链接：https://www.nowcoder.com/discuss/85719?type=5&order=4&pos=4&page=1?from=%20GZHhljdx
来源：牛客网

//桶排序是: 桶思想排序 + 一个普通的排序（常用快速排序）
#pragma mark bucketSort
 
/*
     映射函数getGroupCount是得到在第几个桶，其能保证第一
  个桶有整个数组的最小值和最后一个桶有整个数组的最大值。
*/
int getGroupCount(long num,long size ,long min ,long max ){
    int count = (int)((size)*(num - min)/(max - min));
    return count;
}
//size  为一个桶的囊括的数的范围
void bucketSort(int arr[],int length,int size){
    if (length < 2 ){
        return;
    }
    int len = length;
    //拿到最大最小值
    long min = arr[0];
    long max = arr[0];
    for (int i = 1 ; i<len; i++) {
        min = arr[i] < min ? arr[i]: min;
        max = arr[i] > max ? arr[i]: max;
    }
    //如果最小值等于最大值说明数组中就一种数
    if (min == max) {
        return;
    }
    //创建桶
    int bucketCount = (int)((max -min)/size +1);
    vector<vector<int>> bucket(bucketCount);
    int bid = 0;
    //把数组中的数 扔进桶里
    for (int i =0;  i < len; i++) {
 
        bid = getGroupCount(arr[i], bucketCount, min, max);
        bucket[bid].push_back(arr[i]);
    }
    for (int i=0; i< bucketCount; i++) {
        //对桶内进行插入排序。按照升序，这样可以保证从下往上读的稳定性
        for (int j = 1; j<bucket[i].size(); j++) {
            if  (bucket[i][j] < bucket[i][j-1]) {
                swap(bucket[i][j],bucket[i][j-1]);
            }
        }
        for (int t = 0; t< bucket[i].size(); t++) {
            cout<<bucket[i][t]<<' ';
        }
 
    }
    //    int *newArr = new int[len];
    int index = 0;
    for (int i =0 ;i<bucketCount ;i++){
        for (int j =0; j<bucket[i].size(); j++) {
            arr[index++] = bucket[i][j];
        }
    }   
}

10、基数排序

取得数组中的最大数，并取得位数；
arr为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序（利用计数排序适用于小范围数的特点）；

作者：opooc
链接：https://www.nowcoder.com/discuss/85719?type=5&order=4&pos=4&page=1?from=%20GZHhljdx
来源：牛客网

//拿到传入数的位数
int getRadixCount(int count){
    int num = 1;
    if (count /10 >0) {
        num ++;
    }
    return num;
}
//拿到10的传入位数的次方(10^num)
int getTenRadixCount(int radixCount){
    int tenRadix = 1;
    while (radixCount > 0 ) {
        tenRadix *= 10;
        radixCount --;
    }
    return tenRadix;
}
void radixSort(int arr[], int length){
    int len = length;
    int max = arr[0];
    for (int i =1 ; i< length; i++) {
        max = arr[i]>max? arr[i]:max;
    }
    int radixCount = getRadixCount(max);
    int tenRadixCount = getTenRadixCount(radixCount);
    int (*bucket)[10] = new int[10][10];
    int* num = new int[10]();
    int multiplier = 1;
    while (multiplier < tenRadixCount) {
        for (int i = 0; i< len; i++) {
            int curCount = arr[i]/multiplier%10;
            int k = num[curCount];
            bucket[curCount][k] = arr[i];
            num[curCount]++;
        }
        int index = 0;
        for (int j = 0; j < 10; j++) {
            if (num[j]!=0) {
                for (int k =0; k<num[j]; k++) {
                    arr[index++]  =  bucket[j][k];
                }
            }
            //把桶清空，准备下一次循环。
            num[j] = 0;
        }
        multiplier *= 10;
    }
}

2. 字符串

微信文章:字符串操作的全面总结

2.1 String类的构造函数和析构函数如下

String类函数	说明
string s;	生成一个空字符串s
string s(s2);	拷贝构造函数 生成s2的复制品
string s("value");	用字符串value初始化s
string s(b,e);	以迭代器区间b,e内的字符作为字符串s的初值
string s(cp,n);	取字符数组，前n个字符作初值
string s(s2,pos2);	将字符串s2"始于位置pos2"部分当作字符串的初值
string s(s2,pos1,len);	将字符串s2内"始于pos1且长度最多len"的部分作为字符串的初值
s.~string();	销毁所有字符，释放内存

2.2 与容器共有的 string 操作

与容器共有的 string 操作方法	说明
s.insert(p,t);	在迭代器 p 指向的元素之前插入一个值为 t 的新元素,返回指向新插入元素的迭代器
s.insert(p,n,t);	在迭代器 p 指向的元素之前插入 n 个值为 t 的新元素
s.insert(p,b,e);	在迭代器 p 指向的元素之前插入迭代器 b 和 e 标记范围内所有的元素。返回 void
s.assign(b,e);	在迭代器 b 和 e 标记范围内的元素替换 s。string类型，返回 s；容器类型返回 void
s.assign(n,t);	用值为 t 的 n 个副本替换 s。对于 string 类型，该操作返回 s；对于容器类型，则返回 void
s.erase(p);	删除迭代器 p 指向的元素。返回一个迭代器，指向被 删除元素后面的元素
s.erase(b,e);	删除迭代器 b 和 e 标记范围内所有的元素。返回一个迭代器，指向被删除元素段后面的第一个元素

2.3 string 类型特有的版本：

string以数组的形式存储，可以用数组的下标进行修改操作：

string 修改操作方法	说明
s.insert(pos,n,c);	在下标 pos 的元素之前插入 n 个字符 c
s.insert(pos,s2);	在下标 pos 的元素之前插入 string 对象 s2
s.insert(pos,s2,pos2,len);	在下标为 pos 的元素之前插入 s2 中从下标 pos2 开始的 len 个字符
s.insert(pos,cp,len);	在下标为 pos 打元素之前插入 cp 所指向数组的前len 个字符
s.insert(pos,cp);	在下标为 pos 的元素之前插入 cp 所指向的以空字符结束的字符串副本
s.assign(s2);	用 s2 的副本替换 s
s.assign(s2,pos2,len);	用 s2 中从下标 pos2 开始的 len 个字符替换 s
s.assign(cp,len);	用 cp 所指向数组的前 len 个字符副本替换 s
s.assign(cp);	用 cp 所指向的以空字符结束的字符串替换 s
s.erase(pos,len);	删除从下标 pos 开始的 len 个字符

2.4 适合string类型操作的函数

• substr()主要功能是复制子字符串，要求从指定位置开始，并具有指定的长度。
• append() 方法在被选元素的结尾（仍然在内部）插入指定内容。提示：如需在被选元素的开头插入内容，请使用prepend()方法。
• replace() 该函数返回一个字符串，其中指定的字符串已经被替换为另一字符串，并且替换的次数也可以指定。

 string s2 = s.substr(6,5);  //从第6个开始取5个
s2 = s.substr(6);  //从第6个开始取拷贝所有的
s.append(" 3rd Ed");   //再s最后添加3rd Ed
s.insert(s.size()," 3rd Ed"); //最后插入
s.replace(11,3,"4th");       //下标11开始的3个替换为4th //replace相当于先删除后插入

2.5 string类型的查找

查找函数	说明
s.find( args);	在 s 中查找 args 的第一次出现
s.rfind( args);	在 s 中查找 args 的最后一次出现
s.find_first_of( args);	在 s 中查找 args 的任意字符的第一次出现
s.find_last_of( args) ;	在 s 中查找 args 的任意字符的最后一次出现
s.find_first_not_of( args);	在 s 中查找第一个不属于 args 的字符
s.find_last_not_of( args);	在 s 中查找最后一个不属于 args 的字符

2.6 string对象的比较

string对象比较函数compare用法	说明
str1.compare(str2);	如果相等则输出为0，str1>str2输出大于0，否则，输出小于0
str1.compare(m,n,str2);	str1的子串（从索引m开始，包含n个字符）与str2进行比较
str1.compare(m,n,str2,m,n);	str1的子串（从索引m开始，包含n个字符）与str2的子串（从索引m开始，包含n个字符）进行比较

2.7 string_view sv(string)

sv.substr(begin,end)更快

三、网络通信

1.TCP和UDP的区别

都位于传输层

1、TCP面向连接，UDP无连接；
2、TCP占用系统资源较多，拥塞控制，握手，慢开始、拥塞避免、快重传、快恢复，UDP少；
3、TCP结构复杂20字节的头，UDP简单8字节的头；
4、TCP基于字节流模式，UDP时数据报模式；
5、TCP保证数据正确性，UDP可能丢包；
6、TCP保证数据顺序，UDP不保证。
7、TCP用于HTTP/S，FTP等文件传输协议，POP、SMTP等邮件传输协议；UDP用于IP电话，视频通话

2.OSI七层模型，TCP/IP四层模型

分层的优点：

• 开放的标准化接口，实现模块化工程，降低了开发的复杂度，多厂商兼容性
• 易于理解、学习和更新协议标准
• 便于故障排除

img

3.三次握手、四次挥手

img

（1）序号（sequence number）：Seq序号，占32位，用来标识从TCP源端向目的端发送的字节流，发起方发送数据时对此进行标记。

（2）确认号（acknowledgement number）：Ack序号，占32位，只有ACK标志位为1时，确认序号字段才有效，Ack=Seq+1。

（3）标志位（Flags）：共6个，即URG、ACK、PSH、RST、SYN、FIN等。具体含义如下：

• URG：紧急指针（urgent pointer）有效。
• ACK：确认序号有效。
• PSH：接收方应该尽快将这个报文交给应用层。
• RST：重置连接。
• SYN：发起一个新连接。
• FIN：释放一个连接。

需要注意的是：

不要将确认序号Ack与标志位中的ACK搞混了。
确认方Ack=发起方Seq+1，两端配对。

img

1.为什么要进行第三次握手？

为了防止服务器端开启一些无用的连接增加服务器开销以及防止已失效的连接请求报文段突然又传送到了服务端，因而产生错误。

在传输的过程中，比如客户端发起了SYN=1创建连接的请求(第一次握手)。如果服务器端就直接创建了这个连接并返回包含SYN、ACK和Seq等内容的数据包给客户端，这个数据包因为网络传输的原因丢失了，丢失之后客户端就一直没有接收到服务器返回的数据包。客户端可能设置了一个超时时间，时间到了就关闭了连接创建的请求。再重新发出创建连接的请求，而服务器端是不知道的，就重开了个端口造成资源浪费。

另外一种是SYN=1的包丢失了，但是过一段时间有找到了，导致重开了一个端口造成资源浪费。

img

为什么“握手”是三次，“挥手”却要四次？

• 建立连接时，被动方服务器端结束CLOSED阶段进入“握手”阶段并不需要任何准备，可以直接返回SYN和ACK报文，开始建立连接。

• 释放连接时，被动方服务器，突然收到主动方客户端释放连接的请求时并不能立即释放连接，因为还有必要的数据需要处理，所以服务器先返回ACK确认收到报文，经过CLOSE-WAIT阶段准备好释放连接之后，才能返回FIN释放连接报文。

为什么客户端在TIME-WAIT阶段要等2MSL?

• 如果客户端在2MSL内，再次收到了来自服务器端的FIN报文，说明服务器端由于各种原因没有接收到客户端发出的ACK确认报文。客户端再次向服务器端发出ACK确认报文，计时器重置，重新开始2MSL的计时；
• 否则客户端在2MSL内没有再次收到来自服务器端的FIN报文，说明服务器端正常接收了ACK确认报文，客户端可以进入CLOSED阶段，完成“四次挥手”。

4. IP/ARP/RARP

ARP（Address Resolution Protocol）地址解析协议

作用：把网络层32位的IP转换成数据链路层48位的MAC地址，在这个过程中有一个很重要的表，ARP缓存表

如果有缓存的情况，A可以直接告诉数据链路层，E的MAC地址。A会查询ARP缓存表，查看E的MAC地址是什么，然后告知数据链路层。

如果没有缓存的情况，ARP会广播某一个IP的信息，收到这个广播的设备会回应一个包，表示我是不是这个IP地址。如果是，广播该IP地址的设备会记录对应设备的MAC地址

当一个IP数据包准备好了的时候，它是怎么选择一个合适的路径来"送货"的呢?

最特殊的情况是目的主机和主机直连，那么主机根本不用寻找路由，直接把数据传递过去就可以了。

稍微一般一点的情况是，主机通过若干个路由器(router)和目的主机连接。那么路由器就要通过ip包的信息来为ip包寻找到一个合适的目标来进行传递，比如合适的主机，或者合适的路由。路由器或者主机将会用如下的方式来处理某一个IP数据包:

如果IP数据包的TTL(生命周期)以到，则该IP数据包就被抛弃。

搜索路由表，优先搜索匹配主机，如果能找到和IP地址完全一致的目标主机，则将该包发向目标主机

搜索路由表，如果匹配主机失败，则匹配同子网的路由器，如果找到路由器，则将该包发向路由器。

搜索路由表，如果匹配同子网路由器失败，则匹配同网号路由器，如果找到路由器，则将该包发向路由器。

搜索路由表，如果以上都失败了，就搜索默认路由，如果默认路由存在，则发包。
如果都失败了，就丢掉这个包。

5.HTTPS

对称加密与非对称加密

对称加密加密与解密使用的是同样的密钥，所以速度快，但由于需要将密钥在网络传输，所以安全性不高。
（2） 非对称加密使用了一对密钥，公钥与私钥，所以安全性高，但加密与解密速度慢。
（3） 解决的办法是将对称加密的密钥使用非对称加密的公钥进行加密，然后发送出去，接收方使用私钥进行解密得到对称加密的密钥，然后双方可以使用对称加密来进行沟通。

传输过程

证书验证阶段：

• 浏览器发起 HTTPS 请求。
• 服务端返回 HTTPS 证书。
• 客户端验证证书是否合法，如果不合法则提示告警。

数据传输阶段：

• 当证书验证合法后，在本地生成随机数。
• 通过公钥加密随机数，并把加密后的随机数传输到服务端。
• 服务端通过私钥对随机数进行解密。
• 服务端通过客户端传入的随机数构造对称加密算法，对返回结果内容进行加密后传输。

为什么数据传输是用对称加密？

首先，非对称加密的加解密效率是非常低的，而 HTTP 的应用场景中通常端与端之间存在大量的交互，非对称加密的效率是无法接受的。

另外，在 HTTPS 的场景中只有服务端保存了私钥，一对公私钥只能实现单向的加解密，所以 HTTPS 中内容传输加密采取的是对称加密，而不是非对称加密。

Q：HTTPS 为什么安全？

A：因为 HTTPS 防止传输过程被监听、防止数据被窃取，可以确认网站的真实性。

Q：为什么需要证书？

A：防止“中间人”攻击，同时可以为网站提供身份证明。

Q：使用 HTTPS 会被抓包吗？

A：会被抓包，HTTPS 只防止用户在不知情的情况下通信被监听，如果用户主动授信，是可以构建“中间人”网络，代理软件可以对传输内容进行解密。

四、操作系统

1. 并发

并发是指宏观上在一段时间内能同时运行多个程序，而并行则指同一时刻能运行多个指令。

操作系统通过引入进程和线程，使得程序能够并发运行。

2. 共享

共享是指系统中的资源可以被多个并发进程共同使用。

有两种共享方式：互斥共享和同时共享。

互斥共享的资源称为临界资源，在同一时刻只允许一个进程访问，需要用同步机制来实现互斥访问。

3. 虚拟

虚拟技术把一个物理实体转换为多个逻辑实体。

主要有两种虚拟技术：时分复用技术和空分复用技术。

多个进程能在同一个处理器上并发执行使用了时分复用技术

虚拟内存使用了空分复用技术，它将物理内存抽象为地址空间，每个进程都有各自的地址空间。地址空间的页被映射到物理内存，地址空间的页并不需要全部在物理内存中，当使用到一个没有在物理内存的页时，执行页面置换算法，将该页置换到内存中。

4. 异步

异步指进程不是一次性执行完毕，而是走走停停，以不可知的速度向前推进。

5. 进程管理

进程控制、进程同步、进程通信、死锁处理、处理机调度等。

1. 进程线程协程的区别

Ⅰ 拥有资源

进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。

Ⅱ 调度

线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。

Ⅲ 系统开销

由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置

而线程切换时只需保存和设置少量寄存器内容，开销很小。

Ⅳ 通信方面

线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。

2. 进程状态的切换

• 就绪状态（ready）：等待被调度
• 运行状态（running）
• 阻塞状态（waiting）：等待资源

应该注意以下内容：

• 就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。
• 阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态。

3. 进程调度算法

3.1 批处理系统

批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。

先来先服务 first-come first-serverd（FCFS）

非抢占式的调度算法，按照请求的顺序进行调度。

短作业优先 shortest job first（SJF）

非抢占式的调度算法，按估计运行时间最短的顺序进行调度。

最短剩余时间优先 shortest remaining time next（SRTN）

最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。

当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。

3.2. 交互式系统

交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。

时间片轮转

将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。

时间片轮转算法的效率和时间片的大小有很大关系：

• 因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。
• 而如果时间片过长，那么实时性就不能得到保证。

优先级调度

为每个进程分配一个优先级，按优先级进行调度。

为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

多级反馈队列

多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。

每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。

可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

[图片上传失败...(image-da492a-1595293109591)]

4.进程同步

• 空闲让进：临界区空闲时，说明没有进程使用临界资源，此时应该让想要进入临界区的进程立刻进来
• 忙则等待：如果已经有进程进入临界区，则其它同样想要进入的进程只能等着
• 有限等待：不能让进程一直干等着，要保证他在有限的时间内可以进入临界区
• 让权等待：当进程不能进入自己的临界区时，应该立刻释放处理机，防止进程陷入“忙等”状态。

1. 临界区

对临界资源进行访问的那段代码称为临界区。

为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查。

2. 同步与互斥

• 同步：多个进程因为合作产生的直接制约关系，使得进程有一定的先后执行关系。

• 互斥：多个进程在同一时刻只有一个进程能进入临界区。

3. 如何实现互斥?

① 单标志法：用一个 Flag 来标志哪个进程可以进入临界区，在初始给定 Flag 的情况下，一定可以确保是 Flag 对应的进程可以进入临界区。而在该进程顺利进入并完成自己的任务后，它会将 Flag 改指向另一个进程。

② 双标志先检查法：为每个进程都设置一个可以起到开关作用的 Flag。它的核心是，初始所有的进程 Flag 都为 false，表示暂时都不想进入临界区。某一时刻有个进程想要进入了，他首先会检查当前是否有其他进程正在占用，有的话就作罢，自己慢慢等，没有的话就自己进入，一进入就马上打开 Flag 开关为 true，相当于”上了一把锁“，这期间只有自己拥有占有权，其他进程都是进不来的。在自己完成任务后，再置 Flag 为 false，相当于释放了占有权（把锁打开）。

双标志先检查法并不能保证互斥访问资源，它违背了“忙则等待”的原则。

③ 双标志后检查法

④ Peterson 算法:在一开始还是和后检查法一样，抢先进行“上锁”，但是上锁之后又将 turn 置为对方线程，表示自己虽然想要进入临界区，但是不介意“将这个机会让给对方”。尽管如此，由于 while 的限制条件增加了，而 turn 又是公用的，所以保证了最后只会有一方的 while 满足条件。既做到了互斥访问资源，也避免了双方都访问不到资源。

4. 信号量

信号量（Semaphore）是一个整型变量，可以对其执行 down 和 up 操作，也就是常见的 P 和 V 操作。

• down : 如果信号量大于 0 ，执行 -1 操作；如果信号量等于 0，进程睡眠，等待信号量大于 0；
• up ：对信号量执行 +1 操作，唤醒睡眠的进程让其完成 down 操作。

如果信号量的取值只能为 0 或者 1，那么就成为了 互斥量（Mutex） ，0 表示临界区已经加锁，1 表示临界区解锁。

如果由于 P0 在使用临界资源而导致 P1 暂时无法使用，那么干脆就不给 P1 陷入循环的机会，直接让它自己去阻塞队列，这样 P1 在被唤醒之前，永远无法占用处理机，也自然就不可能出现白白占用处理机的情况。而在 P0 释放资源后，我们才来考虑唤醒 P1。

5.进程通信

• 进程同步：控制多个进程按一定顺序执行；
• 进程通信：进程间传输信息。

进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。

1. 管道

管道是通过调用 pipe 函数创建的，fd[0] 用于读，fd[1] 用于写。

#include <unistd.h>
int pipe(int fd[2]);

它具有以下限制：

• 只支持半双工通信（单向交替传输）；
• 只能在父子进程或者兄弟进程中使用。

[图片上传失败...(image-da55c0-1595293109591)]

2. FIFO

也称为命名管道，去除了管道只能在父子进程中使用的限制。

#include <sys/stat.h>
int mkfifo(const char *path, mode_t mode);
int mkfifoat(int fd, const char *path, mode_t mode);

FIFO 常用于客户-服务器应用程序中，FIFO 用作汇聚点，在客户进程和服务器进程之间传递数据。

img

3. 消息队列

相比于 FIFO，消息队列具有以下优点：

• 消息队列可以独立于读写进程存在，从而避免了 FIFO 中同步管道的打开和关闭时可能产生的困难；
• 避免了 FIFO 的同步阻塞问题，不需要进程自己提供同步方法；
• 读进程可以根据消息类型有选择地接收消息，而不像 FIFO 那样只能默认地接收。

4. 信号量

它是一个计数器，用于为多个进程提供对共享数据对象的访问。

5. 共享存储

允许多个进程共享一个给定的存储区。因为数据不需要在进程之间复制，所以这是最快的一种 IPC。

需要使用信号量用来同步对共享存储的访问。

多个进程可以将同一个文件映射到它们的地址空间从而实现共享内存。

6. 套接字

用于不同机器间的进程通信。

6.死锁

1. 四个必要条件

① 互斥：

要求进程竞争的资源必须是互斥使用的资源。因为如果是可以共享使用的资源，多个进程直接同时使用就好，不会陷入等待的僵局。

② 非抢占：

要求进程占有的资源只能由进程使用完之后自己主动释放，其它进程不能抢占该资源。因为如果其它进程可以抢占资源，那么就是直接拿到资源了，也不会陷入等待的僵局。

③ 占有和请求：

要求进程是在占有（holding）至少一个资源的前提下，请求（waiting）新的资源的。由于新的资源被其它进程占有，此时，发出请求的进程就会带着自己占有的资源进入阻塞状态。

④ 循环等待：

要求存在一条进程资源的循环等待链，链中的每一个进程占有的资源同时被另一个进程所请求。

2.死锁的处理

预防死锁

① 破坏互斥条件

② 破坏非抢占条件

• 从占有资源的进程的角度考虑，如果它请求不到新的资源，那么它必须立即释放占有的全部资源，以后需要的时候重新申请
• 从请求资源的进程的角度考虑，如果它需要请求资源，那么操作系统会帮助它抢占相关资源。比如现在有一个优先级更高的进程，如果是采用优先级调度算法，那么它将有机会在操作系统的帮助下抢占到资源。

③ 破坏占有和请求条件

在进程运行之前就一次申请完需要的全部资源，如果资源不到位，就先不让它运行；如果资源到位，就让它带着资源运行。

④ 破坏循环等待条件

规定每个进程必须按照编号递增的顺序请求资源：必须先请求小编号资源，后请求大编号资源，请求大编号资源后，后续请求的资源只会比该资源编号更大。这样就成功打破了闭环。

避免死锁

资源分配图算法

银行家算法

解除死锁

① 资源剥夺法：

② 撤销/终止进程法：

③ 进程回退法：

7. 内存管理

内存分配、地址映射、内存保护与共享、虚拟内存等。

8. 文件管理

文件存储空间的管理、目录管理、文件读写管理和保护等。

9. 设备管理

完成用户的 I/O 请求，方便用户使用各种设备，并提高设备的利用率。

主要包括缓冲管理、设备分配、设备处理、虛拟设备等。