わかった。私のコメントへの返信であなたが言ったことに基づいて、私が試みることは次のとおりです。
「4番目から6番目まで」と言って、3、2、1（ソートされていませんが、適切な4番目の要素よりも少ない）のようなものを取得できるようにしたいです。4、5、6 (ソート済みで、ソート済みリストの場合と同じ場所にあります); 8、7、9 (ソートされていませんが、すべて適切な 6 番目の要素よりも大きい)。
簡単にするために、リストに 10 を追加しましょう: 10、9、8、7、6、5、4、3、2、1。
したがって、クイック選択アルゴリズムを使用して i番目と k番目の要素を見つけることができます。上記の場合、i は 4 で、k は 6 です。もちろん、値 4 と 6 が返されます。リストを 2 回通過する必要があります。したがって、これまでの実行時間は O(2n) = O(n) です。もちろん、次の部分は簡単です。気になるデータには下限と上限があります。必要なことは、上限と下限の間にある要素を探して、リストをもう一度パスすることだけです。そのような要素が見つかった場合は、それを新しい List にスローします。最後に、関心のある i番目から k番目の要素のみを含む List を並べ替えます。
したがって、総実行時間は最終的に O(N) + O((ki)lg(ki)) になると思います
static void Main(string[] args) {
//create an array of 10 million items that are randomly ordered
var list = Enumerable.Range(1, 10000000).OrderBy(x => Guid.NewGuid()).ToList();
var sw = Stopwatch.StartNew();
var slowOrder = list.OrderBy(x => x).Skip(10).Take(10).ToList();
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);
//Took ~8 seconds on my machine
sw.Restart();
var smallVal = Quickselect(list, 11);
var largeVal = Quickselect(list, 20);
var elements = list.Where(el => el >= smallVal && el <= largeVal).OrderBy(el => el);
Console.WriteLine(sw.ElapsedMilliseconds);
//Took ~1 second on my machine
}
public static T Quickselect<T>(IList<T> list , int k) where T : IComparable {
Random rand = new Random();
int r = rand.Next(0, list.Count);
T pivot = list[r];
List<T> smaller = new List<T>();
List<T> larger = new List<T>();
foreach (T element in list) {
var comparison = element.CompareTo(pivot);
if (comparison == -1) {
smaller.Add(element);
}
else if (comparison == 1) {
larger.Add(element);
}
}
if (k <= smaller.Count) {
return Quickselect(smaller, k);
}
else if (k > list.Count - larger.Count) {
return Quickselect(larger, k - (list.Count - larger.Count));
}
else {
return pivot;
}
}