Der beste Weg, um ein Array zu sortieren

Question

Angenommen, ich habe ein Array von Datensätzen, die ich basierend auf einem der Felder im Datensatz sortieren möchte. Was ist der beste Weg, dies zu erreichen?

TExample = record 
    SortOrder : integer; 
    SomethingElse : string; 
end; 

var SomeVar : array of TExample; 

Answer 1

Sie können Zeiger auf die Elemente des Arrays zu einem TList hinzufügen, dann TList.Sort mit einer Vergleichsfunktion aufrufen und schließlich ein neues Array erstellen und die Werte aus dem TList in der gewünschten Reihenfolge kopieren.

Wenn Sie jedoch die nächste Version D2009 verwenden, gibt es eine neue Sammlungsbibliothek, die Arrays sortieren kann. Es wird eine optionale IComparer<TExample> Implementierung für benutzerdefinierte Sortierreihenfolgen benötigt. Hier ist es in Aktion für Ihren speziellen Fall ist:

TArray.Sort<TExample>(SomeVar , TDelegatedComparer<TExample>.Construct(
    function(const Left, Right: TExample): Integer 
    begin 
    Result := TComparer<Integer>.Default.Compare(Left.SortOrder, Right.SortOrder); 
    end)); 

Answer 2

Verwenden einer der Sortier alorithms vorzuschlagen durch Wikipedia. Die Swap-Funktion sollte Array-Elemente unter Verwendung einer temporären Variablen des gleichen Typs wie die Array-Elemente austauschen. Verwenden Sie eine stabile Sortierung, wenn Einträge mit demselben Ganzzahlwert SortOrder in der Reihenfolge bleiben sollen, in der sie sich ursprünglich befanden.

Answer 3

Mit einer Reihe, würde ich entweder quicksort oder möglicherweise heapsort, und nur den Vergleich ändern TExample.SortOrder zu verwenden, wird der Swap-Teil noch einfach weiter handeln die Array- und Swap-Zeiger. Wenn das Array sehr groß ist, möchten Sie möglicherweise eine verkettete Listenstruktur, wenn viel eingefügt und gelöscht wird.

C basierte Routinen gibt es mehr hier http://www.yendor.com/programming/sort/

Eine andere Seite, haben aber pascal Quelle http://www.dcc.uchile.cl/~rbaeza/handbook/sort_a.html

Answer 4

Wenn Ihre Notwendigkeit von Zeichenfolge sortierte dann sortierte Verwendung TStringList und Rekord von TString.AddObject(string, Pointer(int_val)) hinzufügen.

Wenn aber nach Integer-Feld und String sortieren - verwenden Sie TObjectList und nach dem Hinzufügen aller Datensätze rufen Sie mit notwendigen sortierten Funktionen als Parameter.

Answer 5

TStringList haben effiziente Sortiermethode.
Wenn Sie Sort verwenden möchten, verwenden Sie ein Objekt TStringList mit der Eigenschaft Sorted True.

HINWEIS: Für mehr Geschwindigkeit, fügen Sie Objekte in einem nicht sortierten TStringList hinzu und ändern Sie am Ende die Eigenschaft auf True.
HINWEIS: Für die Sortierung nach Ganzzahl Feld, konvertieren Sie in String.
HINWEIS: Wenn doppelte Werte vorhanden sind, ist diese Methode nicht gültig.

Grüße.

Answer 6

Das hängt von der Anzahl der Datensätze ab, die Sie sortieren. Wenn Sie nur weniger als ein paar hundert sortieren, dann funktionieren die anderen Sortiermethoden gut, wenn Sie mehr sortieren werden, dann sehen Sie sich das alte vertrauenswürdige Turbo Power Projekt an. In der Quelle ist ein sehr guter Sortieralgorithmus enthalten. Eine, die sehr effizient Millionen von Datensätzen effizient sortiert.

Wenn Sie die tStringList-Methode zum Sortieren einer Liste von Datensätzen verwenden möchten, stellen Sie sicher, dass Ihre Ganzzahl nach rechts aufgefüllt ist, bevor Sie sie in die Liste einfügen. Sie können das Format ('%. 10d', [rec.Sortierreihenfolge]) rechts auf 10 Stellen zum Beispiel ausrichten.

