summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Assets/Algorithms/AStarPathfinding.cs18
-rw-r--r--Assets/Algorithms/AStarPathfinding.cs.meta11
-rw-r--r--Assets/Algorithms/Algorithms.cs15
-rw-r--r--Assets/Algorithms/Recursion.cs23
-rw-r--r--Assets/Algorithms/Searching.cs35
-rw-r--r--Assets/Algorithms/Searching.cs.meta11
-rw-r--r--Assets/Algorithms/Sorting.cs159
-rw-r--r--Assets/Algorithms/Sorting.cs.meta11
-rw-r--r--Assets/Algorithms/说明.txt2
-rw-r--r--Assets/Algorithms/说明.txt.meta7
-rw-r--r--Assets/Test/05_Recursion/Test_Recursion.cs96
11 files changed, 369 insertions, 19 deletions
diff --git a/Assets/Algorithms/AStarPathfinding.cs b/Assets/Algorithms/AStarPathfinding.cs
new file mode 100644
index 0000000..7f42e8e
--- /dev/null
+++ b/Assets/Algorithms/AStarPathfinding.cs
@@ -0,0 +1,18 @@
+//using System.Collections;
+//using System.Collections.Generic;
+//using UnityEngine;
+
+//public class AStarPathfinding : MonoBehaviour
+//{
+// // Start is called before the first frame update
+// void Start()
+// {
+
+// }
+
+// // Update is called once per frame
+// void Update()
+// {
+
+// }
+//}
diff --git a/Assets/Algorithms/AStarPathfinding.cs.meta b/Assets/Algorithms/AStarPathfinding.cs.meta
new file mode 100644
index 0000000..a5fbb9d
--- /dev/null
+++ b/Assets/Algorithms/AStarPathfinding.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: 18831f10a8e1abc4383fcc871a29473a
+MonoImporter:
+ externalObjects: {}
+ serializedVersion: 2
+ defaultReferences: []
+ executionOrder: 0
+ icon: {instanceID: 0}
+ userData:
+ assetBundleName:
+ assetBundleVariant:
diff --git a/Assets/Algorithms/Algorithms.cs b/Assets/Algorithms/Algorithms.cs
index 31be4a8..f376ac6 100644
--- a/Assets/Algorithms/Algorithms.cs
+++ b/Assets/Algorithms/Algorithms.cs
@@ -1,4 +1,5 @@
-using System.Collections;
+using System;
+using System.Collections;
using System.Collections.Generic;
using UnityEngine;
@@ -21,6 +22,13 @@ namespace AlgorithmCollection
data[i2] = temp;
}
+ public static void Swap<T>(ref T[] data, int i1, int i2)
+ {
+ T temp = data[i1];
+ data[i1] = data[i2];
+ data[i2] = temp;
+ }
+
// 阶乘
public static int Factorial(int n)
{
@@ -29,6 +37,11 @@ namespace AlgorithmCollection
return n * Factorial(n - 1);
}
+ public static T Min<T>(T v1, T v2) where T : IComparable
+ {
+ return v1.CompareTo(v2) < 0 ? v1 : v2;
+ }
+
}
} \ No newline at end of file
diff --git a/Assets/Algorithms/Recursion.cs b/Assets/Algorithms/Recursion.cs
index 30ebd8a..5a02035 100644
--- a/Assets/Algorithms/Recursion.cs
+++ b/Assets/Algorithms/Recursion.cs
@@ -16,7 +16,7 @@ namespace AlgorithmCollection.Recursion
{
if (perms == null)
perms = new List<List<T>>();
- foreach(List<T> perm in perms)
+ foreach (List<T> perm in perms)
{
List<T> p = new List<T>(perm);
perms.Add(p);
@@ -26,18 +26,18 @@ namespace AlgorithmCollection.Recursion
// 生成器形式，每次返回一个组合
public static IEnumerable Permutations<T>(List<T> data)
{
- foreach(var perm in _Permutations(data, 0, data.Count - 1))
+ foreach (var perm in _Permutations(data, 0, data.Count - 1))
{
yield return perm;
}
}
// 计算start~end范围内的全排列
- private static IEnumerable _Permutations<T>(List<T> data, int start , int end, List<T> perm = null)
+ private static IEnumerable _Permutations<T>(List<T> data, int start, int end, List<T> perm = null)
{
- if(perm == null)
+ if (perm == null)
perm = new List<T>(data.Count);
- if(start == end)
+ if (start == end)
{
perm.Add(data[start]);
yield return perm;
@@ -50,14 +50,23 @@ namespace AlgorithmCollection.Recursion
perm.Add(data[i]);
Algorithms.Swap(ref data, start, i);
IEnumerator itor = _Permutations(data, start + 1, end, perm).GetEnumerator();
- while(itor.MoveNext())
+ while (itor.MoveNext())
yield return itor.Current;
Algorithms.Swap(ref data, start, i);
perm.RemoveAt(perm.Count - 1);
}
}
}
- #endregion
+ #endregion
+
+ #region 分治
+
+ public static void DivideAndConquer()
+ {
+
+ }
+
+ #endregion
}
} \ No newline at end of file
diff --git a/Assets/Algorithms/Searching.cs b/Assets/Algorithms/Searching.cs
new file mode 100644
index 0000000..3489eac
--- /dev/null
+++ b/Assets/Algorithms/Searching.cs
@@ -0,0 +1,35 @@
+using System;
+using System.Collections;
+using System.Collections.Generic;
+using AlgorithmCollection;
+
+namespace AlgorithmCollection.Searching
+{
+
+ public static class SearchingHelper
+ {
+
+ // 二分搜索，返回索引号
+ // O(logn)
+ public static int BinarySearch<T>(T[] dataList, T value) where T : IComparable, IEquatable<T>
+ {
+ int n = dataList.Length;
+ int left = 0;
+ int right = n - 1;
+ while(left <= right)
+ {
+ int middle = (right + left) / 2;
+ T midValue = dataList[middle];
+ if (value.Equals(midValue))
+ return middle;
+ if (value.CompareTo(midValue) > 0)
+ left = middle + 1;
+ if (value.CompareTo(midValue) < 0)
+ right = middle - 1;
+ }
+ return -1; // 没找到
+ }
+
+ }
+
+} \ No newline at end of file
diff --git a/Assets/Algorithms/Searching.cs.meta b/Assets/Algorithms/Searching.cs.meta
new file mode 100644
index 0000000..558b074
--- /dev/null
+++ b/Assets/Algorithms/Searching.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: 1cb8dd50b5546ca4eab54c697cc29344
+MonoImporter:
+ externalObjects: {}
+ serializedVersion: 2
+ defaultReferences: []
+ executionOrder: 0
+ icon: {instanceID: 0}
+ userData:
+ assetBundleName:
+ assetBundleVariant:
diff --git a/Assets/Algorithms/Sorting.cs b/Assets/Algorithms/Sorting.cs
new file mode 100644
index 0000000..c4bdc70
--- /dev/null
+++ b/Assets/Algorithms/Sorting.cs
@@ -0,0 +1,159 @@
+using System;
+using System.Collections;
+using System.Collections.Generic;
+using AlgorithmCollection;
+
+//https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95
+namespace AlgorithmCollection.Sorting
+{
+
+ // 排序主要关注稳定性和效率
+ // *稳定性，相同值的元素相对位置在排序前后是否改变
+ // *效率，时间复杂度和空间复杂度
+ public static class SortingHelper
+ {
+
+ // 选择合适的算法排序
+ public static void Sort<T>(T[] data, bool bDescent = false, bool bStable = false) where T : IComparable, IEquatable<T>
+ {
+ int n = data.Length;
+ }
+
+ #region 归并排序
+ // 归并排序 | 稳定 | 分治法
+ // T(n) = O(nlogn) 渐进最优
+ // S(n) = O(n) 需要大小为n的额外空间
+ public static void MergeSort<T>(T[] data, bool descent = false) where T : IComparable, IEquatable<T>
+ {
+ T[] temp = new T[data.Length];// 需要额外的临时空间
+ _MergeSort(data, 0, data.Length - 1, descent, temp);
+ }
+
+ // 归并排序，非递归
+ public static void MergeSort_NoneRecursion<T>(T[] data, bool descent = false) where T : IComparable, IEquatable<T>
+ {
+ T[] temp = new T[data.Length];// 需要额外的临时空间
+ int s = 1;
+ int n = data.Length;
+ for(int seg = 1; seg < n; seg += seg) //步长1,2,4,8...
+ {
+ for(int start = 0; start < n; start += seg * 2)
+ {
+ int left = start, right = Algorithms.Min(start + seg * 2 - 1, n - 1);
+ int mid = Algorithms.Min(start + seg - 1, n - 1);
+ _Merge(data, left, mid, right, descent, temp);
+ _CopyTo(temp, data, left, right);
+ }
+ }
+ }
+
+ private static void _MergeSort<T>(T[] data, int left, int right, bool descent, T[] temp) where T : IComparable, IEquatable<T>
+ {
+ // 这是一个O(logn)的分治算法，对于每此分治，会有一个O(n)的合并算法，所以归并排序复杂度是O(nlogn)
+ if (left < right)
+ {
+ int middle = (left + right) / 2;
+ _MergeSort(data, left, middle, descent, temp);
+ _MergeSort(data, middle + 1, right, descent, temp);
+ _Merge(data, left, middle, right, descent, temp);// 把left~right部分合并到temp中
+ _CopyTo(temp, data, left, right); // 把合并后的temp部分复制回去
+ }
+ }
+
+ private static T[] _Merge<T>(T[]data, int left, int middle, int right, bool descent, T[] temp) where T : IComparable, IEquatable<T>
+ {
+ // 这是一个O(n)的合并算法
+ int l = left, r = middle + 1;
+ int i = 0;
+ while(l <= middle || r <= right)
+ {
+ if(l > middle)
+ {
+ temp[i++] = data[r++];
+ continue;
+ }
+ if(r > right)
+ {
+ temp[i++] = data[l++];
+ continue;
+ }
+ if (descent && data[l].CompareTo(data[r]) > 0 || !descent && data[l].CompareTo(data[r]) < 0)
+ {
+ temp[i++] = data[l];
+ l++;
+ }
+ else
+ {
+ temp[i++] = data[r];
+ r++;
+ }
+ }
+ return temp;
+ }
+
+ private static void _CopyTo<T>(T[] src, T[] dst, int from, int to)
+ {
+ for (int i = from; i <= to; ++i)
+ dst[i] = src[i - from];
+ }
+
+ #endregion
+
+ #region 快速排序
+ // 快速排序 | 不稳定 | 原地排序 | 分治法
+ // 平均T(n)=O(nlogn)，最坏T(n)=O(n²)
+ // S(n)=O(1)
+ public static void QuickSort<T>(T[] data, bool descent = false) where T : IComparable, IEquatable<T>
+ {
+ _QuickSort(data, descent, 0, data.Length - 1);
+ }
+ private static void _QuickSort<T>(T[] data, bool descent, int start, int end) where T : IComparable, IEquatable<T>
+ {
+ if(start < end)
+ {
+ int p = _Partion(data, descent, start, end);
+ _QuickSort(data, descent, start, p - 1);
+ _QuickSort(data, descent, p + 1, end);
+ }
+ }
+ private static int _Partion<T>(T[] data, bool descent, int start, int end) where T : IComparable
+ {
+ T v = data[start];
+ int i = start;
+ int j = end + 1;
+ while(true)
+ {
+ while ((descent && data[++i].CompareTo(v) >= 0
+ || !descent && data[++i].CompareTo(v) <= 0) && i < end) ;
+ while ((descent && data[--j].CompareTo(v) <= 0
+ || !descent && data[--j].CompareTo(v) >= 0) && j > start) ;
+ if (i >= j)
+ break;
+ Algorithms.Swap(ref data, i, j);
+ }
+ Algorithms.Swap(ref data, start, j);
+ return j;
+ }
+ #endregion
+
+ // 冒泡排序，稳定
+ // O(n²)
+ public static void BubbleSort<T>(T[] data, bool descent = false) where T : IComparable, IEquatable<T>
+ {
+ int n = data.Length;
+ for(int i = 0; i < n; ++i)
+ {
+ for(int j = 0; j < n - i - 1; ++j)
+ {
+ if (descent && data[j].CompareTo(data[j + 1]) < 0
+ || !descent && data[j].CompareTo(data[j + 1]) > 0)
+ {
+ Algorithms.Swap(ref data, j, j + 1);
+ }
+ }
+ }
+ }
+
+ }
+
+} \ No newline at end of file
diff --git a/Assets/Algorithms/Sorting.cs.meta b/Assets/Algorithms/Sorting.cs.meta
new file mode 100644
index 0000000..5958b22
--- /dev/null
+++ b/Assets/Algorithms/Sorting.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: 43b3b96427109e2459a379a1f36de857
+MonoImporter:
+ externalObjects: {}
+ serializedVersion: 2
+ defaultReferences: []
+ executionOrder: 0
+ icon: {instanceID: 0}
+ userData:
+ assetBundleName:
+ assetBundleVariant:
diff --git a/Assets/Algorithms/说明.txt b/Assets/Algorithms/说明.txt
deleted file mode 100644
index 634f729..0000000
--- a/Assets/Algorithms/说明.txt
+++ /dev/null
@@ -1,2 +0,0 @@
-Algrothms.cs里是通用算法合集
-
diff --git a/Assets/Algorithms/说明.txt.meta b/Assets/Algorithms/说明.txt.meta
deleted file mode 100644
index be7853f..0000000
--- a/Assets/Algorithms/说明.txt.meta
+++ /dev/null
@@ -1,7 +0,0 @@
-fileFormatVersion: 2
-guid: 64304d8e88db18b46bade48952f0e7f5
-TextScriptImporter:
- externalObjects: {}
- userData:
- assetBundleName:
- assetBundleVariant:
diff --git a/Assets/Test/05_Recursion/Test_Recursion.cs b/Assets/Test/05_Recursion/Test_Recursion.cs
index ef72a21..ac9de5e 100644
--- a/Assets/Test/05_Recursion/Test_Recursion.cs
+++ b/Assets/Test/05_Recursion/Test_Recursion.cs
@@ -2,19 +2,26 @@
using System.Collections.Generic;
using AlgorithmCollection;
using AlgorithmCollection.Recursion;
+using AlgorithmCollection.Searching;
+using AlgorithmCollection.Sorting;
using UnityEngine;
public class Test_Recursion : MonoBehaviour
{
void Start()
{
- TestPermutations();
+ //TestPermutations();
+ //TestHanoi();
+ //TestBinarySearch();
+ //TestMergeSort();
+ //TestQuickSort();
+ TestBubbleSort();
}
void TestPermutations()
{
// 全排列
- Debug.Log("====全排列====");
+ Debug.Log("全排列");
List<char> data = new List<char> { 'a', 'b', 'c' };
int count = 0;
foreach (List<char> p in RecursionHelper.Permutations(data))
@@ -27,4 +34,89 @@ public class Test_Recursion : MonoBehaviour
Debug.Assert(count == Algorithms.Factorial(data.Count));
}
+ // 汉诺塔，a柱上顺序大小的积木移动到c柱
+ void TestHanoi()
+ {
+ Debug.Log("汉诺塔");
+ Hanoi(3, 'a', 'b', 'c');
+ }
+
+ // 把n个积木从a移动到c
+ void Hanoi(int n, char a, char b, char c)
+ {
+ if (n <= 0)
+ return;
+ Hanoi(n - 1, a, c, b); // 把a柱上面n-1个移动到b柱
+ Debug.Log(a + "->" + c); // 把a柱下面最大的积木移到c柱，这个大积木移动完毕可以不用考虑
+ Hanoi(n - 1, b, a, c); // 把b柱的n-1个移动到c柱
+ }
+
+ void TestBinarySearch()
+ {
+ Debug.Log("二分搜索");
+ int[] value = {1,2,5,6,7,8 }; //升序数组
+ int index = SearchingHelper.BinarySearch(value, 6);
+ Debug.Log(index);
+ }
+
+ void TestMergeSort()
+ {
+ int[] value = { 9, 7, 2, 3, 4, 6, 1 };
+ SortingHelper.MergeSort(value, true);
+ string content = "";
+ for (int i = 0; i < value.Length; ++i)
+ {
+ content += value[i] + " ";
+ }
+ Debug.Log(content);
+
+ SortingHelper.MergeSort_NoneRecursion(value);
+ content = "";
+ for (int i = 0; i < value.Length; ++i)
+ {
+ content += value[i] + " ";
+ }
+ Debug.Log(content);
+ }
+
+ void TestQuickSort()
+ {
+ int[] value = { 9, 7, 2, 3, 4, 6, 1 };
+ SortingHelper.QuickSort(value, true);
+ string content = "";
+ for (int i = 0; i < value.Length; ++i)
+ {
+ content += value[i] + " ";
+ }
+ Debug.Log(content);
+
+ SortingHelper.QuickSort(value);
+ content = "";
+ for (int i = 0; i < value.Length; ++i)
+ {
+ content += value[i] + " ";
+ }
+ Debug.Log(content);
+ }
+
+ void TestBubbleSort()
+ {
+ int[] value = { 9, 7, 2, 3, 4, 6, 1 };
+ SortingHelper.BubbleSort(value, true);
+ string content = "";
+ for (int i = 0; i < value.Length; ++i)
+ {
+ content += value[i] + " ";
+ }
+ Debug.Log(content);
+
+ SortingHelper.BubbleSort(value);
+ content = "";
+ for (int i = 0; i < value.Length; ++i)
+ {
+ content += value[i] + " ";
+ }
+ Debug.Log(content);
+ }
+
}
generated by cgit v1.1-26-g67d0 at 2025-05-18 14:29:37 +0000