时间戳

首页 > 解决方案 > 如何使用固定元素对通用序列进行排序

c# - 如何使用固定元素对通用序列进行排序

问题描述

我有一个数字序列，我需要对它们进行排序，除了一些应该保持在初始位置的数字。例如，假设我的序列是：

33, 20, 48, 17, 48, 36, 20, 12, 25

...并且数字 20 和 25 应该保持固定。然后对序列进行排序后，我应该得到以下结果：

12, 20, 17, 33, 36, 48, 20, 48, 25

我怎样才能实现这种受限排序？我想实现的方法有这个签名：

public static IEnumerable<TSource> OrderBy<TSource, TKey>(
    this IEnumerable<TSource> source,
    Func<TSource, TKey> keySelector,
    Func<TSource, bool> pinPredicate)
{
    //...
}

然后可以使用此方法产生理想的结果，如下所示：

var source = new int[] { 33, 20, 48, 17, 48, 36, 20, 12, 25 };
var result = source.OrderBy(n => n, n => n == 20 || n == 25);

我直接尝试通过链接 LINQ 方法来解决这个问题Select，OrderBy但都失败了。这个问题似乎太复杂了，无法使用单链 LINQ 方法来解决。

标签： c#algorithmlinqsorting

解决方案

你可以试试这个 LINQ 解决方案。

private static IEnumerable<int> PinnedSort(IEnumerable<int> numbers, ISet<int> pinnedNumbers)
{
    // Extract pinned numbers into (number, index) tuples
    // Might be cleaner to make a class here instead
    var onlyPinnedNumbers = numbers
        .Select((number, index) => (number, index))
        .Where(pair => pinnedNumbers.Contains(pair.number));

    // Sort other numbers that don't exist in pinned numbers set
    var sortedNumbers = numbers
        .Where(number => !pinnedNumbers.Contains(number))
        .OrderBy(number => number)
        .ToList();

    // Insert pinned numbers into sorted list
    foreach (var (number, index) in onlyPinnedNumbers)
    {
        sortedNumbers.Insert(index, number);
    }

    return sortedNumbers;
}

可以这样运行：

var numbers = new int[] { 33, 20, 48, 17, 48, 36, 20, 12, 25 };

// Store pinned numbers in hashset, for O(1) lookups
var pinnedNumbers = new HashSet<int> { 20, 25 };

var pinnedSort = PinnedSort(numbers, pinnedNumbers);

Console.WriteLine("{ " + string.Join(", ", pinnedSort) + " }");

输出：

{ 12, 20, 17, 33, 36, 48, 20, 48, 25 }

推荐阅读