Answer 7

(Ich weiß, das ein Jahr später, aber immer noch nützliche Dinge.)

Skamradt Vorschlag aufzufüllen ganzzahlige Werte annimmt, die Sie sortieren wollen eine Zeichenfolge vergleichen mit. Das wäre langsam. Aufrufformat() für jede Einfügung, langsamer noch. Stattdessen möchten Sie einen Ganzzahlvergleich durchführen.

Sie beginnen mit einem Satztyp:

TExample = record 
    SortOrder : integer; 
    SomethingElse : string; 
end; 

Sie nicht angeben, wie die Datensätze gespeichert wurden, oder wie man sie wollte einmal zugreifen sortiert. Also lassen Sie uns annehmen, dass Sie sie in einem dynamischen Array setzen:

var MyDA Array of TExample; 
... 
    SetLength(MyDA,NewSize);   //allocate memory for the dynamic array 
    for i:=0 to NewSize-1 do begin  //fill the array with records 
    MyDA[i].SortOrder := SomeInteger; 
    MyDA[i].SomethingElse := SomeString; 
    end; 

Jetzt können Sie durch den ganzzahligen Wert SortOrder dieses Array sortieren möchten. Wenn Sie eine TStringList (also die ts.Find-Methode) verwenden möchten, sollten Sie jede Zeichenfolge zur Liste hinzufügen und SortOrder als Zeiger hinzufügen. Dann sortieren auf den Zeiger:

var tsExamples: TStringList;   //declare it somewhere (global or local) 
... 
    tsExamples := tStringList.create; //allocate it somewhere (and free it later!) 
... 
    tsExamples.Clear;     //now let's use it 
    tsExamples.sorted := False;   //don't want to sort after every add 
    tsExamples.Capacity := High(MyDA)+1 //don't want to increase size with every add 
             //an empty dynamic array has High() = -1 
    for i:=0 to High(MyDA) do begin 
    tsExamples.AddObject(MyDA[i].SomethingElse,TObject(MyDA[i].SortOrder)); 
    end; 

Hinweis den Trick der Integer SortOrder in einen TObject Zeiger Gießen, die in der TStringList.Object Eigenschaft gespeichert wird. (Dies hängt von der Tatsache, dass Integer und Zeiger die gleiche Größe haben.) Irgendwo wir eine Funktion definieren, müssen die TObject Zeiger vergleichen:

