反射的概念

允许程序运行时获取类内部信息，并且能操作对象的内部属性和方法。

但C++本身并没有反射的概念，需要通过第三方库来实现。

反射的目标：

1. 类对象反射。
2. 类成员数据反射。
3. 类成员函数反射。

注册时成员为public作用域
通过注册宏实现反射功能

归并排序

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

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

选择排序

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

简单选择排序

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

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)条边。