多益网络笔试总结：

题型：单选，填空，编程

单选涉及的知识点：

主要知识点有栈（先入先出考察），二叉树知识（前中后序遍历以及重组二叉树），排序算法稳定性，时间复杂度以及一些很简单的基础题型

填空涉及的知识点：

1. 英语翻译，给了一段英语文章，要求翻译成中文，我的主题是关于大数据的
2. 匿名管道怎么进行进程通信
3. 给二叉树的前序遍历与中序遍历，求后续遍历
4. 简述内连接与外连接
5. DHCP与NAT的含义与作用

编程题：

从m个数中选择n个数，要求每个数被选择的概率相同

总结：

总的来说相比其他公司笔试较为容易，多为考察基础，但是也暴露了一些高频知识点掌握情况不好的问题，比如排序算法以及数据库相关的知识。

编程题因为没有想到不考算法，思考了很久也没想出来，由于不太清楚C++的random怎么写导致最后提交失败，提交之后才想到自己死心眼的一定要用C++写，其实用python很容易实现。

下面是一些知识点的知识总结，如果您掌握的较好，请忽略。

十大排序算法

来源为：十大排序从入门到入赘 - 力扣（LeetCode）

复杂度与稳定性一览：

稳定性指的是对于存在相等元素的序列，排序后，原相等元素在排序结果的相对位置相比原输入序列不变。如果排序对象只是数值，那么是否稳定没有区别。但若是对引用类型进行排序，排序依据是该类型中的某个可比较的数值字段，那么我们可能会希望该字段相同，但其他字段不同的元素相对位置相比原输入保持不变，这时候就需要稳定排序。

下列说明在正文相应章节均有更详细的描述。

※1冒泡: 输入数组已排序时最好。
※2选择: 时间复杂度与输入数组特点无关。
※3插入: 输入数组已排序时最好。
※4希尔: 复杂度取决于增量序列，两行分别为希尔增量，
和Knuth增量的希尔排序。输入数组已排序时最好。
※5归并: 所列复杂度为「自顶向下非原地」版本。
自顶向下/自底向上，非原地/原地的时间空间复杂度见该归并排序一节。
※6快速: 当输入数组有序，且总是选取第一个元素为主轴时，
时间复杂度退化为O(n^2)。空间开销为递归深度。
※7堆: 原地堆排序空间复杂度为O(1)。输入数组所有数字相等时，
时间复杂度为O(n)。
※8计数: k是计数数组大小。应用稳定性优化则稳定，否则不稳定。
朴素版本空间复杂度为O(k)，稳定性优化版本空间复杂度为O(n + k)。
※9基数: d是最大数位数，k是计数数组大小，处理负数时k=19。
※10桶: 稳定性取决于桶内排序是否稳定。空间取决于桶使用数组还是容器，
若采用数组为O(kn)，容器则为O(n)。所有元素放入同一个桶时复杂度最大。
最坏时间复杂度取决于采用哪种桶内排序算法。

稳定性: 存在稳定和非稳定版本时，视作「稳定」。

一.冒泡排序

首先从第一位开始从前往后比较相邻两个数字，如果前者大，则交换两数字位置，之后比较位向右移一位；第一轮从前往后的比较使得最大的数字冒泡到最后，此时可以说一个数字已经被排序，每一轮的比较将使得当前未排序数字中的最大者被排序，未排序数字总数减 1。第 n-1 轮结束后排序完成。

稳定性：稳定。

冒泡排序始终只交换相邻元素，如果对象大小相等时不交换，相对位置不变，故稳定。

优化：

提前结束优化

当某一轮比较均为发生交换时，说明排序已经完成，可设置一个bool量记录一轮排序是否有发生交换，若无则提前退出循环结束程序。

冒泡界优化

记录前一轮交换的最终位置，说明该位置之后的元素为已排序状态，下一轮的交换只需执行到该处。

代码：

提前结束优化：

