diff options
Diffstat (limited to 'Assets/Algorithms/Searching/SearchingHelper.cs')
| -rw-r--r-- | Assets/Algorithms/Searching/SearchingHelper.cs | 113 |
1 files changed, 92 insertions, 21 deletions
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; } } |