C#等价于C++ std :: partial_sort吗？

Question

我正在尝试通过许多标准为可排序的数据集实现分页算法.不幸的是,虽然其中一些标准可以在数据库级别实现,但有些必须在应用程序级别完成(我们必须与另一个数据源集成).我们有一个分页(实际上是无限滚动)的要求,并且正在寻找一种方法来最小化在每个分页调用时在应用程序级别对整个数据集进行排序的痛苦.

进行部分排序的最佳方法是什么,只排序绝对需要排序的列表部分？是否有相当于std::partial_sort.NET库中可用的C++ 函数？我该如何解决这个问题？

编辑:这是我想要的一个例子:

假设我需要根据一些排序标准获得1000个元素集的元素21-40.为了加快排序速度,因为我每次都必须遍历整个数据集(这是一个基于HTTP的Web服务,这是无状态的),我不需要整个数据集.我只需要正确排序21-40元素.创建3个分区就足够了:元素1-20,未排序(但都小于元素21); 元素21-40,排序 ; 和元素41-1000,未排序(但都大于元素40).

Answer 1

好.以下是我根据您在回复我的评论时所说的内容.

我想能够说"第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 ^个元素.在你的情况下,我是4,k是6.那当然会返回值4和6.这将在你的列表中进行两次传递.所以,到目前为止,运行时间是O(2n)= O(n).当然,下一部分很简单.我们关注的数据有上下限.我们需要做的就是再次通过我们的列表来查找我们的上限和下限之间的任何元素.如果我们找到这样一个元素,我们将它扔进一个新的List.最后,我们对List进行排序,其中仅包含我们关心的^第 i ^个到^第 k ^个元素.

所以,我相信总运行时最终为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;
    }
}