1. C和C++区别：

• C语言：面向过程的语言，其核心关注于问题是如何被解决的，把实现一个软件功能的过程分为一个个过程。 例如汽车要去加油，其过程为：汽车启动->汽车行驶->汽车加油。在这里我们不关注物件本身(汽车这个对象)，默认定义执行该过程的主题是汽车。
• C++语言： 面向对象的语言，在计算机科学中的对象既可以表示客观世界的问题空间(namespace)中的具体的某个事物，又可以表示软件系统解空间的基本元素，如变量、数据结构、函数等。例如汽车要去加油，汽车<启动，开车，加油>, 我们关注物件(对象)本身，只需要考虑什么时间干什么事。启动，开车，加油属于这个物件的基本属性。

C语言基础部分：

• 标识符： 一个标识符以字母或者下划线开始的后面可以跟多个字母、数字、下划线。C标识符中不允许出现标点字符，并且区分大小写。
• 关键字： C中的保留字，这些保留字不能作为常量名，变量名和其他标识符的名称。常用的的关键字包括:while, do, for, break, continue, default, goto, char, double, int, long, short, float,

• **数据类型： ** C语言有四种数据类型：
  • **基本数据类型: **他们是算术类型，包括整数类型和浮点类型，注意char是属于整数类型的。 基本数据类型占用的空间(64位机器)：char-1字节，int-4字节， float-4字节，double-8字节。
  • 枚举类型： 他们也是算术类型，被用来定义在程序中，只能赋予其一定的离散整数值的变量
  • void类型： 类型说明符 void表明没有可用的值
  • 派生类型： 它们主要包括：指针，数组，结构，共用体，和函数类型
  • 强制类型转换： (类型说明符)(表达式)

变量：

变量是程序可操作的存储区名称。全局变量保存在内存的全局存储区中，占用静态的存储单元；局部变量保存在栈中，只有在所在函数被调用的时候才动态地为变量分配存储单元。

C语言经过编译后将内存分为一下几个区域：

• 栈(stack): 由编译器进行管理，自动分配和释放，存放函数调用过程的各种参数，局部变量，返回值以及函数的返回地址。操作方式类似于数据中的栈。
• 堆(heap): 用于程序动态申请分配和释放空间。C语言中的malloc和free，C++中的new和delete均是在堆中进行的。正常情况下，程序员申请的空间在使用结束后应该释放，若程序员没有释放空间，则在程序结束后由系统自动回收。注意：这里的对并不是数据结构中的堆。
• 全局(静态)存储区: 分为DATA和BSS段，DATA段(全局初始化区)存放初始化的全局变量和静态变量；BSS段(全局未初始化分区) 存放未初始化的全局变量和静态变量。程序运行结束时自动释放，其中在BSS段在程序执行之前会被系统自动清零，所以未初始化的全局变量和静态变量在程序执行之前已经为0.
• 文字常量区：存放常量字符串，程序结束由系统释放。
• 程序代码区：存放程序的二进制代码。

因此，C语言的全局变量和局部变量在内存之中是有区别的，C语言的全局变量包括外部变量和静态变量，均是保存在全局存储区中，占用永久性的存储单元；局部变量，即自动变量，保存在栈中，只有在所在的函数被调用时才有系统动态在栈中分配临时性的存储单元。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <stdio.h>
#include <stdlib.h>
int k1 = 1;
int k2;
static int k3 = 2;
static int k4;
int main( )
{  staticint m1=2, m2;
    inti=1;
    char*p;
    charstr[10] = "hello";
    char*q = "hello";
    p= (char *)malloc( 100 );
    free(p);
    printf("栈区-变量地址  i：%p\n", &i);
    printf("                p：%p\n", &p);
    printf("              str：%p\n", str);
    printf("                q：%p\n", &q);
    printf("堆区地址-动态申请：%p\n", p);
    printf("全局外部有初值 k1：%p\n", &k1);
    printf("    外部无初值 k2：%p\n", &k2);
    printf("静态外部有初值 k3：%p\n", &k3);
    printf("    外静无初值 k4：%p\n", &k4);
    printf("  内静态有初值 m1：%p\n", &m1);
    printf("  内静态无初值 m2：%p\n", &m2);
    printf("文字常量地址    ：%p, %s\n",q, q);
    printf("程序区地址      ：%p\n",&main);
    return0;
}

