diff options
| author | chai <chaifix@163.com> | 2021-06-22 14:58:53 +0800 |
|---|---|---|
| committer | chai <chaifix@163.com> | 2021-06-22 14:58:53 +0800 |
| commit | 8938c3447d88e31f77f20553ed185fc8e64c9ac8 (patch) | |
| tree | 0b13d53b203323891826a600febfe4e90c991a36 /Assets/Algorithms | |
| parent | 5d81d8d8b4062def695c27fa02f67625871e8dce (diff) | |
+misc
Diffstat (limited to 'Assets/Algorithms')
21 files changed, 583 insertions, 283 deletions
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<T>(ref IList<T> data, int i1, int i2)
+ {
+ T temp = data[i1];
+ data[i1] = data[i2];
+ data[i2] = temp;
+ }
+
public static void Swap<T>(ref List<T> 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<T>(List<T> 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/AStarPathfinding.cs b/Assets/Algorithms/PathFinding/AStarPathfinding.cs index 7f42e8e..88d3e94 100644 --- a/Assets/Algorithms/AStarPathfinding.cs +++ b/Assets/Algorithms/PathFinding/AStarPathfinding.cs @@ -1,18 +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()
-// {
-
-// }
-//}
+//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/PathFinding/AStarPathfinding.cs.meta index a5fbb9d..a5fbb9d 100644 --- a/Assets/Algorithms/AStarPathfinding.cs.meta +++ b/Assets/Algorithms/PathFinding/AStarPathfinding.cs.meta 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<T>(List<T> data, ref List<List<T>> perms)
- {
- if (perms == null)
- perms = new List<List<T>>();
- foreach (List<T> perm in perms)
- {
- List<T> p = new List<T>(perm);
- perms.Add(p);
- }
- }
-
- // 生成器形式，每次返回一个组合
- public static IEnumerable Permutations<T>(List<T> data)
- {
- 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)
- {
- if (perm == null)
- perm = new List<T>(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.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<T>(List<T> data, ref List<List<T>> perms) // A B C D
+ { // + A (BCD)
+ List<List<T>> outPerms = new List<List<T>>(); // + B (CD)
+ List<T> temp = new List<T>(data.Count); // + C(D)
+ DivideAndConquer(data, // +D
+ (IList<T> 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<T> dataList, DivisionDescriptor div) => // adhoc 最小子任务处理 // + B (ACD)
+ { // + C (ABD)
+ temp.Add(dataList[div.left]); // + D (ABC)
+ List<T> newCompose = new List<T>(temp);
+ outPerms.Add(newCompose);
+ temp.RemoveAt(temp.Count - 1);
+ },
+ (IList<T> 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<T> 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<T>(List<T> data)
+ {
+ 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)
+ {
+ if (perm == null)
+ perm = new List<T>(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<T>(IList<T> dataList);
+ public delegate void AdHoc<T>(IList<T> dataList, DivisionDescriptor division);
+ public delegate DivisionDescriptor[] Divide<T>(IList<T> dataList, DivisionDescriptor division, out bool bAdhoc);
+ public delegate void Merge<T>(IList<T> dataList, DivisionDescriptor[] divisions);
+ public delegate void Postprocess<T>(IList<T> dataList, DivisionDescriptor div);
+
+ // 分治算法框架
+ public static void DivideAndConquer<T>(IList<T> dataList, Init<T> init, AdHoc<T> adhoc, Divide<T> divide, Merge<T> merge = null, Postprocess<T> postprocess = null)
+ {
+ DivisionDescriptor div = init(dataList);
+ _DivideAndConquer(dataList, div, adhoc, divide, merge, postprocess);
+ }
+
+ private static void _DivideAndConquer<T>(IList<T> dataList, DivisionDescriptor div, AdHoc<T> adhoc, Divide<T> divide, Merge<T> merge, Postprocess<T> 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<T>(IList<T> dataList, int threshold, AdHoc<T> adhoc, Divide<T> divide, Merge<T> merge)
+ {
+
+ }
+
+ #endregion
+
+ }
+}
\ No newline at end of file diff --git a/Assets/Algorithms/Recursion.cs.meta b/Assets/Algorithms/Recursion/Recursion.cs.meta index 07aa1e2..07aa1e2 100644 --- a/Assets/Algorithms/Recursion.cs.meta +++ b/Assets/Algorithms/Recursion/Recursion.cs.meta 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>(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.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>(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; // 没找到 + } + + public static int BinarySearch<T>(List<T> dataList, T value) where T : IComparable, IEquatable<T>
+ {
+ int index = -1;
+ RecursionHelper.DivideAndConquer(dataList,
+ (IList<T> data) =>
+ {
+ DivisionDescriptor div = new DivisionDescriptor();
+ div.left = 0;
+ div.right = data.Count - 1;
+ return div;
+ },
+ (IList<T> data, DivisionDescriptor div) =>
+ {
+ if (data[div.left].CompareTo(value) == 0)
+ {
+ index = div.left;
+ }
+ },
+ (IList<T> 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<T>(IList<T> 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<T>(IList<T> 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<T>(IList<T> data, bool descent = false) where T : IList, IComparable + { + return default(T); + } + + } + +}
\ No newline at end of file diff --git a/Assets/Algorithms/Searching.cs.meta b/Assets/Algorithms/Searching/SearchingHelper.cs.meta index 558b074..558b074 100644 --- a/Assets/Algorithms/Searching.cs.meta +++ b/Assets/Algorithms/Searching/SearchingHelper.cs.meta 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.cs b/Assets/Algorithms/Sorting/Sorting.cs index c4bdc70..292f7eb 100644 --- a/Assets/Algorithms/Sorting.cs +++ b/Assets/Algorithms/Sorting/Sorting.cs @@ -1,159 +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);
- }
- }
- }
- }
-
- }
-
+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/Sorting.cs.meta index 5958b22..5958b22 100644 --- a/Assets/Algorithms/Sorting.cs.meta +++ b/Assets/Algorithms/Sorting/Sorting.cs.meta |