今天，我们开始做一个动作类游戏。

美术资源

我们先下载今天要用到的美术资源。

链接：https://pan.baidu.com/s/1Vci83yoTRvViXIXElZ4k0g?pwd=tynm

提取码：tynm

新建项目。

把美术资源拖进项目。

创建角色

我们创建个文件夹，就叫Player。

创建角色蓝图。

我们再创建一个玩家控制器。

这时候我们再添加一个游戏模式。

然后我们改下GameMode的类默认值细节的设置。

编译保存。然后改一下默认游戏模式。改成我们刚建的。

返回资源浏览器。编辑PlayerChar。给它添加个模型。

调整下位置，旋转。

选中胶囊体组件，把胶囊体半高改成92。

然后添加摄像机。

然后调整下弹簧臂的位置。

编译保存运行。

移动

编辑PlayerChar。添加自定义事件。

增加ScaleValue变量编译。

保存编译。返回项目设置。

添加轴映射。

然后我们打开Controller。

编辑。

编译保存。现在角色可以向前向后移动了。左右也是。

然后再在项目设置里加一个轴。

然后控制器也加上左右。

前后左右都没有问题。现在回到项目设置添加视角。

返回playerchar。

编译保存运行。ok行走没问题了。

移动动画

现在要创建动画蓝图了。

打开动画蓝图编辑。保存。

新建一个混合空间。

点击编辑混合空间。在资产详情里修改水平坐标。

拖动idle_eqip_01到最左。

然后把walk_eqip_front拖到速度为1时的地方。

让速度到3时跑。

保存。等于走有三种状态。

然后再打开动画蓝图。

点开状态机。

添加状态。

进去Idle/Run状态。

把Speed提升为变量。

然后点击事件图表。

保存，打开playerchat。点网格体。设置动画类。

编译保存，运行。现在可以跑了。

现在输入我们加一个慢走。

打开玩家PlayerCharController。编写走路。

编译保存运行。现在可以慢慢地走了。

武器
现在我们加一下武器。在playerChar中加一个骨骼网格体。

然后父项插槽选Sword_1。资产也选一下。

编译保存运行。

连招系统

攻击

找到这个动作。

然后创建动画蒙太奇。

然后绑定下按键。

然后打开PlayerChat。添加自定义事件。

然后我们找到角色的控制器。加上攻击。

运行发现胶囊体没有跟角色移动。找到动画，启动根运动。

现在胶囊体会跟角色移动了。角色会跟着攻击动画移动。打开PlayerChar。让角色每次攻击都能连续。不会因双次按下攻击按键而抽搐。增加一个变量，用来判断是否在攻击中。

完整蓝图。

现在连点不会抽搐了。

连招

删掉攻击的逻辑，开始编写连招逻辑。

增加变量。并使用数组。

这里要多少个连击动作，就加多少个数组就可以了。

接着，我们找到连击动作。

创建动画蒙太奇。

然后找到Combo_01动画。

我们分解下连招动画。找到第一下下剑时的结束时间。调整结束时间。

然后做连招第二下的动画。

然后做连招第三下的动画。

然后做连招第四下的动画。

所有分解的招式。

然后返回PlayerChar。编辑连招逻辑。

然后找到刚创建的数组变量。

把四个连招动作按顺序赋予数组。

然后我们添加一个变量，用来计数攻击次数。

初始值设为-1。

然后编译下蓝图。

攻击先判断是否在攻击。

然后攻击次数加1。

然后判断攻击次数是否大于招式动画的长度。

如果小于招式动画的长度就获取一下招式。

如果大于招式动画的长度就把，Attack count归零。

然后设置一下ComboReset。

接着找到动画Combo_01_1_Montage，然后在攻击后摇前，大概在8后，右键加一下动画通知。

在动画结束时也加一下动画通知。

动画234也一样。

加完通知后，接着我们使用下通知。 打开PlayerCharABP。

在ComoStart通知时去做Do Attack。

然后再动画播放结束时，把所有的状态设置为初始值。

