Лучшие алгоритмы сортировки для C # / .NET в различных сценариях

Question

Каковы лучшие алгоритмы для сортировки данных в C #?

Существует ли один алгоритм сортировки, который может хорошо обрабатывать 80% сортировок?

Пожалуйста, приведите примеры кода, если применимо.

Answer 1

Проверьте этот сайт: Сравнение сортировок с анимацией

Краткий ответ: Быстрая сортировка

Более длинный ответ: Приведенный выше сайт покажет вам сильные и слабые стороны каждого алгоритма с изящной анимацией.

Короткий ответ: нет лучшего подхода ко всему виду (но вы знали, что, поскольку вы сказали 80% времени :)), но быстрая сортировка (или 3-сторонняя быстрая сортировка), вероятно, будет лучшим общим алгоритмом, который вы можете использовать .

Это алгоритм, используемый по умолчанию для списков в .Net, поэтому вы можете просто вызвать .Sort, если то, что у вас уже есть в списке.

На сайте, на который я указывал вам выше, есть псевдокод, если вы хотите узнать, как это реализовать.

Answer 2

Что вы пытаетесь отсортировать? Есть ли причина не использовать:

List<T>.Sort() ? 

Я уверен, что здесь используется QuickSort, и вам не нужно беспокоиться об ошибках кодирования. Вы можете реализовать IComparable, чтобы изменить то, что вы хотите отсортировать.

Если все ваши данные не помещаются в памяти ... что ж, вы отправляетесь в гонки с сортировкой Merge или что-то в этом роде.

Answer 3

Bubblesort и Insertionsort - O (n ^ 2), Mergesort и Quicksort - O (nlogn). Вы можете использовать метод Sort () из List, который реализует Quicksort, а также вы можете попробовать реализовать его и адаптировать к вашим потребностям. Вот базовая реализация: Quicksort

//O(nlogn) 
public static void QuickSort(int[] array, int init, int end)
{
   if (init < end)
   {
       int pivot = Partition(array, init, end);
       QuickSort(array, init, pivot-1);
       QuickSort(array, pivot + 1, end);
   }   
}

//O(n)
private static int Partition(int[] array, int init, int end)
{
   int last = array[end];
   int i = init - 1;
   for (int j = init; j < end; j++)
   {
        if (array[j] <= last)
        {
            i++;
            Exchange(array, i, j);     
         }
    }
    Exchange(array, i + 1, end);
    return i + 1;
}

private static void Exchange(int[] array, int i, int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

С http://yadiragarnicabonome.com/sorting-arrays/

Answer 4

попробуйте быструю сортировку: http://www.codeproject.com/KB/recipes/QuickSort_gen.aspx