A 星寻路算法

寻路消耗公式：f(寻路消耗)=g(离起点距离)+h(离终点距离)

开启列表：记录待检查的节点。
关闭列表：记录已检查的节点。

A 星（A*）寻路算法是一种图搜索算法，用于在网格图上找到从起点到终点的最短路径。

基本原理

初始化：将起点加入开启列表。设定起点的 g 值为 0，h 值为起点到终点的估算距离。

循环过程：从开启列表中取出 f 值最小的节点作为当前节点。将当前节点从开启列表移到关闭列表。

检查当前节点的所有相邻节点：如果相邻节点是终点，则路径找到，算法结束。如果相邻节点不在关闭列表中，计算其 g 值和 h 值，并将其加入开启列表。如果相邻节点已在开启列表中，检查新的 g 值是否更小，如果是则更新该节点的 g 值和父节点。

结束条件：如果开启列表为空，则表示没有找到路径。如果找到终点，则可以通过节点的父节点链回溯到起点，得到完整路径。

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
using System.Collections.Generic;

public class AStarPathfinding
{
    // 寻找路径的方法，输入起点和终点，返回路径上的节点列表
    public List<Node> FindPath(Node start, Node goal)
    {
        // 开放列表，存储待处理的节点
        List<Node> openList = new List<Node>();
        // 封闭列表，存储已处理的节点
        HashSet<Node> closedList = new HashSet<Node>();
        // 将起点添加到开放列表中
        openList.Add(start);

        // 当开放列表不为空时循环
        while (openList.Count > 0)
        {
            // 从开放列表中获取F值最小的节点作为当前节点
            Node currentNode = GetNodeWithLowestF(openList);
            // 如果当前节点为终点，则返回重构的路径列表
            if (currentNode == goal)
            {
                return ReconstructPath(currentNode);
            }

            // 将当前节点从开放列表移除，加入封闭列表
            openList.Remove(currentNode);
            closedList.Add(currentNode);

            // 遍历当前节点的邻居节点
            foreach (Node neighbor in currentNode.Neighbors)
            {
                // 如果邻居节点已在封闭列表中，则跳过
                if (closedList.Contains(neighbor))
                {
                    continue;
                }

                // 计算从起点经过当前节点到邻居节点的临时代价
                float tentativeG = currentNode.G + GetDistance(currentNode, neighbor);
                // 如果邻居节点不在开放列表中，或者新的G值比旧的小
                if (!openList.Contains(neighbor) || tentativeG < neighbor.G)
                {
                    // 更新邻居节点的父节点、G值、H值和F值
                    neighbor.Parent = currentNode;
                    neighbor.G = tentativeG;
                    neighbor.H = GetDistance(neighbor, goal);
                    neighbor.F = neighbor.G + neighbor.H;

                    // 如果邻居节点不在开放列表中，则加入开放列表
                    if (!openList.Contains(neighbor))
                    {
                        openList.Add(neighbor);
                    }
                }
            }
        }

        // 如果开放列表为空，则表示未找到路径，返回空
        return null; // Path not found
    }

    // 获取F值最小的节点
    private Node GetNodeWithLowestF(List<Node> nodes)
    {
        Node lowestFNode = nodes[0];
        foreach (Node node in nodes)
        {
            if (node.F < lowestFNode.F)
            {
                lowestFNode = node;
            }
        }
        return lowestFNode;
    }

    // 重构路径，从当前节点逆序遍历父节点直至起点，返回路径列表
    private List<Node> ReconstructPath(Node currentNode)
    {
        List<Node> path = new List<Node>();
        while (currentNode != null)
        {
            path.Add(currentNode);
            currentNode = currentNode.Parent;
        }
        path.Reverse();
        return path;
    }

    // 获取两个节点之间的距离
    private float GetDistance(Node a, Node b)
    {
        // 实现计算节点之间的距离逻辑
        return Vector3.Distance(a.Position, b.Position);
    }
}

// 表示地图上的节点
public class Node
{
    public Vector3 Position; // 节点位置
    public float G; // 离起点距离
    public float H; // 离终点距离
    public float F; // 总消耗
    public Node Parent; // 父节点
    public List<Node> Neighbors; // 邻居节点列表
}

冒泡排序

选择排序

插入排序

希尔排序

归并排序

快速排序

快速排序是一种基于分治思想的排序算法，它的主要思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以达到整个数据变成有序序列。

快速排序步骤：
从数列中挑出一个元素，称为”基准”（pivot）。重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

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
using System;

public class QuickSortExample
{
    public static void QuickSort(int[] array, int left, int right)
    {
        if (left < right)
        {
            int pivotIndex = Partition(array, left, right);
            QuickSort(array, left, pivotIndex - 1);
            QuickSort(array, pivotIndex + 1, right);
        }
    }

    private static int Partition(int[] array, int left, int right)
    {
        int pivot = array[right];
        int i = left - 1;
        for (int j = left; j < right; j++)
        {
            if (array[j] < pivot)
            {
                i++;
                Swap(array, i, j);
            }
        }
        Swap(array, i + 1, right);
        return i + 1;
    }

    private static void Swap(int[] array, int a, int b)
    {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

public class Program
{
    public static void Main()
    {
        int[] array = { 34, 7, 23, 32, 5, 62 };
        QuickSortExample.QuickSort(array, 0, array.Length - 1);
        Console.WriteLine(string.Join(", ", array));
    }
}

堆排序

二分法

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
using System;

class Program
{
    static int BinarySearch(int[] array, int target)
    {
        int left = 0;
        int right = array.Length - 1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2;

            if (array[mid] == target)
            {
                return mid; // 找到目标，返回索引
            }
            else if (array[mid] < target)
            {
                left = mid + 1; // 在右半部分继续搜索
            }
            else
            {
                right = mid - 1; // 在左半部分继续搜索
            }
        }

        return -1; // 如果找不到目标，返回 -1
    }

    static void Main()
    {
        int[] array = { 1, 3, 5, 7, 9, 11, 13 };
        int target = 7;

        int result = BinarySearch(array, target);

        if (result != -1)
        {
            Console.WriteLine($"目标 {target} 在数组中的索引是: {result}");
        }
        else
        {
            Console.WriteLine("目标不在数组中");
        }
    }
}

二分法（Binary Search）的原理是一种高效的搜索算法，适用于在有序的数组或列表中查找目标元素。该算法通过反复将搜索范围减半，从而大大减少了查找的时间复杂度。

原理详解

初始条件：假设数组已经排好序，并且我们知道待查找的目标值。我们使用两个指针，分别指向数组的左右边界（即 left 和 right 指针）。

查找过程：计算中间位置：计算当前搜索范围的中间索引 mid。mid = left + (right - left) / 2

比较中间元素：将中间位置的元素 array[mid] 与目标值 target 进行比较：

  • 相等：如果 array[mid] 等于目标值，则查找成功，返回 mid 索引。
  • 小于目标值：如果 array[mid] 小于目标值，则目标值一定在右半部分。因此，将 left 指针移动到 mid + 1，缩小搜索范围。
  • 大于目标值：如果 array[mid] 大于目标值，则目标值一定在左半部分。因此，将 right 指针移动到 mid - 1，缩小搜索范围。

终止条件：如果找到了目标值，返回其索引。如果 left 超过了 right，说明数组中不存在目标值，返回 -1 表示查找失败。