最有效的排序数组的方式，并保持相应的原始索引

本文关键字：原始 索引 排序 有效 数组 方式 | 更新日期: 2023-09-27 18:10:05

我想在c#中对整数数组进行排序，但也要保留数组中每个元素对应的原始索引。

我的第一个想法是转换为一个Dictionary对象，键作为索引，值作为值;然后用linq按值排序。我觉得这个性能不太好。还有其他可能的解决方案吗?性能是关键。

这似乎是一个很好的和简单的解决方案;但这是最快的方法吗?

最有效的排序数组的方式，并保持相应的原始索引

如果您讨论的是时间性能，您可以将数组复制到第二个数组中，对第二个数组进行排序，然后使用两个数组分别实现功能。这将使O(1)能够访问所需的元素。

如果你谈论的是空间方面的性能，你使用字典的方法是最好的，因为它只会保留一个元素的副本，从而产生O(n)空间。

像往常一样，在真正遇到性能问题之前不要进行优化。

而老式的和未类型化的数组。Sort(数组键，数组项)在跟踪索引方面比LINQ更好。

进入数组实现:

    数组 c# Github源代码
  • CPP平台实现部分
  • Matt Warren -如果你真的想了解Array
<标题>数组。Sort vs Linq
    [GlobalSetup]
    public virtual void Setup()
    {
        data = new T[N];
        indexes = new int[N];
        for (var cc = 0; cc < N; cc++)
        {
            data[cc] = GetRandom();
            indexes[cc] = cc;
        }
    }
    // Clone is nessesary as Array.Sort is done in place, ie the next call will be incorrectly given a pre-sorted list
    private T[] GetTestData() => (T[]) data.Clone();
    private int[] GetTestDataIndex() => (int[])indexes.Clone();
    [Benchmark]
    public virtual void Sort()
    {
        Array.Sort(GetTestData());
    }
    [Benchmark]
    public virtual void SortMaintainIndex()
    {
        Array.Sort(GetTestData(), GetTestDataIndex());
    }
    [Benchmark]
    public virtual void SortWithLinq()
    {
        int cc = 0;
        var withIndex = GetTestData()
                  .Select(x => (cc++, x))
                  .OrderBy(x => x.x)
                  .ToArray();
    }

在速度方面没有可比性:来源:https://gist.github.com/guylangston/cd9a0719d467f020eba46c6d0beb0584

BenchmarkDotNet=v0.10.14, OS=Windows 10.0.17134
Intel Core i7-3930K CPU 3.20GHz (Ivy Bridge), 1 CPU, 12 logical and 6 physical cores
.NET Core SDK=2.1.300
  [Host]     : .NET Core 2.1.0 (CoreCLR 4.6.26515.07, CoreFX 4.6.26515.06), 64bit RyuJIT
  DefaultJob : .NET Core 2.1.0 (CoreCLR 4.6.26515.07, CoreFX 4.6.26515.06), 64bit RyuJIT

            Method |     N |        Mean |      Error |     StdDev |      Median |
------------------ |------ |------------:|-----------:|-----------:|------------:|
              Sort |  1000 |    35.85 us |  0.3234 us |  0.2700 us |    35.76 us |
 SortMaintainIndex |  1000 |    60.82 us |  0.2280 us |  0.1780 us |    60.76 us |
      SortWithLinq |  1000 |   172.26 us |  3.3984 us |  3.7773 us |   170.75 us |
              Sort | 10000 |   611.82 us | 13.8881 us | 18.0584 us |   602.77 us |
 SortMaintainIndex | 10000 |   889.25 us | 18.6503 us | 28.4810 us |   874.06 us |
      SortWithLinq | 10000 | 2,484.35 us | 57.8378 us | 54.1015 us | 2,476.72 us |

在. net 中有一组特定的内置函数来完成此操作。查找Array的重载。用TKey[]参数排序。有几个重载允许您指定要排序的子范围或自定义IComparer<TKey>。秘诀是传入原始数组作为keys参数，并传入标识数组(0, 1, 2,... n-1)作为items参数。下面的函数将为您完成所有的工作:

