C# 是否有相当于 C++ std::partial_sort 的方法？

Question

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

进行部分排序的最佳方法是什么，仅对列表中绝对需要排序的部分进行排序？ .NET 库中是否有相当于 C++ 的

std::partial_sort

函数？我该如何解决这个问题？

编辑：这是我想要的示例：

假设我需要根据某些排序标准获取 1000 个元素集中的第 21-40 个元素。为了加快排序速度，而且由于我每次都必须遍历整个数据集（这是一个基于 HTTP 的 Web 服务，无状态），因此我不需要排序整个数据集。我只需要正确排序元素 21-40。创建 3 个分区就足够了：元素 1-20，未排序（但全部小于元素 21）；元素 21-40，已排序；和元素 41-1000，未排序（但都大于元素 40）。

Answer 1

好的。根据您在回复我的评论时所说的话，我会尝试以下方法。

我希望能够说“第 4 到第 6”并得到类似：3， 2, 1（未排序，但都小于正确的第四个元素）； 4、5、6（已排序 并且在同一位置，它们将用于排序列表）； 8、7、9 （未排序，但都大于正确的第六个元素）。

让我们将 10 添加到列表中以使其更容易：10, 9, 8, 7, 6, 5, 4, 3, 2, 1。

因此，您可以做的是使用快速选择算法来查找第 i^th 和 k^th 元素。在上面的例子中，i 是 4，k 是 6。这当然会返回值 4 和 6。这将需要两次遍历您的列表。因此，到目前为止，运行时间为 O(2n) = O(n)。当然，下一部分很简单。我们关心的数据有下限和上限。我们需要做的就是再次遍历列表，查找上限和下限之间的任何元素。如果我们找到这样的元素，我们会将其放入一个新的列表中。最后，我们对仅包含我们关心的第 i^th 到第 k^th 元素的列表进行排序。

所以，我相信总运行时间最终是 O(N) + O((k-i)lg(k-i))

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;
    }
}

Answer 2

这是我尝试为此创建一个扩展方法（我总是从列表的开头进行排序，因此该函数不将起始索引作为参数；我将其作为读者的练习:-)）

public static class ListExtensions
{
    public static void PartialSort<T>(this List<T> list, int count) where T : IComparable
    {
        ArgumentNullException.ThrowIfNull(list);
        if (count > list.Count)
            throw new ArgumentOutOfRangeException(nameof(count), "Count must be less than or equal to the list count.");

        for (int i = 0; i < count; i++)
        {
            T min = list[i];
            int minIndex = i;
            for (int j = i + 1; j < list.Count; j++)
            {
                if (min.CompareTo(list[j]) == 1)
                {
                    min = list[j];
                    minIndex = j;
                }
            }

            // Remove before insert in order to not change the capacity of the list.
            list.RemoveAt(minIndex);

            list.Insert(i, min);
        }
    }
}

Answer 3

您可以使用 List.Sort(int, int, IComparer):

inputList.Sort(startIndex, count, Comparer<T>.Default);