vector<int> bubbleSort(vector<int>& arr)
{
    if(arr.size()<2) return arr;
    //n-1轮次执行，当前n-1个元素排列好之后，最后一个元素无需排列，故i<arr.size()-1
    for(int i = 0;i<arr.size()-1;i++)
    {
        //本轮执行是否有交换的标志，若无则false，若有则true
        bool swapped = false;
        //每次循环，通过依次向右比较两个数，将本轮循环最大的数放到最右
        for(int j = 1;j<arr.size()-1;j++)
        {
            //若左大于右则交换，并将swapped置为true
            if(arr[j-1]>arr[j])
            {
                swap(arr[j-1],arr[j]);
                swapped = true;
            }
        }
        //若无交换，表示当前数组已经排序好了，退出大循环
        if(!swapped) break;
    }
    return arr;

}

提前结束+冒泡界优化：

vector<int> bubbleSort(vector<int>& arr)
{
    if (arr.length < 2) return arr;
    boolean swapped = true;
    int lastSwappedIndex = arr.length-1;
    int swappedIdx = -1;

    while(swapped)
    {
        //当swapped为false时，排序完成
        swapped = false;
        // 每轮循环，通过依次向右比较两个数，将本轮循环中最大的数放到最右
        for (int i = 0; i < lastSwappedIdx; i++) {
            // 若左大于右则交换，并将swapped置为true
            if (arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
                swapped = true;
                swappedIdx = i;
            }
        }
        lastSwappedIdx = swappedIdx;
    }
    return arr;
}

复杂度分析：

最好的时候是已经排序好的，时间复杂度为O（n)

平均时间复杂度和最差时间复杂度都是O(n^2)

二.选择排序

对于要排序的数组，设置一个minIdx记录最小数字下标。先假设第一个数字最小，此时minIdx=0，将arr[minIdx]与后续数字注意比较，当遇到更小的数字时，使minIdx等于该数字下标，第一轮将找出此时数组最小的数字，之后将midIdx下标的数字与第一个数字交换，此时第一个数字已被排序。然后开始第2轮比较，令minIdx = 1，重复上述过程。每一轮的比较将使得当前未排序数字中的最小者被排序，未排序数字总数减1。第arr.length - 1轮结束后排序完成。

微优化：

在交换之前判断minIdx是否有变化，若无变化则无需交换，在数组大致有序时，能够减少无效交换带来的开销

稳定性：

不稳定，例如772，第一轮交换第一个7和2，两个7的位置改变

双元选择优化

在遍历寻找最小值下标minIdx时，可以同时寻找最大值下标maxIdx，这样就可以一轮遍历确定两个元素的位置，遍历次数减少一半，但是没轮的操作变多了，因此该优化只能少量提升选择排序的速度

复杂度分析：

平均，最好最坏都是O(n^2)

代码：

单元选择排序：

vector<int> selectSort(vector<int>& arr)
{
    if(arr.size()<2) return arr;
    //n-1轮次执行，当前n-1个元素排列好后，最后一个元素无需执行，故i<arr.size()-1
    for(int i = 0;i<arr.size()-1;i++)
    {
        int minIdx = i;
        //找到本轮执行中最小的元素，将最小元素的下标赋给minIdx
        for(int j = 1;j<arr.size()-1;j++)
        {
            if(arr[j]<arr[i])
            {
                minIdx = j;
            }
        }
        //若本轮第一个数字不是最小值，则交换位置
        if(minIdx != i) swap(arr[i],arr[minIdx]);
    }
    return arr;
}

双元选择排序：

public int[] selectSortDouble(int[] arr) {
    if (arr.length < 2) return arr;
    int n = arr.length;
    // 每轮确定两个数字，因此界也会动态变化
    for (int i = 0; i < n - 1 - i; i++) {
        int minIdx = i, maxIdx = i;
        // 找到本轮执行中最小和最大的元素
        for (int j = i + 1; j < n - i; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
            if(arr[j] > arr[maxIdx]) maxIdx = j;
        }
        // 若本轮最大值等于最小值，说明未排序部分所有元素相等，无需再排序
        if(minIdx == maxIdx) break;
        // 若本轮第一个数字不是最小值，则交换位置（将最小值与本轮第一个数字交换位置）
        if (minIdx != i) swap(arr, i, minIdx);
        // 在交换i和minIdx时，有可能出现i即maxIdx的情况，此时需要修改maxIdx为minIdx
        if(maxIdx == i) maxIdx = minIdx;
        // 若本轮最后一个数字不是最大值，则交换位置（将最大值与本轮最后一个数字交换位置）
        if (maxIdx != n - 1 - i) swap(arr, n - 1 - i, maxIdx);
    }
    return arr;
}

