1. 算法总览

常见的排序算法有插入排序、选择排序、希尔排序、堆排序、冒泡排序、快速排序、归并排序和基数排序。常见排序算法可以分为两大类：

• 非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。
• 线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。排序算法的时间复杂度如下：

1. make

1.1 make是什么

make是一个命令，是管理文件的自动编译管理器，这里的自动是指能根据文件时间戳自动发现更新过的文件而减少编译的工作量，同时通过读取makefile的文件的内容来进行预期的编译工作，make将只编译有改动的文件，而不用完全编译。

1. shell

shell是Linux系统中运行的一种特殊程序。在用户和内核之间之间充当“翻译官”，用户登陆Linux系统时，自动加载一个Shell程序，Bash是Linux系统中默认使用的Shell程序。

• 内核：用于调用计算机硬件资源
• shell：将用户指令转换成计算机语言让内核去调用计算机硬件资源

1. Ubuntu常用快捷键

1
2
3
4
5
6
7
8
9

1、打开终端：Ctr+Alt+T
2、关闭终端：Ctrl + Shift + Q
3、复制：Ctrl + Shift + C
4、粘贴：Ctrl + Shift + V
5、跳转回主机操作:ctr+alt
6、跳回虚拟机：Ctr+G
7、新建终端窗口：Ctrl + Shift + N
8、运行命令：Alt + F2
9、全屏切换：F11

1.STL概述

1.1 六大组件

• 容器：各种数据结构,如vector、list、deque、set、map等,用来存放数据
• 算法：各种常用的算法（冒泡，排序）,如sort、find、copy、for_each、search、erase
• 迭代器：扮演了容器与算法之间的胶合剂，是所谓的泛型指针
• 仿函数：行为类似函数，可作为算法的某种策略
• 适配器：一种用来修饰容器或者仿函数或迭代器接口的东西
• 空间配置器：负责空间的配置与管理。注意一般都伴随着重新分配空间，那么原来的迭代器就会失效

六大组件的交互关系是Container通过Allocator获得数据存储空间，Alogrithm通过Iterator存取Container的内容，Functor可以协助Algorithm完成不同的策略变化，Adapter可以修饰或套接Functor。本笔记将会以此对这六大组件进行介绍。

++说在前面：STL的实现版本由HP版本、PJ版本、RW版本、STLport版本和SGISTL版本等五个主要版本++

1.说在前面

c++支持两种类--抽象类和具体类。一个抽象类包含着没有实现代码的成员函数（纯虚函数）。具体了类没有纯虚函数。只有具体类才可以实例化（但抽象类实例化指针和引用是运行的），即只能对具体类建立实例或对象。

在这里主要讲解各种数据结构的思想，列举抽象类接口和实现一部分具体类的接口功能。

1. 面向对象程序设计

面向对象程序设计的核心思想是数据抽象、继承和动态绑定。通过数据抽象，我们可以将类的接口与实现相分离；使用继承。可以使用相似的类型对其关系建模；使用动态绑定，可以在一定程度上忽略相似类型的区别。

• 1）继承：根部类为基类（相似于java的父类），其他继承于基类的类为派生类。
• 2）虚函数：某些函数，基类希望它的派生类各自定义适合其自生的函数
• 3）动态绑定：能使用同一代码分别处理基类和派生类。如虚函数运行版本由实参决定。

1.1 定义基类

• 作为继承关系中根结点的类通常有定义了一个虚析构函数。
• 基类中的成员函数分为两种：一是派生类要进行重写覆盖的函数，称为虚函数；二是希望直接继承而不改变的函数。当我们使用指针或引用调用虚函数时，该调用将被动态绑定。
• 基类通过在其成员函数的声明语句之前加上关键字virtual使得函数执行动态绑定。其只能出现在类内部声明或定义中。
• 派生类可以继承定义在基类中的成员，但是派生类的的成员函数不一定有权访问从基类继承而来的成员。派生类能访问公有成员，但不能访问私有成员。为解决这一问题，引入了新访问运算符：protected(派生类有权访问，禁止用户访问）

1.类型

1.1 基本内置类型

基本内置类型有算术类型和空类型。算术类型分两类为整型和浮点型，下图显示了C++的算数类型:

1.2 复合类型

c++有几种复合类型：数组、结构、string、引用和指针。这里讨论引用和指针。

1. 面向对象

相比于c++,python中的OOP理解和使用都较简单，其把隐藏的的语法杂质和复杂性都去掉了。 ## 1.1 类对象提供的默认行为 在python的面向对象模型种，要分清类对象和实例对象。类对象就是class定义了一个类只会，该类提供些行为就是类对象.而实例对象就是该类的实例。每次调用类，就会生成一个实例。 类对象提供的默认行为：

• class语句创建类对象并将其赋值给变量名。就像def一样，class语句也是可执行语句，执行时会产生类对象，并赋值变量名
• class语句的赋值语句会创建类属性，像模块文件一样，class语句内的顶层的赋值语句（不在def内）会成为类对象的属性。
• 类属性提供对象的状态（变量）和行为（函数）
• 类仍然时模块内的属性。当class执行时，只是赋值语句而已，赋值了一个类对象

1. python的运行过程

1.1 字节码编译

当程序运行时,Python内部会将源代码(.py文件中的程序)编译成所谓的字节码的形式,就是将每一行源代码语句从上到下翻译过来,翻译成一组字节码的指令.这些字节码可以提高执行速度;比起源代码语句,字节码要执行快的多。