然后在动画蒙太奇里设置下混出混入时间。让混出混入时间远小于本身动画的时间。

然后创建一个保存攻击的状态。

SaveAttack开始时也要保存下。

然后把动画蓝图里的DoAttack改成AttackSave就可以连击出连招了。

https://github.com/user-attachments/assets/801d8e67-cbcd-4e1b-846b-c73e4299567a

更好的打击感

上面已经把攻击连招讲完了，但是攻击的时候不能转向，他只能朝着一个方向走，手感不是很好。下面完善一下攻击。然后做出攻击时可转向，添加闪避以及伤害通知。

攻击时可转向

一个流畅的动作类游戏，他必须得是非常跟手的。随时都跟着你的操作。在你攻击的时候，他应该也能跟着转向。这样才是一个好的动作游戏的手感。

打开playerchar。

新建一个函数。

用这个函数计算最后一次输入。就是要用这个函数获取最后一次键盘是按的哪个方向。这个函数不能单独使用，得配合其它函数使用。

新建一个变量，用来保存我们的输入movement。

还要新建一个变量，用来保存我们最后一次输入的角度。

我们把角色移动拖进来。

把角色最后输入的向量存到Movement Input。

我们还需要加一个变量，用来检测砍一刀时，有没有输入向量。

输入角度也保存一下。

这样这个函数是算写完了。

然后我们返回事件图表，让每帧都执行一下。

然后我们再创建一个函数。用这个函数改变角度。就是要让攻击动画改变角度。

添加两个输入。

先判断下输入的两个值。

然后就可以对角度设置渐变推进。

也设置下没有速度的时候的情况。

然后我们做下动画通知。新建一个文件夹。

创建一个AnimNotifyState蓝图。

打开编辑。新建变量。

然后重载一下函数。

然后找个动画试试。找到攻击这个蒙太奇。

添加状态通知。

表于在这段区间之间都可以转向。就是攻击前摇时可以选择方向。

然后回到RotationByAnim，把InterpSpeed变量小眼睛点开。

编译。回到动作就可以看到这个变量了。

然后设置这个渐变速度为10。

然后把其它的动画也设置下。

然后接下来我们开始写这个动画通知的函数。

我们再重载下两个函数。

现在攻击时可以转向了。
https://github.com/user-attachments/assets/f2124445-7383-46ad-b3cc-a05e40cee7fb

伤害通知

直接在动画序列中加通知。

接着我们回到playerchar写伤害逻辑。

然后我们返回动画蓝图。

运行可以看到攻击的范围。
https://github.com/user-attachments/assets/d1f9993d-0546-469f-a9c4-45f4dbdc1316

闪避

我们先加一下按键。

然后我们找个动画。创建动画蒙太奇。

然后回到动画。把启动根运动勾上。

角色就能跟着胶囊体动了。

然后我们写一下闪避的逻辑。

在控制里也加一下。

编译保存运行。
https://github.com/user-attachments/assets/6e411bef-0ddc-465b-b158-d4b264e40361

但反复按会鬼畜。这里改一下。

然后在动画播放完后状态设置为不翻滚。

编译保存运行。

现在反复按不会鬼畜了。

这里可以加速动画播放让翻滚快点。

闪避时可转向

直接给这个通知拉满，只要在翻滚的过程就能改变方向。

修复攻击时闪避后不能再攻击的Bug

因为攻击中闪避而没有走ComboReset。所以IsAttack永远为真。所以在闪避后再做一下ComboReset就可以了。

闪避时不能攻击

如果在闪避中，就不要给角色攻击了。

创建敌人

按照惯例，先创建一个文件夹。

创建模型

然后创建一个蓝图。

然后打开它。给它加个模型。

调下参数。

然后改一下这个模型的颜色。

再原来的材质上复制多一份。

双击新的材质，我们改下颜色。

点应用，保存。回来看，白色的材质球就做好了。

然后回到AIChar，模型换个颜色。

敌人AI

然后我们创建一个AIController。

然后还要一个行为树。