三.插入排序

对于待排序数组，从第二个元素开始，比较它与之前的元素，直到找到不小于的对象，此时将该元素插入到该该次比较对象之后。重复这个插入过程直到最后一个元素作为插入对象元素完成插入操作（类比摆扑克）

稳定性：

稳定的

折半插入优化

注意到插入排序的每一轮向前插入都使得该元素在完成插入后，从第一个元素到该元素是排序状态（指这部分的相对排序状态，在它们中间后续可能还会插入其他数字），利用这一点，对一个新的插入对象向前执行折半插入，能够显著减少比较的次数。另一种优化是增量递减插入排序，也叫希尔排序，将在希尔排序章节中介绍。（二分查找框架）

复杂度：

最坏时间复杂度O(n^2)

平均时间复杂度O(n^2)

最好时间复杂度O(n)

代码

vector<int> insertSort(vector<int>& arr)
{
    if(arr.size()<2) return arr;
    for(int i = 1;i<arr.size();i++)
    {
        int target = arr[i];
        int j = i-1;
        for(;j>=0;j--)//跟每一个i前面的值比较，直到找到》=的值
        {
            if(target<arr[j]) arr[j+1] = arr[j];
            else break;
        }
        arr[j+1] = target;
    }
    return arr;
}

折半插入排序：

public int[] insertSortBinary(int[] arr) {
    if (arr.length < 2) return arr;
    // n - 1 轮次执行
    for (int i = 1; i < arr.length; i++) {
        // 若当前插入对象大于等于前一个对象，无需插入
        if (arr[i - 1] <= arr[i]) continue;
        int target = arr[i];
        // 折半查找 (二分查找「模版一」)
        int low = 0, high = i - 1;
        // while结束后，target要插入的位置为low或high + 1 (low = high + 1)
        while (low <= high) {
            int center = low + (high - low) / 2;
            if (arr[center] <= target) low = center + 1;
            else high = center - 1;
        }
        for (int j = i; j > low; j--) { // 移动
            arr[j] = arr[j - 1];
        }
        arr[low] = target; // 插入
    }
    return arr;
}

四.希尔排序

希尔排序是简单插入排序的改进，它基于一下事实：

1. 简单插入排序对排序程度较高的序列有较高的效率。假设初始序列已完全排序，则每一轮均只需比较一次，将得到 O(n)的线性复杂度，冒泡排序和选择排序做不到这一点，均仍需O(n^2) 次比较(冒泡排序在应用提前结束优化后可以做到)。
2. 简单插入排序每次比较最多将数字移动一位，效率较低。

对原待排序列中相隔gap的数字执行简单插入排序，然后缩小gap，对新的gap间隔的数字再次执行简单插入排序，以一种规则减少 gap 的大小，当 gap 为1时即简单插入排序，因此希尔排序也称作 增量递减排序。

稳定性：

不稳定

复杂度分析：

Shell增量：n/2^k，最坏时间复杂度为O(n^2)

代码：

vector<int> shellSort(vector<int> &arr)
{
    if(arr.size()<2) return arr;
    int n = arr.size();
    for(int gap = n/2;gap>0;gap /=2)
    {
        for(int start = 0;start<gap;start++)
        {
            for(int i = start+gap;i<n;i+=gap)
            {
                int target = arr[i],j = i-gap;
                for(;j>=0;j-=gap)
                {
                    if(target<arr[j])
                    {
                        arr[j+gap] = arr[j];
                    }
                    else
                    {
                        break;
                    }
                }
                if(j != i-gap) arr[j+gap] = target;//表示发生移动才插入
            }
        }
    }
    return arr;
}

五.归并排序

归并排序是 分治思想 的应用，即将原待排数组 递归或迭代地 分为左右两半，直到数组长度为1，然后对左右数组进行合并(merge)，在合并中完成排序。

递归轨迹为：

稳定性：稳定

六.快速排序

