From 5d81d8d8b4062def695c27fa02f67625871e8dce Mon Sep 17 00:00:00 2001 From: chai Date: Mon, 21 Jun 2021 22:59:39 +0800 Subject: *misc --- Assets/Algorithms/AStarPathfinding.cs | 18 +++ Assets/Algorithms/AStarPathfinding.cs.meta | 11 ++ Assets/Algorithms/Algorithms.cs | 15 +- Assets/Algorithms/Recursion.cs | 23 ++- Assets/Algorithms/Searching.cs | 35 +++++ Assets/Algorithms/Searching.cs.meta | 11 ++ Assets/Algorithms/Sorting.cs | 159 +++++++++++++++++++++ Assets/Algorithms/Sorting.cs.meta | 11 ++ "Assets/Algorithms/\350\257\264\346\230\216.txt" | 2 - .../Algorithms/\350\257\264\346\230\216.txt.meta" | 7 - Assets/Test/05_Recursion/Test_Recursion.cs | 96 ++++++++++++- 11 files changed, 369 insertions(+), 19 deletions(-) create mode 100644 Assets/Algorithms/AStarPathfinding.cs create mode 100644 Assets/Algorithms/AStarPathfinding.cs.meta create mode 100644 Assets/Algorithms/Searching.cs create mode 100644 Assets/Algorithms/Searching.cs.meta create mode 100644 Assets/Algorithms/Sorting.cs create mode 100644 Assets/Algorithms/Sorting.cs.meta delete mode 100644 "Assets/Algorithms/\350\257\264\346\230\216.txt" delete mode 100644 "Assets/Algorithms/\350\257\264\346\230\216.txt.meta" 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(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 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>(); - foreach(List perm in perms) + foreach (List perm in perms) { List p = new List(perm); perms.Add(p); @@ -26,18 +26,18 @@ namespace AlgorithmCollection.Recursion // 生成器形式，每次返回一个组合 public static IEnumerable Permutations(List 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(List data, int start , int end, List perm = null) + private static IEnumerable _Permutations(List data, int start, int end, List perm = null) { - if(perm == null) + if (perm == null) perm = new List(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[] dataList, T value) where T : IComparable, IEquatable + { + 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[] data, bool bDescent = false, bool bStable = false) where T : IComparable, IEquatable + { + int n = data.Length; + } + + #region 归并排序 + // 归并排序 | 稳定 | 分治法 + // T(n) = O(nlogn) 渐进最优 + // S(n) = O(n) 需要大小为n的额外空间 + public static void MergeSort(T[] data, bool descent = false) where T : IComparable, IEquatable + { + T[] temp = new T[data.Length];// 需要额外的临时空间 + _MergeSort(data, 0, data.Length - 1, descent, temp); + } + + // 归并排序，非递归 + public static void MergeSort_NoneRecursion(T[] data, bool descent = false) where T : IComparable, IEquatable + { + 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[] data, int left, int right, bool descent, T[] temp) where T : IComparable, IEquatable + { + // 这是一个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[]data, int left, int middle, int right, bool descent, T[] temp) where T : IComparable, IEquatable + { + // 这是一个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[] 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[] data, bool descent = false) where T : IComparable, IEquatable + { + _QuickSort(data, descent, 0, data.Length - 1); + } + private static void _QuickSort(T[] data, bool descent, int start, int end) where T : IComparable, IEquatable + { + 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[] 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[] data, bool descent = false) where T : IComparable, IEquatable + { + 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/\350\257\264\346\230\216.txt" "b/Assets/Algorithms/\350\257\264\346\230\216.txt" deleted file mode 100644 index 634f729..0000000 --- "a/Assets/Algorithms/\350\257\264\346\230\216.txt" +++ /dev/null @@ -1,2 +0,0 @@ -Algrothms.cs里是通用算法合集 - diff --git "a/Assets/Algorithms/\350\257\264\346\230\216.txt.meta" "b/Assets/Algorithms/\350\257\264\346\230\216.txt.meta" deleted file mode 100644 index be7853f..0000000 --- "a/Assets/Algorithms/\350\257\264\346\230\216.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 data = new List { 'a', 'b', 'c' }; int count = 0; foreach (List 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); + } + } -- cgit v1.1-26-g67d0