打开AICharController。在事件开始时运行行为树。

然后在AIChar里关联上AICharController。

编译保存。然后我们打开行为树，新建一个黑板。

给AI也创建下动画蓝图。

然后打开它。

双击状态机添加状态。

因为都是小白人，所以AI也可以用之前创建的混合空间。

speed提升为变量。

编译保存。

然后回到AIChar。使用刚才的动画蓝图。

然后给敌人加下武器。加下骨骼网格体。

然后加一下盾。

然后我们返回动画蓝图。

我们动画蓝图算是写完了。AI也会根据它移动的速度来决定它动画是走是跑还是站立。这些都是和主角一样的。然后我们写下行为树。

然后新建一个装饰器。

用来检测有没有玩家。

然后取一下位置。

然后需要加一下球形检测。

Object Types提升为变量。

半径给1000。

然后Draw Debug Type改成持久。

最后连上。

输出会Out Hits打开。

然后把每个数组再break一下。

如果这个球体检测到玩家，那就转化为玩家。检测不到就什么都不干。

然后as player char给他设置黑板值。

然后把Key提升为变量。

把小眼睛点亮，这样你在行为树上才能看到这个变量。

然后返回节点也连上。在循环结束之后返回为真。

编译保存。返回行为树。添加装饰器。

然后点击黑板，在黑板上新建一个值。

改下基类。

保存。

把顺序换成选择。

然后再来个顺序。再加个装饰器。

再来个顺序。

设置未设置。用于没检测到玩家的操作。

检测到玩家就走向玩家。

保存。给场景添加一个导航网格体边界体积。

调整导航网格体边界体积，让它覆盖整个场景。保存运行。现在可以看到敌人走过来了。
https://github.com/user-attachments/assets/b852159c-7af5-4355-939e-5cbf04939564

参数调整

AI追到你后的等待时间可以自行调整。

敌人的速度也可以调整下。

添加巡逻

新建一个服务。

打开，重载下接收Tick AI。

然后先取一下位置。

然后得到一个随机可以到达的位置。

设置半径为500。

然后把得到的位置设置为黑板键。

把Key提升为变量。改一名。

小眼睛打开。

最后把线连上。

编译保存。

返回行为树。添加服务。

返回黑板。增加一个向量变量。

返回行为树，把Target Location改为目的地。

移动到目的点。

保存。运行。现在AI能随机走动了。

攻击

然后在行为树新加一个任务，让敌人攻击。

打开，重载下接收执行AI函数。

转化为AIChar，直接播放蒙大奇。

给AI找个攻击动画。

创建一个动画蒙太奇。

打开动画，启动下根运动。让他播放这个动画时有位移。

返回任务，指定动画资产为Attack_08_Montage。

最后返回执行结果。

然后返回行为树。添加攻击。

编译保存运行。现在敌人会先过来再攻击，等待两秒再攻击。
https://github.com/user-attachments/assets/7590acab-f16d-413a-9b09-176d8f08e8de

添加伤害

玩家打AI

先给AI加点变量。

接着回到主角这里，编辑攻击逻辑。

基础伤害给到10。

主角这边的攻击伤害算写完了。

返回AIChar，继续写敌人被打的逻辑。

保存编译运行。

打印了很多。需要关掉一些没必要的碰撞。

主角这边也改一下。

现在的攻击输出就正常了。

因为AI会档主角的摄像机，所以AI的胶囊机碰撞的自定义下。

死亡

先加个变量判断是否死亡。

UI

敌人血条

新建UI文件夹。

我们做一下血条。新建UI控件蓝图。

然后打开它。新加画布。

然后加个进度条。

锚点改成中间。

然后把位置设置回来。

对齐都改成0.5。

尺寸y改成15。

填充颜色改成红色。

然后创建绑定。

添加对象变量。

用现血量除以总血量得到血条的百分比。

编译保存。回到AIChar。

添加控件组件。

改名为血条。

控件类是AIHPBar。

血条放到头顶上。

给它空间设为屏幕。

