归并排序

算法思想：先将需要排序的元素分开，在合并的过程中将元素进行排序，最终得到一个有序数组。
分开方法：逻辑二分。

模拟：将数组拆分为单个元素

选择排序

每次从乱序区中选择一个最小的排序
分为简单选择排序和堆排序

简单选择排序

每次遍历都找到一个最小的元素，放在乱序区的第一个位置。

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

void SelectSort(int arr[], int n)
{
    for(int i=0;i<n;i++){
        int Min=i;
        for(int j=i+1;j<n;j++){
            if(arr[j]<arr[Min]){
                Min=j;
            }
        }
        swap(arr[i],arr[Min]);
    }
}

交换排序

基于比较的排序算法，通过不断交换元素的位置，使得排序的元素达到有序。
主要有冒泡排序和快速排序。

冒泡排序

冒泡排序思路与实现都很简单，通过不断比较两个相邻的元素，如果第一个元素比第二个元素大，则交换两个元素的位置，这样循环一轮下来，最大的元素就浮到了最右边。

同样将数组分为待排区和有序区，实现如下：

1
2
3
4
5
6
7
8
9
10

void BubbleSort(int* arr, int n) 
{
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-i-1;j++){
            if(arr[j]>arr[j+1]){
                swap(arr[j],arr[j+1]);
            }
        }
    }
}

有关排序的一些概念

时间复杂度：一个算法执行所耗费的时间。
空间复杂度：运行完一个程序所需内存的大小。
原地排序：空间复杂度为 O(1)，不需要申请额外的空间。
内部排序：待排序的元素全部存放在内存中。
外部排序：待排序元素很多，需要从外存中读取元素。
稳定性：排序前后两个相同元素的相对位置不变。

拓扑排序

一些概念

1. 有向无环图：有向说明图的路径是有方向的，无环说明图的路径不能成环。
2. 拓扑序列：设一个具有n个顶点的有向图，其中顶点序列V1—Vn满足一条路径，若Vi必须在Vj之前，则称这个顶点序列为拓扑序列。
3. 拓扑排序：按照顶点的依赖关系进行排序，使得没有前驱的顶点排在最前，没有后继的顶点排在后面，直到所有节点都被移除。

算法思想

它的思路总结起来只有两步：

1. 在有向图中选择一个没有前驱的顶点并输出。
2. 删除该顶点和以它为尾的弧。
3. 重复上述两步直到所有顶点都被输出，或者当前图中不存在无前驱的顶点为止。

蒙太奇动画

在UE中可以使用蒙太奇动画完成一些效果，完成人物的一些特俗运动，比如攀爬、跳跃、技能等等。
使用蒙太奇的动画只需要创建一个蒙太奇动画，插入一个slot和section，便可以在动画蓝图涨使用，我们可以不关心蒙太奇动画的实现细节而达到很好的表现效果。

散列表定义

散列表（HashTable，也叫哈希表），是根据关键码值(Key)而直接进行访问的数据结构。也就是说，它通过把键值映射到整数的方法(Value=f(Key))，来访问记录，这加快了查找速度。

在存储散列表时，通过散列函数来确定每个键值对应的存储位置，当我们要查找一个Key时，便可以通过散列函数直接找到Value的位置。

散列冲突：查找时可能会出现f(Key1)=f(Key2)这种情况，即两个不同的Key，通过散列函数计算出来的值相同，这种现象称为散列冲突。

关于最短路径的一些概念

源点：路径起始的第一个顶点。
终点：路径终止的最后一个顶点。
最短路径：对于无权图来说，就是从源点到终点经过的边数最少的路径；对于带权图来说，就是路径上权值之和最少的路径。

常用的最短路径算法有：SPFA算法、Dijkstra算法、Bellman-Ford算法、SPT算法、Floyd算法，将介绍Dijkstra算法和Floyd算法。

最小生成树的概念

最小生成树，即构造连通网的总代价（总权值）最小的树为最小生成树。

最小生成树的一些性质：

1. 最小生成树一定是连通的。
2. 如果去掉某条边，则最小生成树就不再连通。
3. 最小生成树的边数一定等于顶点数减1。
4. 一个连通图可以有多个生成树。
5. 生成树中不存在环。
6. 对于包含n个顶点的连通图，其最小生成树包含n-1条边。
7. 对于包含n个顶点的完全无向图，最多包含n^(n-2)条边。

图的概念

图（Graph）是由一组顶点(V)和一组能够将两个顶点相连的边(e)的非空有限集组成的。

例如：

定义一个图G=(V,E)，V={V1,V2,V3,V4},E={E1,E2,E3,E4,E5,E6}
E1=<V1,V2> E2=<V1,V3> E3=<V1,V4> E4=<V2,V3> E5=<V3,V2> E6=<V3,V3>

一些定义

基本概念

1. 有向边：一条边所代表的顶点是有序的，则为有向边，也称弧，例如< V1,V2 >和< V2,V1 >是不同的两个边或弧。
2. 无向边：一条边所带表的顶点是无序的，则为无向边，例如(V1,V2)和(V2,V1)是同一个边。
3. 弧的头尾：一条边从V1指向V2，则V1为弧尾，V2为弧头。
4. 度：一个顶点的度是指与它相连的边的数目，入度指入边数，出度指出边数。
5. 路径：从顶点V1到V2的路径是指从V1到V2的边所表示的顶点序列。
6. 权值：与图的边相关的数称为权值，带权值的图称为网。
7. 连通：若两个顶点之间存在路径，则称这两个顶点是连通的。

图的分类

1. 简单图：不存在顶点到自身的边且一条边不重复出现，这样的图称为简单图。
2. 无向图：图中任意一条边代表的顶点是无序的，则为无向图。
3. 有向图：图中任意一条边代表的顶点是有序的，则为有向图。
4. 完全图：图中任意两个顶点之间都存在边，则为完全图。
5. 连通图：图中任意两个顶点之间都存在路径，则为连通图，否则为非连通图。