Die besten Sortieralgorithmen für C#/.NET in verschiedenen Szenarien

Question

Was sind die besten Algorithmen zum Sortieren von Daten in C#?

Gibt es einen Sortieralgorithmus, der 80% gut verarbeiten kann?

Bitte geben Sie gegebenenfalls Codebeispiele an.

Answer 1

Check out this site: Sorting Comparisons with Animtations

Kurze Antwort: Quicksort

Lange Antwort: Die oben genannte Seite zeigt Ihnen die Stärken und Schwächen der einzelnen Algorithmus mit einigen raffinierten Animationen.

Die kurze Antwort ist, es gibt keine beste Allround-Sortierung (aber Sie wussten, dass, weil Sie in 80% der Zeit gesagt :)) aber QuickSort (oder 3 Way Quick Sort) wahrscheinlich der beste allgemeine Algorithmus, den Sie verwenden könnten .

Dies ist der Algorithmus, der standardmäßig für Listen in .Net verwendet wird. Sie können also einfach .Sort anrufen, wenn das, was Sie haben, bereits in einer Liste ist.

Es gibt Pseudo-Code auf der Website, auf die ich Sie oben gezeigt habe, wenn Sie sehen möchten, wie Sie dies implementieren.

Answer 2

try quicksort: http://www.codeproject.com/KB/recipes/QuickSort_gen.aspx

Answer 3

Was möchten Sie sortieren? Gibt es einen Grund, nicht zu verwenden:

List<T>.Sort() ? 

Ich bin sicher, dass dies QuickSort verwendet, und Sie nicht über irgendwelche Codierungsfehler zu kümmern. Sie können IComparable implementieren, um zu ändern, was Sie sortieren möchten.

Wenn alle Ihre Daten nicht in den Speicher passen ... nun, Sie sind zu den Rennen mit Merge sort oder etwas in diese Richtung.

Answer 4

Der Bubblesort und der Insertionsort sind O (n^2), der Mergesort und der Quicksort sind O (nlogn). Sie können die Methode Sort() von List verwenden, die Quicksort implementiert, oder Sie können es auch implementieren und an Ihre Bedürfnisse anpassen. Hier ist eine einfache Implementierung: 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; 
} 

Von https://yadiragarnica.wordpress.com/2015/10/15/sorting-arrays/