编译保存。回到事件图表。

把HPBar拖进来。

这样血条就加上了。

玩家血条
接着我们做一下玩家的血条。

新建个控件蓝图。

编译保存。然后在PlayerChar里加点变量。

然后回到PlayerHPBar创建绑定。

然后我们回到PlayerChar。

编译保存运行。

让玩家受伤
直接在动画Attack08里新建一个通知。

新建通知后，需要一个球形检测。

基本和之前写的玩家攻击逻辑一样。

然后返回PlayerChar。先加个变量。

然后回到AIChar_ABP。

保存编译，运行。现在敌人打玩家，玩家会扣血了。

AI被打动画
找到这个被打动画。

然后创建动画蒙太奇。

打开AIChar。

AI死亡动画
找到这个动画。

创建动画蒙太奇。

返回AIChar编写死亡动画逻辑。

动画要设置根运动。

在动画蒙太奇中不设置启动自动混出。敌人死亡倒地就结束了。

然后找到AI攻击。

让AI攻击前加个判断 ，判断是否正在播动画。

接着回到AIChar。在死亡后删除胶囊体。

编译保存运行。

把AI的攻击动画换成原地的
现在AI攻击会向前，对于游戏来说，玩家不容易闪避。我们给AI换个原地攻击的动画。敌人呆一点比较好。选一个腿没有动的。

然后创建蒙太奇。

动作启动根运动。

在AI攻击蓝图中改用这个动画。

当然，也要加上动画通知。

增加AI攻击前摇时间
打开攻击的动画蒙太奇，再拉一个动作。

把第一段做成0.138。

把前摇速率放慢。

现在敌人的攻击前摇时间加长了，玩家容易闪避了。

玩家被攻击动画
找到玩家被打动画。

然后启用根运动。

创建动画蒙太奇。

然后回到PlayerChar。增加被攻击动画。

每次受到伤害重置下玩家的攻击，防止玩家攻击时被攻击而不能再攻击。

玩家被死亡动画

把红框去掉

事务的特性

原子性
要么全部执行成功，要么全部执行失败。

一致性
执行前后，数据始终处于一致的状态。

隔离性
两个事务之间互不干扰，事务a完成前，事务b不会读取事务a操作时的变化。

持久性
事务的操作会被持久化到数据库，并且不会被回滚。

事务的类型

扁平事务，带有保存点的扁平事务，链式事务，嵌套事务，

并发事务带来的问题

更新丢失（脏写），后者覆盖前者

脏读，一个事务读取了另一个事务未提交的数据

不可重复读，一个事务读取了某些数据，在一段时间后，这个事务再次读取之前读过的数据，此时数据被更改或删除了

幻读，一个事务按照相同的查询条件重新读取之前读过的数据，此时发现其他事务插入了满足当前事务查询条件的新数据。这是针对数据的插入。

##mysql中锁的分类
按性能：悲观锁、乐观锁（乐观锁是通过版本对比来实现的）
按操作类型：读锁，写锁（这两都是悲观锁）
读锁又称为共享锁或S锁（shared Lock）
写锁又锁为排他锁或L锁（Exclusive Lock）
按数据粒度：表锁，行锁，页面锁
按更细粒度：间隙锁、临键锁

死锁的必要条件（4个都满足，才会发生死锁）

1互拆条件
2不可剥夺条件
3请求与保持条件
4循环等待条件

处理死锁的方法

1预防死锁，破坏造成死锁的4个必要条件中的一个或多个，以防止死锁的发生。
2避免死锁，在资源分配中，使用策略防止系统进入不安全状态，从而避免死锁的发生。
3检测死锁
4解除死锁
在实际工作中，，通常采用有序资源分配法和银行家算法来避免死锁。
在mysql中，通常通过以下几种方式来避免死锁
1尽量让数据表中的数据检索都通过索引来完成，避免无效索引导致锁升级为表锁
2合理设计索引，尽量缩小锁的范围
3尽量减少查询条件的范围，尽量避免间隙锁或缩小间隙锁的范围
4尽量控制事务的大小，减少一次事务锁定的资源数量，缩短锁定资源的时间
5如果一条sql语句涉及事务加锁操作，则尽量将其放在整个事务的最后执行
6尽可能使用低级别的事务隔离机制