常量

常量是固定值，在程序的执行期间不会改变。它可以是任意基本的数据类型，整数常量，浮点常量，字符常量，枚举常量等。

• 定义常量： 定义常量有两种方法，使用#define或者使用const关键字，这两种方法从本质上是不同的。#define 是宏定义，它不能定义常量，但宏定义可以实现在字面意义上和其它定义常量相同的功能，本质的区别就在于 #define 不为宏名分配内存，而 const 也不为常量分配内存，怎么回事呢，其实 const 并不是去定义一个常量，而是去改变一个变量的存储类，把该变量所占的内存变为只读！
  
  示例
  #define length 10
  #define NEWLINE ‘\n’
  
  const int var=5;
• 整数常量：整数常量可以是十进制，八进制，十六进制的常量，前缀指定基数，0x/0X表示十六进制，0表示八进制，不带前缀默认代表十进制。整数常量也可以带一个后缀，U代表无符号整数, L代表长整数，大小写和顺序任意。

C++语言的三大特性

• 封装： C++语言支持数据封装，类是数据封装的工具，对象是数据封装的实现，在封装中，还提供一种对数据访问控制的机制，是的一些数据隐藏在封装体内，具有隐藏性。封装和外接的信息交换是通过操作接口进行的，这种访问的控制机制体现在类的共有成员(public)，私有成员(private)，和保护成员(protected)上。私有成员只有类内说明的一些函数才能访问；共有成员类外的函数也可以访问，保护成员只有该类的成员函数和派生类才能访问。
• 继承： C++语言允许单继承和多继承。一个类可以根据需要生成它的派生类，派生类还可以再生成派生类。派生类可以继承基类的成员同时也可以定义自己的成员。继承是实现数据抽象和共享的一种机制。该机制可以避免不能重复利用程序导致的资源浪费。
• 多态： 多态指的是对不同类发出的相同消息会有不同的实现。多态性也可以理解为，在一般类中定义的属性和服务被特殊类继承后，可以具有不同的数据类型或不同的实现。简单来说，多态性指的是发出同样的消息被不同的数据类型的对象接收后会导致不同的行为。C++支持多态性主要表现在：C++语言允许函数重载和运算符重载；C++语言通过定义虚函数来支持动态联编。多态特性的工作依赖虚函数的定义，在需要解决多态问题的重载成员函数前，加上virtual关键字，那么该成员函数就变成了虚函数，从上例代码运行的结果看，系统成功的分辨出了对象的真实类型，成功的调用了各自的重载成员函数。

二维向量的遍历方法

1
2
3
4
5
6
7
8
9

//二维向量的遍历，迭代器遍历
vector<vector<int> > array = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};  
vector<vector<int >>::iterator iter;
for (iter = array.begin(); iter != array.end() ; ++iter) {
    for (int i = 0; i < (*iter).size(); ++i) {
        cout << (*iter)[i] << " " ;
    }
    cout << endl;
}

1
2
3
4
5
6
7
8
9

//二维向量的遍历，数组下表
vector<vector<int> > array = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};  

for (int i = 0; i < array.size(); i++)
{
    for(int j = 0; j < array[i].size(); j++)
        cout << V[i][j] << " ";
    cout << endl;
}	

质数定义：指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。

思路1：定义

根据定义，采用2到n-1中的每一个数去除n，如果不能被整除，则该数为质数。时间复杂度：O(n)。

1
2
3
4
5
6
7
8
9
10
11
12

bool is_prime(int n)
{
    bool isprime = true;
    for(int i=2; i < n; i++){
        if(n % i==0){
            isprime=false;
            break;
        }
    }
    return isprime;
}

思路2：质数筛选定理

质数筛选定理： 如果n不能够被不大于根号n的任何质数整除，则n是一个质数。
参考链接：

• https://zhuanlan.zhihu.com/p/100051075
• https://blog.csdn.net/wo17fang/article/details/47656769

1
2
3
4
5
6
7
8
9
10
11

bool is_prime(int n){
    bool isprime= true;
    int max = static_cast<int>(sqrt(n)); \\隐式类型转换
    for(int j=2; j<=max; j++){
        if(n%j == 0){
            isprime=false;
            break;
        }
    }   
    return isprime;
}

