字典排序.NET 2.0

Question

我遇到一個問題，如何正確排序dictonary在NET 2.0。這段代碼有點老了（2002年或者其他），它可以工作，但不是我想要的。由於「字典」可能非常龐大，因此這種排序功能可能需要很長時間，而客戶端卻沒有這麼做。

人有一個想法如何做到這一點，我知道唯一的辦法就是添加一個排序依據什麼的，因爲我在當它是2002年

注花園裏玩：這是代碼一個正在進行的網站，問題是，我的老闆想要這個速度更快，但我不能對項目做出巨大的改變。

排序函數本身的工作原理是這樣的：有一本字典AvailableFlight其中包含飛行物體（與TotalPrice）。這來自外部來源，所以預過濾不是一種選擇。要達到的目標是讓最低TotalPrice的航班位於頂部。

爲人民誰不知道我要問，在我的項目有一個字典誰包含存儲爲相應整鍵對象的飛行物體。 A 航班對象有財產總價需要排序ASC。這發生在我提供的代碼中，只有處理這段代碼的時間大約需要30秒或更長時間，這是不可接受的。所以問題是，我該如何改進，以便減少時間處理。

public void SortFlightResult() 
    { 
     //bool to check sorting is done or not 
     bool blSort = true; 
     //bool to stay in while or not 
     bool blWhileSort = true; 
     while (blWhileSort) 
     { 
      //check the availableFlights 
      foreach (int i in AvailableFlights.Keys) 
      { 
       foreach (int j in AvailableFlights.Keys) 
       { 
        //if id j is greater then id i and price is less then j must be in place of i 
        if ((AvailableFlights[j].TotalPrice < AvailableFlights[i].TotalPrice) && (j > i)) 
        { 
         //set temperary AvailableFlight object 
         AvailableFlight avTemp = new AvailableFlight(); 
         avTemp = AvailableFlights[i]; 
         AvailableFlights[i] = AvailableFlights[j]; 
         //keep id of the i (if j.id = 3 and i.id = 2) replace i with j but let id = 2 
         AvailableFlights[i].ID = i; 
         AvailableFlights[j] = avTemp; 
         AvailableFlights[j].ID = j; 
         //set bool fase so we know sort is not done 
         blSort = false; 
         //end both foreach loop so we can start over from the top of availableFlights 
         goto endLoop; 
        } 
       } 
      } 
     endLoop: 
      //if true --> availableFlights is sorted set bool while false to quit the function 
      if (blSort) 
      { 
       blWhileSort = false; 
      } 
      else 
      {//set bool sort back to true 
       blSort = true; 
      } 
     } 
    } 

---

所有瞎扯淡一邊，感謝@D士丹利對他有用的評論。 我更改爲算法到堆排序和處理排序的時間從約30秒到400毫秒，真的很高興！

對誰感興趣的堆排序代碼的人：

堆排序

public void HeapSort() 
    { 
     Stopwatch watch = System.Diagnostics.Stopwatch.StartNew(); 

     //Build Max-Heap 
     Dictionary<int, AvailableFlight> input = AvailableFlights; 
     int heapSize = input.Keys.Count; 

     for (int p = (heapSize -1) /2; p >= 0; p--) 
     { 
      MaxHeapify(AvailableFlights, heapSize, p); 
     } 
     for (int i = AvailableFlights.Count - 1; i > 0; i--) 
     { 
      //Swap 
      AvailableFlight temp = input[i]; 
      input[i] = input[0]; 
      input[0] = temp; 

      heapSize--; 
      MaxHeapify(AvailableFlights, heapSize, 0); 
     } 

     watch.Stop(); 
     Debug.WriteLine("SortFlightResult 2: " + watch.ElapsedMilliseconds); 
    } 

MaxHeapify

private static void MaxHeapify(Dictionary<int, AvailableFlight> input, int heapSize, int index) 
    { 
     int left = (index + 1) * 2 - 1; 
     int right = (index + 1) * 2; 
     int largest = 0; 

     if (left < heapSize && input[left].TotalPrice > input[index].TotalPrice) 
     { 
      largest = left; 
     } 
     else 
     { 
      largest = index; 
     } 

     if (right < heapSize && input[right].TotalPrice > input[largest].TotalPrice) 
     { 
      largest = right; 
     } 
     if (largest != index) 
     { 
      AvailableFlight temp = input[index]; 
      input[index] = input[largest]; 
      input[largest] = temp; 

      MaxHeapify(input, heapSize, largest); 
     } 
    } 

Answer 1

假設你有這樣的事情AvailableFlight類：

public class AvailableFlight 
{ 
    public decimal TotalPrice { get; set; } 
    // ... more properties 
} 

您可以創建實施IComparer<AvailableFlight>像這樣一類：

public class FlightByPriceComparer : IComparer<AvailableFlight> 
{ 
    public int Compare(AvailableFlight x, AvailableFlight y) 
    { 
     if (ReferenceEquals(x, null)) 
      return ReferenceEquals(y, null) ? 0 : -1; 
     if (ReferenceEquals(y, null)) return 1; 
     return x.TotalPrice.CompareTo(y.TotalPrice); 
    } 
} 

，並以此來梳理你的字典的值的List<AvailableFlight>：

Dictionary<int, AvailableFlight> AvailableFlights = ... // whereever you got them from 
List<AvailableFlight> sortedFlights = new List<AvailableFlight>(AvailableFlights.Values); 
sortedFlights.Sort(new FlightByPriceComparer()); 

這應該是比你的冒泡排序更快，根據MSDN它使用這些排序算法：

此方法使用System.Array.Sort，它使用QuickSort算法。此實現執行不穩定的排序;也就是說，如果兩個元素相等，他們的順序可能不會被保留。相反，穩定的排序保留了相同元素的順序。

平均而言，此方法是O（n log n）操作，其中n是Count;在最壞的情況下，它是一個O（n^2）操作。

---

請注意，這是不可能的排序字典由其價值觀，有SortedDictionary但僅通過其Keys排序。

Answer 2

使用System.Linq的，以方便和清晰閱讀：

AvailableFlights = AvailableFlights.OrderBy(x => x.Value.TotalPrice).ToDictionary(x => x.Key, x=>x.Value);