mysql事务的实现原理

mysql中事务的隔离性是由锁和MVCC机制实现的，原子性和持久性是由redo log实现的，一致性是由undo log实现的。
redo log是重做日志，提供前滚操作(binlog中有数据,commit)，undo log是回滚日志，提供回滚操作。
redo log与binlog的区别
1binlog是mysql本身就拥有，而redolog是innodb特有的。
2两种日志记录的内容形式不同。MySQL的binlog是逻辑日志，其记录是对应的SQL语句。而innodb存储引擎层面的redolog日志是物理日志，保存了数据库中的值。
3两种日志记录写入磁盘的时间点不同，二进制日志只在事务提交完成后进行一次写入。而InnoDB 存储引擎的重做日志在事务进行中不断地被写入（不断地写入redo log buffer，不断地刷新）
4binlog不是循环使用，在写满或者重启之后，会生成新的binlog文件，redo log是循环使用。
5binlog可以作为恢复数据使用，主从复制搭建，redo log作为异常宕机或者介质故障后的数据恢复使用。

xa

xa事务是一种基于两阶段提交和分布式事务。prepare，commit。

数据一致性问题

1.数据多副本场景
2.调用超时场景
3.缓存与数据库不一致场景
4.多个缓存节点数据不一致场景

分布式事务的理论知识

桶排序（Bucket Sort）

桶排序是计数排序的升级版。顾名思义，会使用「桶」，核心思想就是 把要排序的的数据分到几个有序的桶里，每个桶里面的数据在单独进行排序，所有的桶内数据排序完成后，再按照桶的顺序依次取出，组成的序列就是有序的。

为了桶排序的高效，我们需要做到以下两点：
1.在额外空间充足的情况下，尽量增加桶的数量。
2.使用的映射函数能够把输入的 n 个数据均匀的分配到 k 个桶中。

同时，对于桶内元素的排序，选择哪一种排序算法对于性能的影响也至关重要。

如何把百万级别的订单根据金额排序

适用场景

比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大而内存有限，无法一次性全部加载到内存中。

比如说我们有 10GB 的订单数据，我们希望按订单金额（假设金额都是正整数）进行排序，但是我们的内存有限，只有几百 MB，没办法一次性把 10GB 的数据都加载到内存中。这个时候该怎么办呢？

订单金额最小是 1 元，最大是 10 万元。我们将所有订单根据金额划分到 100 个桶里，第一个桶我们存储金额在 1 元到 1000 元之内的订单，第二桶存储金额在 1001 元到 2000 元之内的订单，以此类推。每一个桶对应一个文件，并且按照金额范围的大小顺序编号命名（00，01，02…99）。
理想的情况下，如果订单金额在 1 到 10 万之间均匀分布，那订单会被均匀划分到 100 个文件中，每个小文件中存储大约 100MB 的订单数据，我们就可以将这 100 个小文件依次放到内存中，用快排来排序。等所有文件都排好序之后，我们只需要按照文件编号，从小到大依次读取每个小文件中的订单数据，并将其写入到一个文件中，那这个文件中存储的就是按照金额从小到大排序的订单数据了。

实现

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

const int len=sizeof(a)/sizeof(int);

void bucketSort(int a[])
{
    int b[10][len+1]={0};//将b全部置0

    int digits=numOfDigits(a);
    for(int i=1;i<=digits;i++)
    {
        distributeElments(a,b,i);
        collectElments(a,b);
        if(i!=digits)
            zeroBucket(b);
    }
}

int numOfDigits(int a[])
{
    int largest=0;
    for(int i=0;i<len;i++)//获取最大值
    {
        if(a[i]>largest)
            largest=a[i];

        int digits=0;//digits为最大值的位数
        while(largest)
        {
            digits++;
            largest/=10;
        }
    }
    return digits;
}

