Unity知识总结——算法
文章目录
- 1.常见排序算法
- 1.冒泡排序
- 2.选择排序
- 3.插入排序
- 4.快速排序
- 5.归并排序
- 6.希尔排序
- 7.堆排序
- 8.桶排序
- 9.计数排序算法
- 10.基数排序算法
- 2. 常见查找算法
- 1.线性查找
- 2.二分查找
- 3.哈希查找
- 4.二叉查找树
- 5.平衡二叉查找树
- 6.跳表
- 7.Trie 树
- 8.Bloom Filter
- 3.空间切割算法
- 4.洗牌算法
- 5.一个数组长度为n-1,有1~n，n个数在里面但是缺了一个，如何用最快的方法找到这个数
- 6.如何计算某个时刻（ex–3:15）的分针和时针的夹角
1.常见排序算法
1.冒泡排序
简介：冒泡排序算法是一种基础的排序算法，它的实现原理比较简单。核心思想是通过相邻元素的比较和交换来将最大（或最小）的元素逐步"冒泡"到数列的末尾。
- 重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来
- 时间复杂度：平均情况和最坏情况下均为O(n^2)。
- 空间复杂度：O(1).
详细文章描述
/// <summary>
/// 递归方式实现冒泡排序
/// </summary>
/// <param name="arr">arr</param>
/// <param name="arrLength">arrLength</param>
public static void RecursiveBubbleSort(int[] arr, int arrLength)
{
if (arrLength == 1)
return;
for (int i = 0; i < arrLength - 1; i++)
{
if (arr[i] > arr[i + 1])
{
//交换arr[i]和arr[i+1]的值
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
RecursiveBubbleSort(arr, arrLength - 1);
}
public static void RecursiveBubbleSortRun()
{
int[] arr = { 1, 8, 9, 5, 6, 2, 3, 4, 7 };
int arrLength = arr.Length;
RecursiveBubbleSort(arr, arrLength);
Console.WriteLine("排序后结果：" + string.Join(", ", arr));
}
2.选择排序
简介：选择排序算法的基本思想是每一次从待排序的数据元素中选出最小或最大的一个元素，存放在序列的起始位置，然而，再从剩余未排序元素中继续寻找最小或最大元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。
- 每次从未排序的部分选择最小（或最大）的元素，放到已排序部分的末尾
- 时间复杂度：平均情况和最坏情况下均为 O(n^2)。
- 空间复杂度：O(1)。
详细文章描述
/// <summary>
/// 选择排序算法
/// </summary>
public static void SelectionSortAlgorithmMain()
{
int[] array = { 64, 25, 12, 22, 11, 99, 3, 100 };
Console.WriteLine("原始数组: ");
PrintArray(array);
SelectionSortAlgorithm(array);
Console.WriteLine("排序后的数组: ");
PrintArray(array);
}
static void SelectionSortAlgorithm(int[] arr)
{
int n = arr.Length;
for (int i = 0; i < n - 1; i++)
{
// 在未排序部分中找到最小元素的索引
int minIndex = i;
for (int j = i + 1; j < n; j++)
{
if (arr[j] < arr[minIndex])
{
minIndex = j;
}
}
// 将最小元素与未排序部分的第一个元素交换位置
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
static void PrintArray(int[] arr)
{
int n = arr.Length;
for (int i = 0; i < n; ++i)
{
Console.Write(arr[i] + " ");
}
Console.WriteLine();
}
3.插入排序
简介：插入排序算法是一种简单、直观的排序算法，其原理是将一个待排序的元素逐个地插入到已经排好序的部分中。
- 将未排序的元素逐个插入到已排序部分的合适位置。
- 时间复杂度：平均情况和最坏情况下均为 O(n^2)。
- 空间复杂度：O(1)。
详细文章描述
public static void InsertionSort(int[] array)
{
int arrayLength = array.Length;//数组长度（时间复杂度为O(n^2)）
for (int i = 1; i < arrayLength; ++i)
{
//定义临时变量
int temp = array[i];
int j = i - 1;
while (j >= 0 && array[j] > temp)
{
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
}
public static void InsertionSortRun()
{
int[] array = { 26, 15, 5, 3, 38, 36, 44, 27, 47, 2, 46, 4, 50, 19, 48 };
Console.WriteLine("排序前:" + string.Join(", ", array));
InsertionSort(array);
Console.WriteLine("排序后:" + string.Join(", ", array));
}
4.快速排序
简介：快速排序是一种常用的排序算法，它基于分治的思想，通过将一个无序的序列分割成两个子序列，并递归地对子序列进行排序，最终完成整个序列的排序。
- 选择一个基准元素，将小于基准的元素放到左侧，大于基准的元素放到右侧，再对左右两部分递归进行快排。
- 时间复杂度：平均情况下为 O(nlogn)，最坏情况下为 O(n^2)。
- 空间复杂度：O(logn)。
详细文章描述
public class 快速排序算法
{
public static void Sort(int[] array, int low, int high)
{
if (low < high)
{
//将数组分割为两部分，并返回分割点的索引
int pivotIndex = Partition(array, low, high);
//递归对分割后的两部分进行排序
Sort(array, low, pivotIndex - 1);
Sort(array, pivotIndex + 1, high);
}
}
private static int Partition(int[] array, int low, int high)
{
//选择最后一个元素作为基准元素
int pivot = array[high];
int i = low - 1;
for (int j = low; j <= high - 1; j++)
{
//如果当前元素小于等于基准元素，则将它与i+1位置的元素交换
if (array[j] <= pivot)
{
i++;
Swap(array, i, j);
}
}
//将基准元素放置到正确的位置上
Swap(array, i + 1, high);
return i + 1; //返回基准元素的索引
}
private static void Swap(int[] array, int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void QuickSortRun()
{
int[] array = { 2, 3, 5, 38, 19, 15, 26, 27, 36, 44, 47, 46, 50, 48, 4 };
Sort(array, 0, array.Length - 1);
Console.WriteLine("排序后结果：" + string.Join(", ", array));
}
}
5.归并排序
简介：归并排序是一种常见的排序算法，它采用分治法的思想，在排序过程中不断将待排序序列分割成更小的子序列，直到每个子序列中只剩下一个元素，然后将这些子序列两两合并排序，最终得到一个有序的序列。
- 将数组分成两半，对每一半进行递归归并排序，然后将两个有序的子数组合并成一个有序数组。
- 时间复杂度：平均情况下为 O(nlogn)。
- 空间复杂度：O(n)。
详细文章描述
public static void MergeSort(int[] arr, int left, int right)
{
if (left < right)
{
// 计算中间索引
int mid = (left + right) / 2;
// 对左半部分数组进行归并排序
MergeSort(arr, left, mid);
// 对右半部分数组进行归并排序
MergeSort(arr, mid + 1, right);
// 合并两个有序数组
Merge(arr, left, mid, right);
}
}
public static void Merge(int[] arr, int left, int mid, int right)
{
int n1 = mid - left + 1; // 左半部分数组的长度
int n2 = right - mid; // 右半部分数组的长度
// 创建临时数组
int[] leftArr = new int[n1];
int[] rightArr = new int[n2];
// 将数据拷贝到临时数组
for (int i = 0; i < n1; ++i)
{
leftArr[i] = arr[left + i];
}
for (int j = 0; j < n2; ++j)
{
rightArr[j] = arr[mid + 1 + j];
}
// 合并两个有序数组
int k = left; // 初始化合并后的数组索引
int p = 0; // 初始化左半部分数组的索引
int q = 0; // 初始化右半部分数组的索引
while (p < n1 && q < n2)
{
if (leftArr[p] <= rightArr[q])
{
arr[k] = leftArr[p];
p++;
}
else
{
arr[k] = rightArr[q];
q++;
}
k++;
}
// 复制左半部分数组的剩余元素
while (p < n1)
{
arr[k] = leftArr[p];
p++;
k++;
}
// 复制右半部分数组的剩余元素
while (q < n2)
{
arr[k] = rightArr[q];
q++;
k++;
}
}
public static void MergeSortRun()
{
int[] array = { 19, 27, 46, 48, 50, 2, 4, 44, 47, 36, 38, 15, 26, 5, 3 };
Console.WriteLine("排序前数组：" + string.Join(", ", array));
MergeSort(array, 0, array.Length - 1);
Console.WriteLine("排序后数组：" + string.Join(", ", array));
}
6.希尔排序
简介：希尔排序简单的来说就是一种改进的插入排序算法，它通过将待排序的元素分成若干个子序列，然后对每个子序列进行插入排序，最终逐步缩小子序列的间隔，直到整个序列变得有序。希尔排序的主要思想是通过插入排序的优势，减小逆序对的距离，从而提高排序效率。
- 将待排序数组划分成若干个间隔相等的子序列，对每个子序列进行插入排序，随着间隔的逐步缩小，直至间隔为1，最终对整个数组进行插入排序，使得整个数组基本有序。
- 时间复杂度：在 O(n^2)和O(n ^1.5) 之间。
- 空间复杂度：O(n)。
详细文章描述
public static void ShellSort(int[] array)
{
int arrLength = array.Length;
// 初始化增量（初始间隔）为数组长度的一半
int gap = arrLength / 2;
// 不断缩小增量，直到增量为1
while (gap > 0)
{
// 对每个子序列进行插入排序
for (int i = gap; i < arrLength; i++)
{
int temp = array[i];
int j = i;
// 在子序列内部进行插入排序
while (j >= gap && array[j - gap] > temp)
{
array[j] = array[j - gap];
j -= gap;
}
array[j] = temp;
}
// 缩小增量
gap /= 2;
}
}
public static void ShellSortRun()
{
int[] array = { 19, 20, 22, 32, 34, 50, 99, 49, 1, 11, 11, 55, 35, 93, 96, 71, 70, 38, 78, 48 };
Console.WriteLine("排序前数组：" + string.Join(", ", array));
ShellSort(array);
Console.WriteLine("排序后数组：" + string.Join(", ", array));
}
7.堆排序
简介：堆排序是一种高效的排序算法，基于二叉堆数据结构实现。它具有稳定性、时间复杂度为O(nlogn)和空间复杂度为O(1)的特点。
- 将待排序数组构建成最大堆，然后将堆顶元素与最后一个元素交换并重新调整堆，直到所有元素都排好序。
- 时间复杂度：平均情况下为 O(nlogn)。
- 空间复杂度：O(1)。
详细文章描述
public static void HeapSort(int[] array)
{
int arrayLength = array.Length;
//构建最大堆
for (int i = arrayLength / 2 - 1; i >= 0; i--)
Heapify(array, arrayLength, i);
//依次取出堆顶元素，并重新调整堆
for (int i = arrayLength - 1; i >= 0; i--)
{
//将堆顶元素与当前最后一个元素交换
int temp = array[0];
array[0] = array[i];
array[i] = temp;
//重新调整堆
Heapify(array, i, 0);
}
}
private static void Heapify(int[] arr, int n, int i)
{
int largest = i; //假设父节点最大
int left = 2 * i + 1; //左子节点
int right = 2 * i + 2; //右子节点
//如果左子节点大于父节点，则更新最大值
if (left < n && arr[left] > arr[largest])
largest = left;
//如果右子节点大于父节点和左子节点，则更新最大值
if (right < n && arr[right] > arr[largest])
largest = right;
//如果最大值不是当前父节点，则交换父节点和最大值，并继续向下调整堆
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
Heapify(arr, n, largest);
}
}
public static void HeapSortRun()
{
int[] array = { 19, 27, 46, 48, 50, 2, 4, 44, 47, 36, 38, 15, 26, 5, 3, 99, 888, 0, -1 };
Console.WriteLine("排序前数组：" + string.Join(", ", array));
HeapSort(array);
Console.WriteLine("排序后数组：" + string.Join(", ", array));
}
8.桶排序
简介：桶排序是一种线性时间复杂度的排序算法，它将待排序的数据分到有限数量的桶中，每个桶再进行单独排序，最后将所有桶中的数据按顺序依次取出，即可得到排序结果。
- 将元素分配到有限数量的桶中，对每个桶中的元素进行排序，然后按照顺序将桶中的元素输出。
- 时间复杂度：平均情况下为 O(n + k)，其中 k 表示桶的数量。
- 空间复杂度：O(n + k)。
详细文章描述
public static void BucketSort(int[] array)
{
int arrLength = array.Length;
if (arrLength <= 1)
{
return;
}
//确定桶的数量
int maxValue = array[0], minValue = array[0];
for (int i = 1; i < arrLength; i++)
{
if (array[i] > maxValue)
maxValue = array[i];
if (array[i] < minValue)
minValue = array[i];
}
int bucketCount = (maxValue - minValue) / arrLength + 1;
//创建桶并将数据放入桶中
List<List<int>> buckets = new List<List<int>>(bucketCount);
for (int i = 0; i < bucketCount; i++)
{
buckets.Add(new List<int>());
}
for (int i = 0; i < arrLength; i++)
{
int bucketIndex = (array[i] - minValue) / arrLength;
buckets[bucketIndex].Add(array[i]);
}
//对每个非空的桶进行排序
int index = 0;
for (int i = 0; i < bucketCount; i++)
{
if (buckets[i].Count == 0)
{
continue;
}
int[] tempArr = buckets[i].ToArray();
Array.Sort(tempArr);
foreach (int num in tempArr)
{
array[index++] = num;
}
}
}
public static void BucketSortRun()
{
int[] array = { 19, 27, 46, 48, 50, 2, 4, 44, 47, 36, 38, 15, 26, 5, 3, 99, 888};
Console.WriteLine("排序前数组：" + string.Join(", ", array));
BucketSort(array);
Console.WriteLine("排序后数组：" + string.Join(", ", array));
}
9.计数排序算法
简介：计数排序是一种非比较性的排序算法，适用于排序一定范围内的整数。它的基本思想是通过统计每个元素的出现次数，然后根据元素的大小依次输出排序结果。
- 时间复杂度：平均情况下为O(n+k)，最好最坏情况下也是O(n+k)，其中n为待排序数组的长度，k为最大值和最小值之差。
- 空间复杂度：O(n + k)。
详细文章描述
public static void CountingSort(int[] array)
{
int arrayLength = array.Length;
if (arrayLength <= 1) return;
int min = array[0];
int max = array[0];
//找出最大值和最小值
for (int i = 1; i < arrayLength; i++)
{
if (array[i] < min) min = array[i];
if (array[i] > max) max = array[i];
}
//统计每个元素出现的次数
int[] count = new int[max - min + 1];
//统计每个元素出现的次数
for (int i = 0; i < arrayLength; i++)
{
count[array[i] - min]++;
}
//根据count数组和min值确定每个元素的起始位置
for (int i = 1; i < count.Length; i++)
{
count[i] += count[i - 1];
}
//存储排序结果
int[] temp = new int[arrayLength];
//根据count数组和min值确定每个元素在temp数组中的位置
for (int i = arrayLength - 1; i >= 0; i--)
{
int index = count[array[i] - min] - 1;
temp[index] = array[i];
count[array[i] - min]--;
}
//将排序结果复制回原数组
for (int i = 0; i < arrayLength; i++)
{
array[i] = temp[i];
}
}
public static void CountingSortRun()
{
int[] array = { 19, 27, 46, 48, 50, 2, 4, 44, 47, 36, 38, 15, 26, 5, 3, 99, 888};
Console.WriteLine("排序前数组：" + string.Join(", ", array));
CountingSort(array);
Console.WriteLine("排序后数组：" + string.Join(", ", array));
}
10.基数排序算法
简介：基数排序是一种非比较性排序算法，它通过将待排序的数据拆分成多个数字位进行排序。
- 时间复杂度：平均情况下为O(d(n+r))，最好最坏情况下也是O(d(n+r))，d为位数，r为基数
- 空间复杂度：*O®
详细文章描述
public static void RadixSort(int[] array)
{
if (array == null || array.Length < 2)
{
return;
}
//获取数组中的最大值，确定排序的位数
int max = GetMaxValue(array);
//进行基数排序
for (int exp = 1; max / exp > 0; exp *= 10)
{
CountingSort(array, exp);
}
}
private static void CountingSort(int[] array, int exp)
{
int arrayLength = array.Length;
int[] output = new int[arrayLength];
int[] count = new int[10];
//统计每个桶中的元素个数
for (int i = 0; i < arrayLength; i++)
{
count[(array[i] / exp) % 10]++;
}
//计算每个桶中最后一个元素的位置
for (int i = 1; i < 10; i++)
{
count[i] += count[i - 1];
}
//从原数组中取出元素，放入到输出数组中
for (int i = arrayLength - 1; i >= 0; i--)
{
output[count[(array[i] / exp) % 10] - 1] = array[i];
count[(array[i] / exp) % 10]--;
}
//将输出数组复制回原数组
for (int i = 0; i < arrayLength; i++)
{
array[i] = output[i];
}
}
private static int GetMaxValue(int[] arr)
{
int max = arr[0];
for (int i = 1; i < arr.Length; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
}
return max;
}
public static void RadixSortRun()
{
int[] array = { 19, 27, 46, 48, 99, 888, 50, 2, 4, 44, 47, 36, 38, 15, 26, 5, 3 };
Console.WriteLine("排序前数组：" + string.Join(", ", array));
RadixSort(array);
Console.WriteLine("排序后数组：" + string.Join(", ", array));
}
2. 常见查找算法
1.线性查找
逐个遍历数组或列表，查找目标元素，时间复杂度为O(n)。
详细文章描述
2.二分查找
对于有序数组或列表，通过比较中间元素与目标元素的大小关系来确定目标元素所在的区间，不断缩小查找范围，直到找到目标元素或查找范围为空，时间复杂度为 O(log n)。
详细文章描述
3.哈希查找
通过哈希函数将关键字映射到哈希表的位置，快速定位目标元素，时间复杂度为 O(1)，但需要额外的空间来存储哈希表。
详细文章描述
4.二叉查找树
通过构建二叉搜索树，按照左子树小于根节点、右子树大于根节点的规则，进行查找操作，时间复杂度取决于树的高度，平均情况为 O(log n)，最坏情况为 O(n)。
逐个遍历数组或列表，查找目标元素，时间复杂度为O(n)。
详细文章描述
5.平衡二叉查找树
例如 AVL 树、红黑树等，保持树的平衡性，使得查找效率更高，时间复杂度稳定在 O(log n)。
逐个遍历数组或列表，查找目标元素，时间复杂度为O(n)。
详细文章描述
6.跳表
一种类似于平衡二叉查找树的数据结构，通过构建多层索引，提高查找效率，平均情况下时间复杂度为 O(log n)。
详细文章描述1
详细文章描述2
7.Trie 树
一种树形数据结构，用于处理字符串检索，时间复杂度与字符串的长度相关。
逐个遍历数组或列表，查找目标元素，时间复杂度为O(n)。
详细文章描述
8.Bloom Filter
一种高效的查找算法，用于判断一个元素是否属于一个集合，可能会存在一定的误判率，但具有空间效率和查询效率高的特点。
逐个遍历数组或列表，查找目标元素，时间复杂度为O(n)。
详细文章描述
3.空间切割算法
- 四叉树：将二维空间递归地划分为四个象限，每个象限又可以进一步划分为四个子象限，以此类推。四叉树常用于图像处理、碰撞检测等领域。
- 八叉树：类似于四叉树，但是将三维空间递归地划分为八个子立方体。八叉树常用于三维物体的空间索引和碰撞检测。
- kd 树：一种多维空间划分结构，将空间按照特定维度划分为两个子空间，可以是二维、三维或更高维。kd 树常用于高维空间的搜索和最近邻查找。
- R 树：一种多维空间索引结构，用于高效地存储和查询多维数据。R 树能够快速查找空间范围内的对象，并支持动态插入和删除操作。
- BVH：一种基于包围体的层次空间划分结构，用于加速碰撞检测和光线追踪等应用。BVH 将空间划分为层次结构，每个节点表示一个包围体，可以是球体、盒子等，以减少碰撞检测的计算量。
4.洗牌算法
逆序遍历这个数组，随机从这个数组里面取一个0~i+1之间的数，因为是左闭右开，所以不用担心会越界，取完后，
将其与当前遍历的元素进行位序交换，然后进行下一次遍历
public static void Shuffle<T>(T[] array)
{
Random random = new Random();
for (int i = array.Length - 1; i > 0; i--)
{
// 随机选取一个不大于 i 的数
int j = random.Next(i + 1);
// 交换当前元素与随机选中的元素
T temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
5.一个数组长度为n-1,有1~n，n个数在里面但是缺了一个，如何用最快的方法找到这个数
如果有序的话就用二分查找，如果无序的就可以用
.
求和法
- 时间复杂度：O(n) 空间复杂度：O(1)。但n过大时，求和存在溢出问题。
//n：最大元素的值而不是元素的个数
int getNum(int a[], int n)
{
int sum = n*(n+1)/2;
int t;
for(int i=0; i<n-1; i++)
{
sum = sum - a[i];
}
return sum;
}
异或法
利用异或运算，
任何数异或自己都等于0，x^X=0
任何数异或0都等于他自己x^0=x；
假如缺的为3。result = 1245N
第二次异或后 result = 1245N 12345N = 0^3 = 3
时间复杂度：O(n) 空间复杂度：O(1)
//异或方法，n：最大元素的值
int getLose(int a[], int n)
{
int t = 0;
for(int i =1; i<=n; i++)
t = t ^ i;
//最大值为n，缺失一个元素，则元素个数为n-2
for(int i=0; i<n-1; i++)
t = t ^ a[i];
return t;
}
6.如何计算某个时刻（ex–3:15）的分针和时针的夹角
分针：每分钟移动360度 / 60 = 6度
时针：每小时移动360度 / 12 = 30度，每分钟时针移动30度 / 60 = 0.5度
如3：15，此时分钟移动了156=90，时针303+0.5*15=97.5，那么两者之间的最小夹角就是7.5度，最大夹角是352.5度
float h = 3;
float m = 15;
float angleM = m / 60 * 360;
if (h >= 12)
{
h = h - 12;
}
float angleH = h * 30 + m / 60 * 30; //时针角度计算
float angle = Math.Abs(angleH - angleM);
Console.WriteLine(angle);