如何使我的MergeSort通用於不同的對象？

Question

我目前有一個合併排序，它根據每個節點中的一個整數（稱爲「F」（So Node.F））對一個節點列表進行排序。

但是，我想出了一個需要使用MergeSort的另一個對象列表 - 實體。但是，我想根據每個實體中的一個整數（它被稱爲「AmountEaten」（So Entity.AmountEaten））進行排序。

現在這裏是我的問題 - >使MergeSort類適用於所有對象。我已經用「對象」來替換所有對節點的引用，但是如何允許自定義條件進行排序？有沒有辦法提供它作爲參數。

如果沒有意義，在MergeSort中，我比較兩個值（例如，Left.F < Right.F）。使用通用對象時，這不起作用，因爲F不存在。我希望能夠在我的排序內比較對象內的任何內容（例如，Left.AmountEaten < Right.AmountEaten）。我無法弄清楚如何將此作爲參數。我立即想到了代表們，但我不確定如何/如果這是正確的。

由於排序處理列表而不是單個對象，因此我不能簡單地給出F/AmountEaten的參數，因爲我想訪問該變量，而不是該值。

如果您需要更多的細節/不明白，請詢問。

似乎已經達成某種形式的結論，但你能幫我做到嗎？

歸併類別：

static class MergeSort 
{ 
    public static IList<object> Sort(IList<object> input, Comparison<object> comparison /* Comparison is a delegate that works out the difference 
                         * between 2 values - Same signature used by List<T>.Sort */) 
    { 
     List<object> Result = new List<object>(); 
     Queue<object> Left = new Queue<object>(); //Switched from lists to queues because removing at index 0 is more efficient 
     Queue<object> Right = new Queue<object>(); 
     //Dequeue() and Count() have a time complexity of O(1) 

     if (input.Count <= 1) 
      return input; 

     int midpoint = input.Count/2; 

     for (int i = 0; i < midpoint; i++) 
      Left.Enqueue(input[i]); 
     for (int i = midpoint; i < input.Count; i++) 
      Right.Enqueue(input[i]); 

     Left = new Queue<object>(Sort(Left.ToList(), comparison)); //Recursion! :o 
     Right = new Queue<object>(Sort(Right.ToList(), comparison)); ; //This line and the one above split the list into smaller lists (left and right) 

     Result = Merge(Left, Right, comparison); //This joins the lists together 

     return Result; 
    } 

    private static List<object> Merge(Queue<object> Left, Queue<object> Right, Comparison<object> comparison) 
    { 
     int cmp = comparison(Left.Peek(), Right.Peek()); 
     //If cmp is less than 0, left is less. If it is greater, left is greater 

     List<object> Result = new List<object>(); 
     while (Left.Count /* O(1) operation */ > 0 && Right.Count > 0) 
     { 
      if (cmp < 0) 
       Result.Add(Left.Dequeue()); 
      //Left.RemoveAt(0) - Using a list to remove at a certain point is inefficient 
      else 
       Result.Add(Right.Dequeue()); 
     } 

     while (Left.Count > 0) 
      Result.Add(Left.Dequeue()); 

     while (Right.Count > 0) 
      Result.Add(Right.Dequeue()); 

     return Result; 
    } 
} 
} 

用法：

Entities = MergeSort.Sort(Entities, (p, q) => p.F.CompareTo(q.F)).ToList(); 

Answer 1

通常最好籤名是一個類似於由List<T>.Sort(...)使用的一個：

static void MergeSort<T>(IList<T> coll, Comparison<T> comparison) 
{ 
    ... 
    // < 0 coll[i] < coll[j], == 0 coll[i] == coll[j], > 0 coll[i] > coll[j] 
    int cmp = comparison(coll[i], coll[j]); 
    ... 
} 

使用：

MergeSort(coll, (p, q) => p.F.CompareTo(q.F)); 

注意，如果F是一個整數，往往你會看到比較像：(p, q) => p.F - q.F。這是可行的，因爲如果p.F > q.F然後p.F - q.F > 0等等。

其他可能的變體是由LINQ OrderBy(...)

使用的一個通常最好的簽名是一個類似於List<T>.Sort(...)使用的一個：

static void MergeSort<T, TKey>(IList<T> coll, Func<T, TKey> selector) 
{ 
    var comparer = Comparer<Tkey>.Default; 

    ... 
    // < 0 coll[i] < coll[j], == 0 coll[i] == coll[j], > 0 coll[i] > coll[j] 
    int cmp = comparer(selector(coll[i]), selector(coll[j])); 
    ... 
} 

使用：

MergeSort(coll, p => p.F); 

這裏我們傳遞給代表能夠返回「排序鍵」的方法，如p => p.F。這是一個慢一點，更難使用（但它可能在LINQ中使用，因爲它更類似於SQL中所做的）