void distributeElments(int a[],int b[10][len+1],int digits)
{
    int divisor=10;//除数
    for(int i=1;i<digits;i++)
        divisor*=10;
    for(int j=0;j<len;j++)
    {
        int numOfDigist=(a[j]%divisor-a[j]%(divisor/10))/(divisor/10);
        //numOfDigits为相应的(divisor/10)位的值,如当divisor=10时,求的是个位数
        int num=++b[numOfDigist][0];//用b中第一列的元素来储存每行中元素的个数
        b[numOfDigist][num]=a[j];
    }
}

void collectElments(int a[],int b[10][len+1])
{
    int k=0;
    for(int i=0;i<10;i++)
        (int j=1;j<=b[i][0];j++)
            a[k++]=b[i][j];
}

void zeroBucket(int b[][len+1])
{
    for(int i=0;i<10;i++)
        for(int j=0;j<len+1;j++)
            b[i][j]=0;
}

总结

快排、归并是经济实用型小轿车。而桶排序、计数排序、基数排序则是赛道上的跑车竞速。

查日志

找到日志的位置，grep Exception backend.log 一把梭。

如果一个Exception不够，再来一个ERROR，反正把你能想到的关键词都想干净。

千万不要跟我说你查不到日志，如果是日志没有打印，请打印出来，磨刀不误砍柴工。如果是你没有权限查看，麻烦你一定要先搞到权限。千万千万要避免“猜”问题。一群人在那儿讨论半天，你猜我猜，最终猜出来的概率是比较低的，除非你见过这个BUG。

看状态

top一把，看看应用CPU占用率是不是异常的高。

load average根据CPU核心数来判断，CPU占用看是否为100%或异常的高。

看线程是否卡住

打印出所有线程栈之后，看看有没有你关心的线程卡住了，BLOCK或者wating之类的情况，然后看看他正在做什么调用

冒泡排序作为最简单的算法之一，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作就是重复地比较元素，直到元素们都落座了正确的位置，序列排序就算完成。
简而言之，将每次相邻两个关键字进行比较（0与1,1与2依次比较大小），小数上浮，大数下沉，每趟排序找出最大的数换到最右边。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端，“blue、blue~”

实现

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

void bubbleSort (int array[], int len) {
    int temp;
    int outer, inner;
    for (outer=0; outer<len-1; outer++) /* 外循环为排序趟数，len个数进行len-1趟 */
        for (inner=0; inner<len-1-outer; inner++) { /* 内循环为每趟比较的次数，第i趟比较len-i次 */
            if (array[inner] > array[inner+1]) { /* 相邻元素比较，若逆序则交换（升序为左大于右，降序反之） */
                temp = array[inner];
                array[inner] = array[inner+1];
                array[inner+1] = temp;
            }
        }
}

归并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

可以看到这种结构很像一棵完全二叉树，分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。

合并相邻有序子序列

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。

实现

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

void merge(int array[],int start,int range,int mid)
{
  int aux[range-start+1],i,j,k;
  
  for(k=start;k<=range;k++)
    aux[k-start]=a[k];
  
  i=start;
  j=mid+1;
  for(k=start;k<=range;k++)
  {
  	if(i>mid)
  	{
  		a[k]=aux[j-start];
  		j++;
	}
	else if(j>range)
	{
		a[k]=aux[i-start];
		i++;
	}
	else if(aux[i-start]>aux[j-start])
	{
		a[k]=aux[j-start];
		j++;
	}
	else
	{
		a[k]=aux[i-start];
		i++;
	}
  }	
}
 
void merge_sort(int array[],int start,int range)
{
    range = range - 1
    if(start>=range)
	    return ;
	
	int mid=(start+range)/2;
	
	merge_sort(array,start,mid);
	merge_sort(array,mid+1,range);
	merge(array,start,range,mid);	
}

假如 H 省有 80 万考生，如何通过成绩快速排序得出排名呢？

计数排序

