From 8938c3447d88e31f77f20553ed185fc8e64c9ac8 Mon Sep 17 00:00:00 2001 From: chai Date: Tue, 22 Jun 2021 14:58:53 +0800 Subject: +misc --- Assets/Algorithms/AStarPathfinding.cs | 18 --- Assets/Algorithms/AStarPathfinding.cs.meta | 11 -- Assets/Algorithms/Algebra.meta | 8 + Assets/Algorithms/Algebra/Linear.cs | 18 +++ Assets/Algorithms/Algebra/Linear.cs.meta | 11 ++ Assets/Algorithms/Algorithms.cs | 14 ++ Assets/Algorithms/Geometry.meta | 8 + Assets/Algorithms/Geometry/GeometryHelper.cs | 18 +++ Assets/Algorithms/Geometry/GeometryHelper.cs.meta | 11 ++ Assets/Algorithms/PathFinding.meta | 8 + Assets/Algorithms/PathFinding/AStarPathfinding.cs | 18 +++ .../PathFinding/AStarPathfinding.cs.meta | 11 ++ Assets/Algorithms/Recursion.cs | 72 --------- Assets/Algorithms/Recursion.cs.meta | 11 -- Assets/Algorithms/Recursion.meta | 8 + Assets/Algorithms/Recursion/Recursion.cs | 163 +++++++++++++++++++++ Assets/Algorithms/Recursion/Recursion.cs.meta | 11 ++ Assets/Algorithms/Searching.cs | 35 ----- Assets/Algorithms/Searching.cs.meta | 11 -- Assets/Algorithms/Searching.meta | 8 + Assets/Algorithms/Searching/SearchingHelper.cs | 124 ++++++++++++++++ .../Algorithms/Searching/SearchingHelper.cs.meta | 11 ++ Assets/Algorithms/Sorting.cs | 159 -------------------- Assets/Algorithms/Sorting.cs.meta | 11 -- Assets/Algorithms/Sorting.meta | 8 + Assets/Algorithms/Sorting/Sorting.cs | 159 ++++++++++++++++++++ Assets/Algorithms/Sorting/Sorting.cs.meta | 11 ++ 27 files changed, 628 insertions(+), 328 deletions(-) delete mode 100644 Assets/Algorithms/AStarPathfinding.cs delete mode 100644 Assets/Algorithms/AStarPathfinding.cs.meta create mode 100644 Assets/Algorithms/Algebra.meta create mode 100644 Assets/Algorithms/Algebra/Linear.cs create mode 100644 Assets/Algorithms/Algebra/Linear.cs.meta create mode 100644 Assets/Algorithms/Geometry.meta create mode 100644 Assets/Algorithms/Geometry/GeometryHelper.cs create mode 100644 Assets/Algorithms/Geometry/GeometryHelper.cs.meta create mode 100644 Assets/Algorithms/PathFinding.meta create mode 100644 Assets/Algorithms/PathFinding/AStarPathfinding.cs create mode 100644 Assets/Algorithms/PathFinding/AStarPathfinding.cs.meta delete mode 100644 Assets/Algorithms/Recursion.cs delete mode 100644 Assets/Algorithms/Recursion.cs.meta create mode 100644 Assets/Algorithms/Recursion.meta create mode 100644 Assets/Algorithms/Recursion/Recursion.cs create mode 100644 Assets/Algorithms/Recursion/Recursion.cs.meta delete mode 100644 Assets/Algorithms/Searching.cs delete mode 100644 Assets/Algorithms/Searching.cs.meta create mode 100644 Assets/Algorithms/Searching.meta create mode 100644 Assets/Algorithms/Searching/SearchingHelper.cs create mode 100644 Assets/Algorithms/Searching/SearchingHelper.cs.meta delete mode 100644 Assets/Algorithms/Sorting.cs delete mode 100644 Assets/Algorithms/Sorting.cs.meta create mode 100644 Assets/Algorithms/Sorting.meta create mode 100644 Assets/Algorithms/Sorting/Sorting.cs create mode 100644 Assets/Algorithms/Sorting/Sorting.cs.meta (limited to 'Assets/Algorithms') diff --git a/Assets/Algorithms/AStarPathfinding.cs b/Assets/Algorithms/AStarPathfinding.cs deleted file mode 100644 index 7f42e8e..0000000 --- a/Assets/Algorithms/AStarPathfinding.cs +++ /dev/null @@ -1,18 +0,0 @@ -//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 deleted file mode 100644 index a5fbb9d..0000000 --- a/Assets/Algorithms/AStarPathfinding.cs.meta +++ /dev/null @@ -1,11 +0,0 @@ -fileFormatVersion: 2 -guid: 18831f10a8e1abc4383fcc871a29473a -MonoImporter: - externalObjects: {} - serializedVersion: 2 - defaultReferences: [] - executionOrder: 0 - icon: {instanceID: 0} - userData: - assetBundleName: - assetBundleVariant: diff --git a/Assets/Algorithms/Algebra.meta b/Assets/Algorithms/Algebra.meta new file mode 100644 index 0000000..9164c45 --- /dev/null +++ b/Assets/Algorithms/Algebra.meta @@ -0,0 +1,8 @@ +fileFormatVersion: 2 +guid: 84b14759ecc9662489845330ec90aea2 +folderAsset: yes +DefaultImporter: + externalObjects: {} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Assets/Algorithms/Algebra/Linear.cs b/Assets/Algorithms/Algebra/Linear.cs new file mode 100644 index 0000000..5448b50 --- /dev/null +++ b/Assets/Algorithms/Algebra/Linear.cs @@ -0,0 +1,18 @@ +using System.Collections; +using System.Collections.Generic; +using UnityEngine; + +public class Linear : MonoBehaviour +{ + // Start is called before the first frame update + void Start() + { + + } + + // Update is called once per frame + void Update() + { + + } +} diff --git a/Assets/Algorithms/Algebra/Linear.cs.meta b/Assets/Algorithms/Algebra/Linear.cs.meta new file mode 100644 index 0000000..9622349 --- /dev/null +++ b/Assets/Algorithms/Algebra/Linear.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: e74733d1140a0704aae5257c720157e4 +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 f376ac6..a6005d3 100644 --- a/Assets/Algorithms/Algorithms.cs +++ b/Assets/Algorithms/Algorithms.cs @@ -15,6 +15,13 @@ namespace AlgorithmCollection v2 = temp; } + public static void Swap(ref IList data, int i1, int i2) + { + T temp = data[i1]; + data[i1] = data[i2]; + data[i2] = temp; + } + public static void Swap(ref List data, int i1, int i2) { T temp = data[i1]; @@ -42,6 +49,13 @@ namespace AlgorithmCollection return v1.CompareTo(v2) < 0 ? v1 : v2; } + public static string ListToString(List data) + { + string content = ""; + data.ForEach((T v) => { content += v.ToString(); }); + return content; + } + } } \ No newline at end of file diff --git a/Assets/Algorithms/Geometry.meta b/Assets/Algorithms/Geometry.meta new file mode 100644 index 0000000..ebbda7e --- /dev/null +++ b/Assets/Algorithms/Geometry.meta @@ -0,0 +1,8 @@ +fileFormatVersion: 2 +guid: e31f96310c59ec04bbf20ca55efbad6f +folderAsset: yes +DefaultImporter: + externalObjects: {} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Assets/Algorithms/Geometry/GeometryHelper.cs b/Assets/Algorithms/Geometry/GeometryHelper.cs new file mode 100644 index 0000000..6da1503 --- /dev/null +++ b/Assets/Algorithms/Geometry/GeometryHelper.cs @@ -0,0 +1,18 @@ +using System.Collections; +using System.Collections.Generic; +using UnityEngine; + +public class GeometryHelper : MonoBehaviour +{ + // Start is called before the first frame update + void Start() + { + + } + + // Update is called once per frame + void Update() + { + + } +} diff --git a/Assets/Algorithms/Geometry/GeometryHelper.cs.meta b/Assets/Algorithms/Geometry/GeometryHelper.cs.meta new file mode 100644 index 0000000..a83acc0 --- /dev/null +++ b/Assets/Algorithms/Geometry/GeometryHelper.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: d034c57c629eee44da089191f2079286 +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Assets/Algorithms/PathFinding.meta b/Assets/Algorithms/PathFinding.meta new file mode 100644 index 0000000..fa103db --- /dev/null +++ b/Assets/Algorithms/PathFinding.meta @@ -0,0 +1,8 @@ +fileFormatVersion: 2 +guid: 16fc842f33eb28e4f82cc11af88ea40e +folderAsset: yes +DefaultImporter: + externalObjects: {} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Assets/Algorithms/PathFinding/AStarPathfinding.cs b/Assets/Algorithms/PathFinding/AStarPathfinding.cs new file mode 100644 index 0000000..88d3e94 --- /dev/null +++ b/Assets/Algorithms/PathFinding/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/PathFinding/AStarPathfinding.cs.meta b/Assets/Algorithms/PathFinding/AStarPathfinding.cs.meta new file mode 100644 index 0000000..a5fbb9d --- /dev/null +++ b/Assets/Algorithms/PathFinding/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/Recursion.cs b/Assets/Algorithms/Recursion.cs deleted file mode 100644 index 5a02035..0000000 --- a/Assets/Algorithms/Recursion.cs +++ /dev/null @@ -1,72 +0,0 @@ -using System; -using System.Collections; -using System.Collections.Generic; -using AlgorithmCollection; - -// 递归与分治算法 - -namespace AlgorithmCollection.Recursion -{ - - public static class RecursionHelper - { - - #region 全排列，返回数据的所有组合 - public static void Permutations(List data, ref List> perms) - { - if (perms == null) - perms = new List>(); - foreach (List perm in perms) - { - List p = new List(perm); - perms.Add(p); - } - } - - // 生成器形式，每次返回一个组合 - public static IEnumerable Permutations(List data) - { - 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) - { - if (perm == null) - perm = new List(data.Count); - if (start == end) - { - perm.Add(data[start]); - yield return perm; - perm.RemoveAt(perm.Count - 1); - } - else - { - for (int i = start; i <= end; ++i) - { - perm.Add(data[i]); - Algorithms.Swap(ref data, start, i); - IEnumerator itor = _Permutations(data, start + 1, end, perm).GetEnumerator(); - while (itor.MoveNext()) - yield return itor.Current; - Algorithms.Swap(ref data, start, i); - perm.RemoveAt(perm.Count - 1); - } - } - } - #endregion - - #region 分治 - - public static void DivideAndConquer() - { - - } - - #endregion - - } -} \ No newline at end of file diff --git a/Assets/Algorithms/Recursion.cs.meta b/Assets/Algorithms/Recursion.cs.meta deleted file mode 100644 index 07aa1e2..0000000 --- a/Assets/Algorithms/Recursion.cs.meta +++ /dev/null @@ -1,11 +0,0 @@ -fileFormatVersion: 2 -guid: d879b71db7b8d344fafd47ce8522aae3 -MonoImporter: - externalObjects: {} - serializedVersion: 2 - defaultReferences: [] - executionOrder: 0 - icon: {instanceID: 0} - userData: - assetBundleName: - assetBundleVariant: diff --git a/Assets/Algorithms/Recursion.meta b/Assets/Algorithms/Recursion.meta new file mode 100644 index 0000000..c60fa9f --- /dev/null +++ b/Assets/Algorithms/Recursion.meta @@ -0,0 +1,8 @@ +fileFormatVersion: 2 +guid: 08485f854d1dd5c43ba0af91f94fd241 +folderAsset: yes +DefaultImporter: + externalObjects: {} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Assets/Algorithms/Recursion/Recursion.cs b/Assets/Algorithms/Recursion/Recursion.cs new file mode 100644 index 0000000..4f2c4d3 --- /dev/null +++ b/Assets/Algorithms/Recursion/Recursion.cs @@ -0,0 +1,163 @@ +using System; +using System.Collections; +using System.Collections.Generic; +using AlgorithmCollection; +using UnityEngine; + +// 递归与分治算法 + +namespace AlgorithmCollection.Recursion +{ + + public struct DivisionDescriptor + { + public int left; + public int right; + public object userdata; + } + + public static class RecursionHelper + { + #region 全排列，返回数据的所有组合 + + public static void Permutations(List data, ref List> perms) // A B C D + { // + A (BCD) + List> outPerms = new List>(); // + B (CD) + List temp = new List(data.Count); // + C(D) + DivideAndConquer(data, // +D + (IList dataList) => // init // + D(C) + { // +C + DivisionDescriptor div = new DivisionDescriptor(); // + C (BD) + div.userdata = -1; // + B(D) + div.left = 0; // + D(B) + div.right = dataList.Count - 1; // + D (BC) + return div; // + B(C) + }, // + C(B) + (IList dataList, DivisionDescriptor div) => // adhoc 最小子任务处理 // + B (ACD) + { // + C (ABD) + temp.Add(dataList[div.left]); // + D (ABC) + List newCompose = new List(temp); + outPerms.Add(newCompose); + temp.RemoveAt(temp.Count - 1); + }, + (IList dataList, DivisionDescriptor div, out bool bAdhoc) => // 划分 + { + int left = div.left; // 包含第一个元素在内的范围 + int right = div.right; + int pivot = (int)div.userdata; // 第一个元素在范围内的索引 + DivisionDescriptor[] divisions; + int l = left; + if (pivot != -1) + { + temp.Add(dataList[pivot]); + Algorithms.Swap(ref dataList, pivot, left); + l = left + 1; + } + divisions = new DivisionDescriptor[right - l + 1]; + int j = 0; + for (int i = l; i <= right ; ++i) + { + divisions[j].left = l; + divisions[j].right = right; + divisions[j].userdata = (int)i; + j++; + } + bAdhoc = l == right; + return divisions; + }, + null, // 合并 + (IList dataList, DivisionDescriptor div) => //子任务后处理 + { + int pivot = (int)div.userdata; // 第一个元素的索引 + int left = div.left; + int right = div.right; + Algorithms.Swap(ref dataList, pivot, left); + temp.RemoveAt(temp.Count - 1); + } + ); + perms = outPerms; + } + + // 生成器形式，每次返回一个组合 + public static IEnumerable Permutations(List data) + { + 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) + { + if (perm == null) + perm = new List(data.Count); + if (start == end) + { + perm.Add(data[start]); + yield return perm; + perm.RemoveAt(perm.Count - 1); + } + else + { + for (int i = start; i <= end; ++i) + { + perm.Add(data[i]); + Algorithms.Swap(ref data, start, i); + IEnumerator itor = _Permutations(data, start + 1, end, perm).GetEnumerator(); + while (itor.MoveNext()) + yield return itor.Current; + Algorithms.Swap(ref data, start, i); + perm.RemoveAt(perm.Count - 1); + } + } + } + #endregion + + #region 分治算法 + + public delegate DivisionDescriptor Init(IList dataList); + public delegate void AdHoc(IList dataList, DivisionDescriptor division); + public delegate DivisionDescriptor[] Divide(IList dataList, DivisionDescriptor division, out bool bAdhoc); + public delegate void Merge(IList dataList, DivisionDescriptor[] divisions); + public delegate void Postprocess(IList dataList, DivisionDescriptor div); + + // 分治算法框架 + public static void DivideAndConquer(IList dataList, Init init, AdHoc adhoc, Divide divide, Merge merge = null, Postprocess postprocess = null) + { + DivisionDescriptor div = init(dataList); + _DivideAndConquer(dataList, div, adhoc, divide, merge, postprocess); + } + + private static void _DivideAndConquer(IList dataList, DivisionDescriptor div, AdHoc adhoc, Divide divide, Merge merge, Postprocess postprocess) + { + bool bAdhoc; + DivisionDescriptor[] division = divide(dataList, div, out bAdhoc); + if (!bAdhoc) + { + for(int i = 0; i < division.Length; ++i) + { + _DivideAndConquer(dataList, division[i], adhoc, divide, merge, postprocess); + postprocess?.Invoke(dataList, division[i]); + } + merge?.Invoke(dataList, division); + } + else + { + for(int i = 0; i < division.Length; ++i) + { + adhoc(dataList, division[i]); + } + } + } + + // 分治算法框架，非递归 + public static void DivideAndConquer_NoneRecursion(IList dataList, int threshold, AdHoc adhoc, Divide divide, Merge merge) + { + + } + + #endregion + + } +} \ No newline at end of file diff --git a/Assets/Algorithms/Recursion/Recursion.cs.meta b/Assets/Algorithms/Recursion/Recursion.cs.meta new file mode 100644 index 0000000..07aa1e2 --- /dev/null +++ b/Assets/Algorithms/Recursion/Recursion.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: d879b71db7b8d344fafd47ce8522aae3 +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Assets/Algorithms/Searching.cs b/Assets/Algorithms/Searching.cs deleted file mode 100644 index 3489eac..0000000 --- a/Assets/Algorithms/Searching.cs +++ /dev/null @@ -1,35 +0,0 @@ -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 deleted file mode 100644 index 558b074..0000000 --- a/Assets/Algorithms/Searching.cs.meta +++ /dev/null @@ -1,11 +0,0 @@ -fileFormatVersion: 2 -guid: 1cb8dd50b5546ca4eab54c697cc29344 -MonoImporter: - externalObjects: {} - serializedVersion: 2 - defaultReferences: [] - executionOrder: 0 - icon: {instanceID: 0} - userData: - assetBundleName: - assetBundleVariant: diff --git a/Assets/Algorithms/Searching.meta b/Assets/Algorithms/Searching.meta new file mode 100644 index 0000000..ff8ea28 --- /dev/null +++ b/Assets/Algorithms/Searching.meta @@ -0,0 +1,8 @@ +fileFormatVersion: 2 +guid: 79b3050310dde11479c16d8b56c5dc77 +folderAsset: yes +DefaultImporter: + externalObjects: {} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Assets/Algorithms/Searching/SearchingHelper.cs b/Assets/Algorithms/Searching/SearchingHelper.cs new file mode 100644 index 0000000..1605b43 --- /dev/null +++ b/Assets/Algorithms/Searching/SearchingHelper.cs @@ -0,0 +1,124 @@ +using System; +using System.Collections; +using System.Collections.Generic; +using AlgorithmCollection; +using AlgorithmCollection.Recursion; + +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; // 没找到 + } + + public static int BinarySearch(List dataList, T value) where T : IComparable, IEquatable + { + int index = -1; + RecursionHelper.DivideAndConquer(dataList, + (IList data) => + { + DivisionDescriptor div = new DivisionDescriptor(); + div.left = 0; + div.right = data.Count - 1; + return div; + }, + (IList data, DivisionDescriptor div) => + { + if (data[div.left].CompareTo(value) == 0) + { + index = div.left; + } + }, + (IList data, DivisionDescriptor div, out bool bAdhoc) => + { + int left = div.left; + int right = div.right; + DivisionDescriptor[] division = new DivisionDescriptor[1]; + if(right <= left) + { + division[0].left = left; + division[0].right = right; + bAdhoc = true; + return division; + } + int mid = (left + right) / 2; + T midValue = data[mid]; + if(midValue.CompareTo(value) > 0) + { + division[0].left = left; + division[0].right = mid - 1; + } + else if (midValue.CompareTo(value) < 0) + { + division[0].left = mid + 1; + division[0].right = right; + } + else + { + division[0].left = mid; + division[0].right = mid; + bAdhoc = true; + return division; + } + bAdhoc = false; + return division; + } + ); + return index; + } + + // 查找最大值 + // O(n) + public static int FindMax(IList dataList) where T : IList, IComparable + { + int max = 0; + for(int i = 0; i < dataList.Count; ++i) + { + if (dataList[i].CompareTo(dataList[max]) > 0) + max = i; + } + return max; + } + + // 查找最小值 + // O(n) + public static int FindMin(IList dataList) where T : IList, IComparable + { + int min = 0; + for (int i = 0; i < dataList.Count; ++i) + { + if (dataList[i].CompareTo(dataList[min]) < 0) + min = i; + } + return min; + } + + + public static T Select_Random(IList data, bool descent = false) where T : IList, IComparable + { + return default(T); + } + + } + +} \ No newline at end of file diff --git a/Assets/Algorithms/Searching/SearchingHelper.cs.meta b/Assets/Algorithms/Searching/SearchingHelper.cs.meta new file mode 100644 index 0000000..558b074 --- /dev/null +++ b/Assets/Algorithms/Searching/SearchingHelper.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 deleted file mode 100644 index c4bdc70..0000000 --- a/Assets/Algorithms/Sorting.cs +++ /dev/null @@ -1,159 +0,0 @@ -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 deleted file mode 100644 index 5958b22..0000000 --- a/Assets/Algorithms/Sorting.cs.meta +++ /dev/null @@ -1,11 +0,0 @@ -fileFormatVersion: 2 -guid: 43b3b96427109e2459a379a1f36de857 -MonoImporter: - externalObjects: {} - serializedVersion: 2 - defaultReferences: [] - executionOrder: 0 - icon: {instanceID: 0} - userData: - assetBundleName: - assetBundleVariant: diff --git a/Assets/Algorithms/Sorting.meta b/Assets/Algorithms/Sorting.meta new file mode 100644 index 0000000..c12cffe --- /dev/null +++ b/Assets/Algorithms/Sorting.meta @@ -0,0 +1,8 @@ +fileFormatVersion: 2 +guid: c33b05e483668f14a8c29cffeec8904b +folderAsset: yes +DefaultImporter: + externalObjects: {} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Assets/Algorithms/Sorting/Sorting.cs b/Assets/Algorithms/Sorting/Sorting.cs new file mode 100644 index 0000000..292f7eb --- /dev/null +++ b/Assets/Algorithms/Sorting/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/Sorting.cs.meta b/Assets/Algorithms/Sorting/Sorting.cs.meta new file mode 100644 index 0000000..5958b22 --- /dev/null +++ b/Assets/Algorithms/Sorting/Sorting.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: 43b3b96427109e2459a379a1f36de857 +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: -- cgit v1.1-26-g67d0