确定主轴和分区是快速排序的核心操作，先在数组中确定一个主轴元素，然后将数组分为两部分，小于主轴的放左侧，大于等于主轴的放右侧。递归的对主轴两侧元素执行这个过程，每次递归都传入待排序数组 arrarr 和本次要处理的部分的左右界，只处理这个范围内的序列。当所有递归都到达基准情形时，排序完成。因为是原地交换，递归过程中 arrarr 总是在动态排序，递归过程无需返回，为尾递归形式。

快速排序中的 核心方法为 partitionpartition。 partitionpartition方法执行后，要实现主轴左边元素均小于主轴，主轴右边元素均大等于主轴元素。

选定一个数作为主轴后（无论是上述哪种方法选取主轴元素， 都将选定的主轴置于当前数组的起始位置 ），设置一个 index (index = pivot + 1) 动态更新最终的主轴下标。从左到右将主轴后的所有元素依次与主轴元素比较，若小于主轴则将该数字与下标为 indexindex 的数字交换，indexindex 右移一位，使得 indexindex 的前一位总是当前最后一个小于主轴的元素。遍历比较结束后，交换下标为 pivotpivot 与 index - 1index−1 的数字，并将当前主轴的下标 index - 1index−1 返回。

稳定性：不稳定

复杂度分析：

时间复杂度：平均 / 最好为 O(nlogn)O(nlogn)，最坏为 O(n^2)O(n2)。

代码：

递归快排：

// 三数取中快排
public int[] quickSortMedian3(int[] arr) {
    if (arr.length < 2) return arr;
    quickSortMedian3(arr, 0, arr.length - 1); // 后两个参数是下标值
    return arr;
}

private void quickSortMedian3(int[] arr, int left, int right) {
      if (left < right) { 
        // 执行median3将左，中，右三数中值放到left位置上
        median3(arr, left, right);
        int pivot = partition(arr, left, right);
        quickSortMedian3(arr, left, pivot - 1);
        quickSortMedian3(arr, pivot + 1, right);
    }
}


// 将left, center, right下标三个数中，大小居中者放到left下标处
private void median3(int[]arr, int l, int r) {
    int c = l + (r - l) / 2;
    if (arr[l] > arr[c]) swap(arr, l, c); // 左中，大者居中
    if (arr[c] > arr[r]) swap(arr, c, r); // 中右，大者居右，此时最大者居右
    if (arr[c] > arr[l]) swap(arr, l, c); // 左中，大者居左，此时中者居左
}

// 随机主轴快排
public int[] quickSortRandom(int[] arr) {
    if (arr.length < 2) {
        return arr;
    }
    quickSortRandom(arr, 0, arr.length - 1);
    return arr;
}

private void quickSortRandom(int[] arr, int left, int right) {
    if (left < right) {
        // 取区间内随机下标，注意Random().nextInt(int x)方法的使用（含0不含x）
        int randomIndex = new Random().nextInt(right - left) + left + 1; // 在[left + 1, right]范围内的随机值
        // 交换随机取得的下标元素与当前起始元素
        swap(arr, left, randomIndex); // arr[left]与它之后的某个数交换
        int pivot = partition(arr, left, right);
        quickSortRandom(arr, left, pivot - 1);
        quickSortRandom(arr, pivot + 1, right);
    }
}

// 朴素快排(首位为主轴)
public int[] quickSortSimple(int[] arr) {
    if (arr.length < 2) return arr;
    quickSortSimple(arr, 0, arr.length - 1); // 后两个参数是下标值
    return arr;
}

private void quickSortSimple(int[] arr, int left, int right) {
    // 若left == right，表示此时arr只有一个元素，即为基准情形，完成递归(准确说是完成递进)
    // (尾递归，“回归”过程中不做任何事情）
    if (left < right) {
        int pivot = partition(arr, left, right);
        quickSortSimple(arr, left, pivot - 1);
        quickSortSimple(arr, pivot + 1, right);
    }
}

//　partition方法
private int partition(int[] arr, int left, int right) {
    int pivot = left, index = pivot + 1;
    // 注意此时right是坐标，要执行到最后一个元素，所以是<=
    for (int i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, index, i);
            index++;
        }
    }
    // 最后一个小于主轴元素的元素下标是index - 1
    swap(arr, pivot, index - 1);
    return index - 1;
}