计数排序是一种稳定的排序算法。 它的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。但是，计数排序也是很高冷！作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

沿用上面的例子。考生的满分是 750 分，最小是 0 分，符合我们之前说的条件：数据范围小且是整数。我们可以划分为 751 个桶分别对应分数为 0 ~ 750 分数的考生。
接着开始遍历考生数据，每个考生按照分数则划分到对应数组下标，相同数组的下标则将该下标的数据值 + 1。其实就是每个数组下标位置对应的是数列数据出现的次数，最后直接遍历该数组，输出元素的下标就是对应的分数，下标对应的元素值是多少我们就输出几次。
桶内的数据都是分数相同的考生，所以并不需要再进行排序。我们只需要依次扫描每个桶，将桶内的考生依次输出到一个数组中，就实现了 80 万考生的排序。因为只涉及扫描遍历操作，所以时间复杂度是 O(n)。

实现

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

public int[] countSort(int[] A) {
    // 找出数组A中的最大值
    int max = Integer.MIN_VALUE;
    for (int num : A) {
        max = Math.max(max, num);
    }
    // 初始化计数数组count
    int[] count = new int[max+1];
    // 对计数数组各元素赋值
    for (int num : A) {
        count[num]++;
    }
    // 创建结果数组
    int[] result = new int[A.length];
    // 创建结果数组的起始索引
    int index = 0;
    // 遍历计数数组，将计数数组的索引填充到结果数组中
    for (int i=0; i<count.length; i++) {
        while (count[i]>0) {
            result[index++] = i;
            count[i]--;
        }
    }
    // 返回结果数组
    return result;
}

如果我们要输出的不仅仅是分数还有学生信息呢，比如说从小到大输出所有学生的姓名和分数，那么这个时候也只要做一点小小的变动。
我们用一个结构体去表示一个学生，如下：

1
2
3
4
5

typedef struct students{ 
    char name[15];
    unsigned int score;
    students *next;
}student;

排序的过程中，我们依次遍历所有的学生分数，假设某个学生的分数为 i ,那么就在 score[i] 的后面插入该学生的节点。排完序后再按每个分数组打印链表中的学生姓名和分数。

适用场景

需要排序的元素必须是整数，二是排序元素的取值要在一定范围内（例子是0-750。如果只排350-750分段，数组长度需要删减），并且比较集中。只有这两个条件都满足，才能最大程度发挥计数排序的优势。

计数排序与桶排序

其实计数排序是桶排序的一种特殊情况（桶不用再排序）。 桶排序的核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

这是发生在很多年以前的故事……
咱们需要做一个拍卖行系统，用来查阅和出售游戏中的道具。
拍卖行的商品总数量有几十万件，对应数据库商品表的几十万条记录。
如果是按照商品名称精确查询还好办，可以直接从数据库查出来，最多也就上百条记录。
如果是没有商品名称的全量查询怎么办？总不可能把数据库里的所有记录全查出来吧，而且还要支持不同字段的排序。
所以，只能提前在内存中存储有序的全量商品集合，每一种排序方式都保存成独立的集合，每次请求的时候按照请求的排序种类，返回对应的集合。
比如按价格字段排序的集合：
比如按等级字段排序的集合：

拍卖行商品列表是线性的，最容易表达线性结构的自然是数组和链表。可是，无论是数组还是链表，在插入新商品的时候，都会存在性能问题。
按照商品等级排序的集合为例，如果使用数组，插入新商品的方式如下：

如果要插入一个等级是3的商品，首先要知道这个商品应该插入的位置。使用二分查找可以最快定位，这一步时间复杂度是O（logN）。
插入过程中，原数组中所有大于3的商品都要右移，这一步时间复杂度是O（N）。所以总体时间复杂度是O（N）。

如果使用链表，插入新商品的方式如下：

如果要插入一个等级是3的商品，首先要知道这个商品应该插入的位置。链表无法使用二分查找，只能和原链表中的节点逐一比较大小来确定位置。这一步的时间复杂度是O（N）。
插入的过程倒是很容易，直接改变节点指针的目标，时间复杂度O（1）。因此总体的时间复杂度也是O（N）。

