Словарь Сортировка .NET 2.0

Question

У меня возникла проблема с тем, как правильно сортировать диктатор в .NET 2.0. Этот бит кода немного старый (2002 или что-то еще), и он работает, но не так, как я хочу. Потому что AvailableFlights Словарь может быть очень огромным, эта функция сортировки может занять много времени, что у клиентов нет.

Кто-нибудь есть идеи, как это сделать, единственный способ, которым я знаю, чтобы добавить OrderBy или что-то, так как я играл в саду, когда он был 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; 
      } 
     } 
    } 

---

Все Bullsh * т в сторону, благодаря @d Stanley за его ПОЛЕЗНЫЕ комментарий. Я Изменен алгоритм к Heap рода и время обработки порезов сортировки вниз от приблизительно 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);