您最多选择25个主题 主题必须以中文或者字母或数字开头,可以包含连字符 (-),并且长度不得超过35个字符

108 行
3.1 KiB

using System;
public static class KdTree3Utils
{
/*
This file implements derivate version of nth_element function in C#. Original Java source code is made by
Adam Horvath and you can find it from
http://blog.teamleadnet.com/2012/07/quick-select-algorithm-find-kth-element.html
This is free and unencumbered software released into the public domain.
*/
// Nth_element made with Quick select algorithm. Custom comparer. nthToSeek is zero base index
public static void nth_element<T>(T[] array, int startIndex, int nthToSeek, int endIndex, Comparison<T> comparison)
{
int from = startIndex;
int to = endIndex;
// if from == to we reached the kth element
while (from < to)
{
int r = from, w = to;
T mid = array[(r + w) / 2];
// stop if the reader and writer meets
while (r < w)
{
if (comparison(array[r], mid) > -1)
{ // put the large values at the end
T tmp = array[w];
array[w] = array[r];
array[r] = tmp;
w--;
}
else
{ // the value is smaller than the pivot, skip
r++;
}
}
// if we stepped up (r++) we need to step one down
if (comparison(array[r], mid) > 0)
{
r--;
}
// the r pointer is on the end of the first k elements
if (nthToSeek <= r)
{
to = r;
}
else
{
from = r + 1;
}
}
return;
}
// Nth_element made with Quick select algorithm. Default comparer. nthSmallest is zero base index
public static void nth_element<T>(T[] array, int startIndex, int nthSmallest, int endIndex)
{
int from = startIndex;
int to = endIndex;
// if from == to we reached the kth element
while (from < to)
{
int r = from, w = to;
T mid = array[(r + w) / 2];
// stop if the reader and writer meets
while (r < w)
{
if (System.Collections.Generic.Comparer<T>.Default.Compare(array[r], mid) > -1)
{ // put the large values at the end
T tmp = array[w];
array[w] = array[r];
array[r] = tmp;
w--;
}
else
{ // the value is smaller than the pivot, skip
r++;
}
}
// if we stepped up (r++) we need to step one down
if (System.Collections.Generic.Comparer<T>.Default.Compare(array[r], mid) > 0)
{
r--;
}
// the r pointer is on the end of the first k elements
if (nthSmallest <= r)
{
to = r;
}
else
{
from = r + 1;
}
}
return;
}
}