/// sort array 'rg', returning the original index positions
static int[] SortAndIndex<T>(T[] rg)
{
    int i, c = rg.Length;
    var keys = new int[c];
    if (c > 1)
    {
        for (i = 0; i < c; i++)
            keys[i] = i;
        System.Array.Sort(rg, keys /*, ... */);
    }
    return keys;
}
同样，对于Array.Sort，请注意我们要小心可能混淆的参数名称。项作为第一个参数传入(称为"keys")，而索引(感觉更像键)作为第二个参数传入(称为"items")。

用法非常清楚:

var rgs = new[] { "xyz", "a", "", "bb", "pdq" };
int[] idx = SortAndIndex(rgs);  // rgs: { "",  "a", "bb", "pdz", "xyz" }
                                // idx: {  2,   1,    3,    4,     0   }

这涵盖了OP的情况，您实际上希望原始数据最终排序。如果你需要的话，你可以在这里停止阅读。

但是一个相关的问题是，如果你想要相同的排序索引，但是你不想修改原始数组，那么怎么办?我们如何在不改变原始项的顺序的情况下获得排序索引?

我发现这样做的最好方法实际上是使用上面的过程对数据进行排序并获得索引，但是然后使用该排序索引将排序项恢复到原始顺序

可能有几种方法可以做到这一点，但由于这个问题提到了效率，我可以展示一些保证执行最少数量的原始项交换的代码，同时只使用单个T存储元素，以便将项恢复到原始的未排序的顺序:

static unsafe void RevertSortIndex<T>(T[] rg, int[] keys)
{
    int i, k, c;
    int* rev = stackalloc int[c = rg.Length];
    for (i = 0; i < c; i++)
        rev[k = keys[i]] = k != i ? i : -1;
    do
        if ((i = rev[--c]) != c && i >= 0)
        {
            T t = rg[k = c];
            do
            {
                rg[k] = rg[i];
                rev[k] = -1;
            }
            while ((i = rev[k = i]) != c);
            rg[k] = t;
            rev[k] = -1;
        }
    while (c > 0);
}

为了只使用单个T元素进行交换，并且只将每个元素移动一次到其最终位置，您必须按照数据确定的非常特定的顺序进行交换。通过一个临时反向索引(rev)可以简化这一点，它很容易从keys创建。这里它显示为stackalloc，但如果您不想走那条路，您可以轻松地将其替换为托管int[]分配。

不用太详细，任何排序索引都包含一个或多个循环(或循环"链")，这些循环从一个链接到另一个，并且遵循每个循环为您提供了一个最佳顺序，您可以将这些元素恢复到原始位置，同时只保留一个临时T。这就是内部do...while循环所做的。

外层的while...循环需要扫描额外的循环，因为排序索引作为一个整体可能有多个独立的链，它们都需要被访问。重要的是，为了得到正确的结果，每个链必须只处理一次，不能再重复处理。因此，为了找出是否已经处理了任何给定的交换，它在rev临时反向索引中的条目被设置为-1。这表明rg中相应的T元素已经被移动(作为前一个链的一部分)。

完整的用法示例如下:

var rgs = new[] { "xyz", "a", "", "bb", "pdq" };
int[] idx = SortAndIndex(rgs);
// rgs: { "",  "a", "bb", "pdz", "xyz" }
// idx: {  2,   1,    3,    4,     0   }
RevertSortIndex(rgs, idx);
// rgs: { "xyz", "a", "", "bb", "pdq"  }
// idx: {   2,   1,    3,    4,     0  }    (unchanged)

最后需要注意的是，SortAndIndex和RevertSortIndex的组合可能会给rgs最终未被修改的外观，但这不应该依赖于并发目的。如果rgs同时从其他地方可见，则中间状态将可见。

您可以创建一个KeyValuePairs数组，然后按值排序:

Array.Sort(array, (left, right) => left.Value.CompareTo(right.Value))

但是数组。Sort(Array, Array)看起来也不错

相关文章：