function CompareObjects(ts:tStringList; Item1,Item2: integer): Integer; 
var i,j: integer; 
begin 
    Result := integer(ts.Objects[i]) - integer(ts.Objects[j]; 
end; 

Jetzt können wir die tsList auf .Object sortieren, indem .CustomSort Aufruf statt von .Sort (die auf der String-Wert sortieren würde.)

tsExample.CustomSort(@CompareObjects);  //Sort the list 

The TStringList jetzt sortiert, so dass Sie über sie von 0 bis .Count-1 und lesen Sie die Saiten in sortierter Reihenfolge durchlaufen können.

Angenommen, Sie wollten keine TStringList, nur ein Array in sortierter Reihenfolge. Oder die Datensätze enthalten mehr Daten als nur die eine Zeichenfolge in diesem Beispiel, und Ihre Sortierreihenfolge ist komplexer. Sie können den Schritt des Hinzufügens jeder Zeichenfolge überspringen und den Array-Index einfach als Elemente in einer TList hinzufügen. Tun Sie alles über die gleiche Art und Weise, mit der Ausnahme eines TList anstelle von TStringList:

var Mlist: TList;     //a list of Pointers 
... 
    for i:=0 to High(MyDA) do 
    Mlist.add(Pointer(i));  //cast the array index as a Pointer 
    Mlist.Sort(@CompareRecords); //using the compare function below 

function CompareRecords(Item1, Item2: Integer): Integer; 
var i,j: integer; 
begin 
    i := integer(item1);   //recover the index into MyDA 
    j := integer(item2);   // and use it to access any field 
    Result := SomeFunctionOf(MyDA[i].SomeField) - SomeFunctionOf(MyDA[j].SomeField); 
end; 

Nun, da Mlist sortiert ist, verwenden Sie es als eine Nachschlagtabelle das Array in sortierter Reihenfolge zuzugreifen:

for i:=0 to Mlist.Count-1 do begin 
    Something := MyDA[integer(Mlist[i])].SomeField; 
    end; 

Wie Wenn ich über die TList iteriert, erhalten wir die Array-Indizes in sortierter Reihenfolge zurück. Wir müssen sie nur auf Integers zurückwerfen, da die TList denkt, dass sie Zeiger sind.

Ich mag es so, aber Sie könnten auch echte Zeiger auf Array-Elemente in der TList setzen, indem Sie die Adresse des Array-Elements anstelle von dessen Index hinzufügen. Um sie dann zu verwenden, würden Sie sie als Zeiger auf TExample-Datensätze ausgeben. Das sagen Barry Kelly und CoolMagic in ihren Antworten.

Answer 8

Der Quicksort-Algorithmus wird häufig verwendet, wenn eine schnelle Sortierung erforderlich ist. Delphi ist (oder war) es zum Beispiel für List.Sort verwenden. Delphi-Liste kann verwendet werden, um alles zu sortieren, aber es ist ein schwergewichtiger Container, der wie ein Array von Zeigern auf Strukturen aussehen soll. Es ist Schwergewicht, auch wenn wir in diesem Thread Tricks wie Guy Gordon verwenden (Putting index oder irgendwas an Stelle von Zeigern, oder direkt Werte setzen, wenn sie kleiner als 32 Bit sind): wir müssen eine Liste erstellen und so weiter ...

Konsequenterweise könnte eine Alternative zur einfachen und schnellen Sortierung eines Arrays von struct die Verwendung von qsort C runtime function aus msvcrt.dll sein.

Hier ist eine Erklärung, die gut sein könnte (Achtung: Code nur auf Windows portierbar).

type TComparatorFunction = function(lpItem1: Pointer; lpItem2: Pointer): Integer; cdecl; 
procedure qsort(base: Pointer; num: Cardinal; size: Cardinal; lpComparatorFunction: TComparatorFunction) cdecl; external 'msvcrt.dll'; 

Vollständiges Beispiel here.

Beachten Sie, dass das Sortieren des Datensatzarrays bei großen Datensätzen langsam erfolgen kann. In diesem Fall kann das Sortieren eines Zeigerarrays auf die Datensätze schneller sein (Irgendwie ähnlich wie bei der Liste).

Answer 9

Ich habe ein sehr einfaches Beispiel erstellt, das korrekt funktioniert, wenn das Sortierfeld eine Zeichenfolge ist.

Type 
    THuman = Class 
    Public 
    Name: String; 
    Age: Byte; 
    Constructor Create(Name: String; Age: Integer); 
    End; 

Constructor THuman.Create(Name: String; Age: Integer); 
Begin 
    Self.Name:= Name; 
    Self.Age:= Age; 
End; 

Procedure Test(); 
Var 
Human: THuman; 
Humans: Array Of THuman; 
List: TStringList; 
Begin 

SetLength(Humans, 3); 
Humans[0]:= THuman.Create('David', 41); 
Humans[1]:= THuman.Create('Brian', 50); 
Humans[2]:= THuman.Create('Alex', 20); 

List:= TStringList.Create; 
List.AddObject(Humans[0].Name, TObject(Humans[0])); 
List.AddObject(Humans[1].Name, TObject(Humans[1])); 
List.AddObject(Humans[2].Name, TObject(Humans[2])); 
List.Sort; 

Human:= THuman(List.Objects[0]); 
Showmessage('The first person on the list is the human ' + Human.name + '!'); 

List.Free; 
End; 

Answer 10

Wenn Sie Delphi XE2 oder neuer haben, können Sie versuchen:

var 
    someVar: array of TExample; 
    list: TList<TExample>; 
    sortedVar: array of TExample; 
begin 
    list := TList<TExample>.Create(someVar); 
    try 
    list.Sort; 
    sortedVar := list.ToArray; 
    finally 
    list.Free; 
    end; 
end;