summaryrefslogtreecommitdiff
path: root/Assets
diff options
context:
space:
mode:
Diffstat (limited to 'Assets')
-rw-r--r--Assets/Algorithms/Recursion/Recursion.cs129
-rw-r--r--Assets/Algorithms/Searching/SearchingHelper.cs113
-rw-r--r--Assets/Test/05_Recursion/Test_Recursion.cs18
3 files changed, 176 insertions, 84 deletions
diff --git a/Assets/Algorithms/Recursion/Recursion.cs b/Assets/Algorithms/Recursion/Recursion.cs
index c704f8f..7bfb171 100644
--- a/Assets/Algorithms/Recursion/Recursion.cs
+++ b/Assets/Algorithms/Recursion/Recursion.cs
@@ -13,58 +13,55 @@ namespace AlgorithmCollection.Recursion
#region 全排列，返回数据的所有组合
public static void Permutations<T>(List<T> dataList, ref List<List<T>> perms)
{
- List<List<T>> outPerms = new List<List<T>>(); // A B C D
- List<T> temp = new List<T>(dataList.Count); // + A (BCD)
- DivideAndConquer( // + B (CD)
- () => // init // + C(D)
- { // +D
- DivisionDescriptor div = new DivisionDescriptor(); // + D(C)
- div.userdata = -1; // +C
- div.left = 0; // + C (BD)
- div.right = dataList.Count - 1; // + B(D)
- return div; // + D(B)
- }, // + D (BC)
- (DivisionDescriptor div) => // adhoc 最小子任务处理 // + B(C)
- { // + C(B)
- temp.Add(dataList[div.left]); // + B (ACD)
- List<T> newCompose = new List<T>(temp); // + C (ABD)
- outPerms.Add(newCompose); // + D (ABC)
- temp.RemoveAt(temp.Count - 1);
- },
- (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;
+ List<List<T>> outPerms = new List<List<T>>(); // A B C D
+ List<T> temp = new List<T>(dataList.Count); // + A (BCD)
+ DNC( // + B (CD)
+ () => // init // + C(D)
+ { // +D
+ DivisionDescriptor div = new DivisionDescriptor(); // + D(C)
+ div.userdata = -1; // +C
+ div.left = 0; // + C (BD)
+ div.right = dataList.Count - 1; // + B(D)
+ return div; // + D(B)
+ }, // + D (BC)
+ (DivisionDescriptor div, out DivisionDescriptor[] divs) => // 划分 // + B(C)
+ { // + C(B)
+ int left = div.left; // 包含第一个元素在内的范围 // + B (ACD)
+ int right = div.right; // + C (ABD)
+ int pivot = (int)div.userdata; // 第一个元素在范围内的索引 // + D (ABC)
+ int l = left;
+ if (pivot != -1)
+ {
+ temp.Add(dataList[pivot]);
+ Algorithms.Swap(ref dataList, pivot, left);
+ l = left + 1;
+ }
+ divs = new DivisionDescriptor[right - l + 1];
+ int j = 0;
+ for (int i = l; i <= right; ++i)
+ {
+ divs[j].left = l;
+ divs[j].right = right;
+ divs[j].userdata = (int)i;
+ j++;
+ }
+ return l == right;
},
- null, // 合并
- (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);
- }
+ (DivisionDescriptor div) => // solve 最小子任务处理
+ {
+ temp.Add(dataList[div.left]);
+ List<T> newCompose = new List<T>(temp);
+ outPerms.Add(newCompose);
+ temp.RemoveAt(temp.Count - 1);
+ },
+ (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;
}
@@ -105,30 +102,30 @@ namespace AlgorithmCollection.Recursion
}
#endregion
- #region 分治算法
+ #region 分治
public delegate DivisionDescriptor Init();
- public delegate void AdHoc(DivisionDescriptor division);
- public delegate DivisionDescriptor[] Divide(DivisionDescriptor division, out bool bAdhoc);
+ public delegate void Solve(DivisionDescriptor division);
+ public delegate bool Divide(DivisionDescriptor division, out DivisionDescriptor[] divs);//返回值代表是否达到最小问题阈值
public delegate void Merge(DivisionDescriptor[] divisions);
public delegate void Postprocess(DivisionDescriptor div);
// 分治算法框架
- public static void DivideAndConquer(Init init, AdHoc adhoc, Divide divide, Merge merge = null, Postprocess postprocess = null)
+ public static void DNC(Init init, Divide divide, Solve solve, Postprocess postprocess = null, Merge merge = null)
{
DivisionDescriptor div = init();
- _DivideAndConquer(div, adhoc, divide, merge, postprocess);
+ _DivideAndConquer(div, solve, divide, merge, postprocess);
}
- private static void _DivideAndConquer(DivisionDescriptor div, AdHoc adhoc, Divide divide, Merge merge, Postprocess postprocess)
+ private static void _DivideAndConquer(DivisionDescriptor div, Solve solve, Divide divide, Merge merge, Postprocess postprocess)
{
- bool bAdhoc;
- DivisionDescriptor[] division = divide(div, out bAdhoc);
- if (!bAdhoc)
+ DivisionDescriptor[] division;
+ bool bUnit = divide(div, out division);
+ if (!bUnit)
{
for(int i = 0; i < division.Length; ++i)
{
- _DivideAndConquer(division[i], adhoc, divide, merge, postprocess);
+ _DivideAndConquer(division[i], solve, divide, merge, postprocess);
postprocess?.Invoke(division[i]);
}
merge?.Invoke(division);
@@ -137,12 +134,20 @@ namespace AlgorithmCollection.Recursion
{
for(int i = 0; i < division.Length; ++i)
{
- adhoc(division[i]);
+ solve(division[i]);
}
}
}
+ #endregion
+
+ #region 动态规划
+ private static void DP()
+ {
+
+ }
#endregion
+
}
} \ No newline at end of file
diff --git a/Assets/Algorithms/Searching/SearchingHelper.cs b/Assets/Algorithms/Searching/SearchingHelper.cs
index a36e653..191ff5e 100644
--- a/Assets/Algorithms/Searching/SearchingHelper.cs
+++ b/Assets/Algorithms/Searching/SearchingHelper.cs
@@ -34,7 +34,7 @@ namespace AlgorithmCollection.Searching
public static int BinarySearch<T>(List<T> data, T value) where T : IComparable, IEquatable<T>
{
int index = -1;
- RecursionHelper.DivideAndConquer(
+ RecursionHelper.DNC(
() =>
{
DivisionDescriptor div = new DivisionDescriptor();
@@ -42,24 +42,16 @@ namespace AlgorithmCollection.Searching
div.right = data.Count - 1;
return div;
},
- (DivisionDescriptor div) =>
- {
- if (data[div.left].CompareTo(value) == 0)
- {
- index = div.left;
- }
- },
- (DivisionDescriptor div, out bool bAdhoc) =>
+ (DivisionDescriptor div, out DivisionDescriptor[] division) =>
{
int left = div.left;
int right = div.right;
- DivisionDescriptor[] division = new DivisionDescriptor[1];
+ division = new DivisionDescriptor[1];
if(right <= left)
{
division[0].left = left;
division[0].right = right;
- bAdhoc = true;
- return division;
+ return true;
}
int mid = (left + right) / 2;
T midValue = data[mid];
@@ -77,13 +69,18 @@ namespace AlgorithmCollection.Searching
{
division[0].left = mid;
division[0].right = mid;
- bAdhoc = true;
- return division;
+ return true;
}
- bAdhoc = false;
- return division;
- }
- );
+ return false;
+ },
+ (DivisionDescriptor div) =>
+ {
+ if (data[div.left].CompareTo(value) == 0)
+ {
+ index = div.left;
+ }
+ }
+ );
return index;
}
@@ -113,10 +110,84 @@ namespace AlgorithmCollection.Searching
return min;
}
-
- public static T Select_Random<T>(IList<T> data, bool descent = false) where T : IList, IComparable
+ // 找到第n大或者第n小，类比快速排序
+ // O(n)
+ public static bool Select<T>(IList<T> data, int n, bool bMin, ref T findValue) where T : IComparable
{
- return default(T);
+ bool suc = false;
+ T v = default(T);
+ RecursionHelper.DNC(
+ ()=>
+ {
+ DivisionDescriptor div = new DivisionDescriptor();
+ div.left = 0;
+ div.right = data.Count - 1;
+ div.userdata = n;
+ return div;
+ },
+ (DivisionDescriptor division, out DivisionDescriptor[] div) =>
+ {
+ div = new DivisionDescriptor[1];
+ int left = division.left;
+ int right = division.right;
+ int remain = (int)division.userdata;
+ if(right <= left)
+ {
+ div[0].left = left;
+ div[0].right = right;
+ div[0].userdata = remain;
+ return true;
+ }
+ int l = left;
+ int r = right + 1;
+ T val = data[l];
+ while (true)
+ {
+ while ((bMin && data[++l].CompareTo(val) <= 0 || !bMin && data[++l].CompareTo(val) >= 0) && l < right);
+ while ((bMin && data[--r].CompareTo(val) >= 0 || !bMin && data[--r].CompareTo(val) <= 0) && r > left);
+ if (l >= r)
+ break;
+ Algorithms.Swap(ref data, l, r);
+ }
+ Algorithms.Swap(ref data, left, r);
+ int count = r - left + 1;
+ if(count > remain)
+ {
+ div[0].left = left;
+ div[0].right = r - 1;
+ div[0].userdata = remain;
+ }
+ else if(count < remain)
+ {
+ div[0].left = r + 1;
+ div[0].right = right;
+ div[0].userdata = remain - count;
+ }
+ else
+ {
+ div[0].left = r;
+ div[0].right = r;
+ div[0].userdata = 0;
+ return true;
+ }
+ return false;
+ },
+ (DivisionDescriptor division)=>
+ {
+ if((int)division.userdata == 0)
+ {
+ int i = division.left;
+ v = data[i];
+ suc = true;
+ }
+ }
+ );
+ if (suc)
+ {
+ findValue = v;
+ return true;
+ }
+ return false;
}
}
diff --git a/Assets/Test/05_Recursion/Test_Recursion.cs b/Assets/Test/05_Recursion/Test_Recursion.cs
index aef587c..9399bc3 100644
--- a/Assets/Test/05_Recursion/Test_Recursion.cs
+++ b/Assets/Test/05_Recursion/Test_Recursion.cs
@@ -10,12 +10,13 @@ public class Test_Recursion : MonoBehaviour
{
void Start()
{
- TestPermutations();
+ //TestPermutations();
//TestHanoi();
//TestBinarySearch();
//TestMergeSort();
//TestQuickSort();
//TestBubbleSort();
+ TestSelect();
}
void TestPermutations()
@@ -138,4 +139,19 @@ public class Test_Recursion : MonoBehaviour
Debug.Log(content);
}
+ void TestSelect()
+ {
+ Debug.Log("查找");
+ List<int> value2 = new List<int>() { 1, 2, 3, 6, 7, 8 }; //升序数组
+ int v = -1;
+ if(SearchingHelper.Select(value2, 10, false, ref v))
+ {
+ Debug.Log(v);
+ }
+ else
+ {
+ Debug.Log("未找到");
+ }
+ }
+
}
generated by cgit v1.1-26-g67d0 at 2025-05-18 17:33:52 +0000