七.堆排序

将输入数组建成一个大顶堆，之后反复取出堆顶并对剩余元素重建大顶堆，将依次取出的堆顶逆序排列，即可将原数组从小到大排列完成排序。

稳定性：不稳定

八.计数排序

计数排序是我们介绍的第一种 非比较排序，通常 适用于整数数组，是一种利用整数特点取得 线性复杂度 的非比较排序方法。假设待排序数组 arrarr 为正整数数组， 朴素 的计数排序过程如下：

创建一个计数数组 countArrcountArr ，其大小为 arrarr 中的最大值 maxmax 再加 1。

遍历 arrarr ，每读取一个arr[i]arr[i] ，直接令countArr[arr[i]]++countArr[arr[i]]++。

从下标 1 开始遍历 countArrcountArr ，依次输出 counter[i]counter[i] 个 ii ，即为排序结果。

稳定性：取决于是否采用稳定性优化版本

时间复杂度：

O(n+k)，n为元素个数，k为计数数组大小

九.基数排序

【基】指的是数的位，例如十进制数123，先对最低位进行排序，之后将结果写回arr，之后挨个位遍历排序，最后一位完成之后，arr则为排列好的

稳定性：稳定

十.桶排序

桶排序将原数组划分到称为 「桶」 的多个区间中，然后对每个桶单独进行排序，之后再按桶序和桶内序输出结果。适合于分布较均匀的数据，具体做法如下。

根据数据规模按照 一定的方法 将待排序数组arr划分为多个区间，每个区间称作一个桶。

每个桶可以是数组，也可以是泛型容器，用于保存arr中落在该桶范围内的数。

对每一个桶都单独排序，需要 以适当的排序 方法支持，例如插入排序，快速排序等。

所有桶完成排序后，按桶序，桶内序依次输出所有元素，得到arr的排序结果。

稳定性：取决于桶内排序方法的稳定性。

内连接和外连接

内连接：

合并具有同一列的两个以上的表的行，结果集中不包含一个表与另一个表不匹配的行（交集）

外连接：

合并具有同一列的两个以上的表的行，结果集中除了一个表与另一个表匹配的行之外，还查询到了左表或右表中不匹配的行

外连接的分类：

左外连接，右外连接，满外连接

DHCP与NAT的含义与作用

两个协议都是IP协议

DHCP（动态主机配置协议）是一个局域网的网络协议。指的是由服务器控制一段IP地址范围，客户机登录服务器时就可以自动获得服务器分配的IP地址和子网掩码。

NAT英文全称是“Network Address Translation”，中文意思是“网络地址转换”，它允许一个整体机构以一个公用IP地址出现在Internet上。

顾名思义，它是一种把内部私有网络地址（IP地址）翻译成合法网络IP地址的技术。简单的说，NAT就是在局域网内部网络中使用内部地址，而当内部节点要与外部网络进行通讯时，就在网关（可以理解为出口，打个比方就像院子的门一样）处，将内部地址替换成公用地址，从而在外部公网（internet）上正常使用，NAT可以使多台计算机共享Internet连接，这一功能很好地解决了公共IP地址紧缺的问题。

• 知识补充：

子网掩码的作用：

子网掩码是一种划分网络号与主机号的形式，掩码的意思就是掩盖掉主机号，剩余的就是网络号

将子网掩码与IP地址按位计算AND，就可得到网络号

为什么要分离主机号和网络号？

因为两台计算机要通讯，首先要判断是否处于同一个广播域内，即网络地址是否相同。如果网络地址相同，表明接受方在本网络上，那么可以把数据包直接发送到目标主机。

路由器寻址工作中，也就是通过这样的方式来找到对应的网络号的，进而把数据包转发给对应的网络内。

怎么进行子网划分？

在上面我们知道可以通过子网掩码划分出网络号和主机号，那实际上子网掩码还有一个作用，那就是划分子网。

子网划分实际上是将主机地址分为两个部分：子网网络地址和子网主机地址。形式如下：

• 未做子网划分的 ip 地址：网络地址＋主机地址
• 做子网划分后的 ip 地址：网络地址＋（子网网络地址＋子网主机地址）