这对于拥有几十万商品的集合来说，这两种方法显然都太慢了。

什么是跳跃表

这时候，可以用到跳跃表这种数据结构。
跳跃表是一种基于有序链表的扩展，简称跳表。
跳表利用类似索引的思想，提取出链表中的部分关键节点。比如给定一个长度是7的有序链表，节点值依次是
1->2->3->4->5->6->7->8。那么我们可以取出所有值为奇数的节点作为关键节点。

此时如果要插入一个值是4的新节点，不再需要和原节点8，7，6，5，3逐一比较，只需要比较关键节点7，5，3.

确定了新节点在关键节点中的位置（3和5之间），就可以回到原链表，迅速定位到对应的位置插入（同样是3和5之间）。

现在节点数目少，优化效果还不明显，如果链表中有1W甚至10W个节点，比较次数就整整减少了一半！
这样做法虽然增加了50%的额外的空间，但是性能提高了一倍。

不过我们可以进一步思考。既然已经提取出了一层关键节点作为索引，那我们为何不能从索引中进一步提取，提出一层索引的索引？

有了2级索引之后，新的节点可以先和2级索引比较，确定大体范围；然后再和1级索引比较；最后再回到原链表，找到并插入对应的位置。
当节点很多的时候，比较次数会减少到原来的四分之一。
当节点足够多的时候，不止能提出两层索引，还可以向更高层次提取，保证每一层是上一层节点数的一半。
至于提取的极限，则是同一层只有两个节点的时候，因为一个节点没有比较的意义。这样的多层链表结构，就是所谓的跳跃表。

跳跃表的插入

当大量的新节点通过逐层比较，最终插入到原链表之后，上层的索引节点会渐渐变得不够用。这时候需要从新节点当中选取一部分提到上一层。跳跃表设计者采用了一种有趣的办法：抛硬币。也就是随机决定新节点是否提拔，每向上提拔一层的几率是50%。
我们仍然借用刚才的例子，假如值为9新节点插入原链表。

因为跳跃表删除和添加的节点是不可预测的，所有很难用一种有效的算法来保证跳表的索引分部始终均匀。
随机抛硬币的方法虽然不能保证索引绝对均匀分布，却可以让大体趋于均匀。

总结一下，跳跃表插入节点的流程有以下几步：
新节点和各层索引节点逐一比较，确定原链表的插入位置。O（logN）

把索引插入到原链表。O（1）
利用抛硬币的随机方式，决定新节点是否提升为上一级索引。结果为“正”则提升并继续抛硬币，结果为“负”则停止。O（logN）
总体上，跳跃表插入操作的时间复杂度是O（logN），而这种数据结构所占空间是2N，既空间复杂度是 O（N）。

跳跃表的删除

删除操作比较简单，只要在索引层找到要删除的节点，然后顺藤摸瓜，删除每一层的相同节点即可。
如果某一层索引在删除后只剩下一个节点，那么整个一层就可以干掉了。还用原来的例子，如果要删除的节点值是5：

总结一下，跳跃表删除节点的步骤：
自上而下，查找第一次出现节点的索引，并逐层找到每一层对应的节点。O（logN）
删除每一层查找到的节点，如果该层只剩下1个节点，删除整个一层（原链表除外）。O（logN）
总体上，跳跃表删除操作的时间复杂度是O（logN）。

跳跃表与二叉查找树的区别

跳跃表的优点是维持结构平衡的成本比较低，完全依靠随机。而二叉查找树在多次插入删除后，需要rebalance来重新调整结构平衡。

在 TCP 通讯中主要有连接的建立、数据的传输、连接的关闭三个过程！每个过程完成不同的工作，而且序列号和确认号在每个过程中的变化都是不同的。

在 TCP 通讯中主要有连接的建立、数据的传输、连接的关闭三个过程！每个过程完成不同的工作，而且序列号和确认号在每个过程中的变化都是不同的。