c# - 按数组中定义的顺序对字符串列表进行排序的有效方法？

Question

我正在尝试按另一个数组中定义的顺序对字符串列表进行排序。我知道可以通过多种方式实现，但我不确定如何有效地做到这一点。我需要它能够处理一个包含数千个项目的大型未排序列表。这是我想出的:

List<string> sortStringListByArray(List<string> unsortedList, string[] order)
{
     List<string> sortedList = new List<string>();
     for(int i = 0; i < order.Length; i++)
     {
          foreach(string s in unsortedList)
          {
              if(s.Equals(order[i]))
              {
                  sortedList.Add(s);
              }
          }
     }
     return sortedList;
}

它按预期工作，但效率肯定不高。有什么方法可以在不遍历列表和订单的情况下执行此操作？

编辑:澄清

谢谢!

Answer 1

表示它的最简单方法是使用右内连接:

return order.Join(unsortedList, a => a, b => b, (a, b) => b).ToList();

---

使用 Lookup 或 Dictionary 的最佳时间复杂度是 O(n+m) :

var lookup = unsortedList.ToLookup(x => x);

return order.SelectMany(x => lookup[x]).ToList();

使用 Dictionary<string, int> 可以使上面的速度快几倍获取 unsortedList 中的项目计数, 然后遍历 order根据counts Dictionary中对应的值生成结果。

---

Lookup和 Dictionary使用 hash table存储值。为了在哈希表中找到一个项目，从该值计算出一个哈希值，这类似于该值在哈希表中的位置的估计位置/索引。这只允许在哈希表中查找(或不查找)值所需的 1 次或少量比较。因此，从 unsortedList 生成查找或字典的时间复杂度为 O(n) , 因为哈希表的平均查找时间为 O(1)