基本概念

排序算法是程序设计中最基本的算法，常用的排序算法有十种，可以分为内部排序和外部排序两种类型：

内部排序

• 内部排序是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。
• 常见的内部排序算法：冒泡排序，快速排序，插入排序，选择排序，希尔排序，堆排序。

外部排序

• 外部排序是针对于极大量数据的排序算法，由于数据无法一次放入内存，算法采用“排序-归并” 策略，首先将部分数据依次读入内存，排序后生成有序的临时文件，在归并阶段将这些临时文件组成较大的有序文件。
• 常见的外部排序算法有归并排序，计数排序，桶排序，基数排序。

关于排序算法的简单介绍：

排序算法的稳定性

如果两个具有相同键的对象在输入输出中的顺序与在输入未排序数组中出现的顺序相同，则该排序算法被认为是稳定的。有些排序算法本质上是稳定的，例如插入排序，合并排序，冒泡排序等。而有些排序算法则不是，例如堆排序，快速排序等。

但是，任何给定的不稳定算法都可以修改为稳定。可以使用特定的排序算法来使其稳定，但是通常，可以通过更改键比较操作将本质上不稳定的任何基于比较的排序算法修改为稳定，以便将两个键的比较视为位置。具有相同键的对象的系数。参考文献

冒泡排序

冒泡排序（Bubble Sort）重复遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。 重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
算法步骤：

1. 以升序为例，比较相邻两个元素大小，如果第一个元素大于第二个，则交换两个元素，否则不做改变。
2. 从数组的第一个元素开始，遍历到数组的倒数第二个元素。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
#include <vector>
using namespace std;

void bubble_sort(vector<int> &num, int len){
    for(int i = 0; i < len-1; i++){
        for(int j = 0; j<len-1-i; j++){
            if(num[j] > num[j+1]) 
                swap(num[j], num[j+1]);
        }
    }
}

int main(){
    vector<int> num= { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
    int len = num.size();
    for(int i=0; i < len; i++)
        cout << num[i] << ' ';
    cout << '\n';
    Bubble_sort(num, len);
    for(int i=0; i < len; i++)
        cout << num[i] << ' ';
    return 0;
}

选择排序

选择排序的方法为第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。 以此类推，直到全部待排序的数据元素的个数为零。 选择排序是不稳定的排序方法。
算法步骤：

1. 记录数据中的第一个元素的index
2. 遍历数据并与该元素进行比较，如果小于该元素则更新index，完成遍历后交换第一个元素和index所指向的最小值。
3. 重复以上步骤直至完成排序。
   

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12

void selection_sort(vector<int> &num, int len){
    int min;
    for(int i=0; i<len; i++){
        min = i;
        for(int j=i; j<len; j++){
            if(num[j] < num[min])
                min = j;
        }
        swap(num[i], num[min]);
    }
}

插入排序

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

代码实现：

1
2
3
4
5
6
7
8
9
10

void intersection_sort(vector<int> &num, int len){
    for(int i=1; i<len; i++){
        for(int j=i; j>0; j--){
            if(num[j] < num[j-1])
                swap(num[j-1], num[j]);
        }
    }
}

希尔排序

希尔排序（Shellsort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是基于插入排序的以下两点性质而提出改进方法的：

1. 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
2. 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
   希尔排序原理的视频介绍：希尔排序

算法实现：

1
2
3
4
5
6
7
8
9
10

void shell_sort(vector<int> &num, int len){
    for(int gap = len / 2; gap > 0; gap /= 2)
        for(int i = gap; i < len; i++){
            int temp = num[i];
            int j = i;
            for( ; j >= gap && temp < num[j-gap]; j-=gap)
                num[j] = num[j-gap];
            num[j] = temp;
        }
}

快速排序

快速排序是在实践中最快的已知排序算法，算法的平均运行时间是O(NlogN), 最坏的性能为O(N^2).
算法步骤：

1. 从数列中随机挑出一个元素，称为 “基准”（pivot）;

2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

算法实现：

1

归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

• 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
• 自下而上的迭代；

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

算法步骤：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；

3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

4. 重复步骤 3 直到某一指针达到序列尾；

5. 将另一序列剩下的所有元素直接复制到合并序列尾

参考资料：
[1] 关于排序算法的一点知识——实例和伪代码
[2]