Der beste Weg, ein Array zu sortieren
https://stackoverflow.com/questions/41733
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Angenommen, ich habe eine Reihe 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;
Lösung
Sie können Zeiger auf die Elemente des Arrays zu a hinzufügen TList, Dann ruf an TList.Sort mit einer Vergleichsfunktion, und schließlich ein neues Array erstellen und die Werte in der gewünschten Reihenfolge aus der TList kopieren.
Wenn Sie jedoch die nächste Version, D2009, verwenden, gibt es eine neue Sammlungsbibliothek, die Arrays sortieren kann.Es ist optional IComparer<TExample> Implementierung für benutzerdefinierte Sortierreihenfolgen.Hier ist es für Ihren speziellen Fall in Aktion:
TArray.Sort<TExample>(SomeVar , TDelegatedComparer<TExample>.Construct(
function(const Left, Right: TExample): Integer
begin
Result := TComparer<Integer>.Default.Compare(Left.SortOrder, Right.SortOrder);
end));
Andere Tipps
(Ich weiß, das ist ein Jahr später, aber immer noch nützliches Zeug.)
Skamradts Vorschlag, ganzzahlige Werte aufzufüllen, setzt voraus, dass Sie mithilfe eines Zeichenfolgenvergleichs sortieren.Das wäre langsam.Der Aufruf von format() für jede Einfügung ist noch langsamer.Stattdessen möchten Sie einen Ganzzahlvergleich durchführen.
Sie beginnen mit einem Datensatztyp:
TExample = record
SortOrder : integer;
SomethingElse : string;
end;
Sie haben nicht angegeben, wie die Datensätze gespeichert wurden oder wie Sie nach der Sortierung darauf zugreifen möchten.Nehmen wir also an, Sie fügen sie in ein dynamisches Array ein:
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 möchten Sie dieses Array nach dem ganzzahligen Wert SortOrder sortieren.Wenn Sie eine TStringList ausgeben möchten (Sie können also die Methode ts.Find verwenden), sollten Sie jede Zeichenfolge zur Liste hinzufügen und die Sortierreihenfolge als Zeiger hinzufügen.Dann sortieren Sie nach dem 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;
Beachten Sie den Trick, die Integer SortOrder in einen TObject-Zeiger umzuwandeln, der in der TStringList.Object-Eigenschaft gespeichert wird.(Dies hängt von der Tatsache ab, dass Integer und Pointer die gleiche Größe haben.) Irgendwo müssen wir eine Funktion definieren, um die TObject-Zeiger zu 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 nach .Object sortieren, indem wir .CustomSort anstelle von .Sort aufrufen (was nach dem Zeichenfolgenwert sortieren würde).
tsExample.CustomSort(@CompareObjects); //Sort the list
Die TStringList ist jetzt sortiert, sodass Sie sie von 0 bis .Count-1 durchlaufen und die Zeichenfolgen in sortierter Reihenfolge lesen können.
Angenommen, Sie möchten keine TStringList, sondern 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 einfach den Array-Index als Elemente in einer TList hinzufügen.Machen Sie alles oben auf die gleiche Weise, außer dass Sie eine TList anstelle von TStringList verwenden:
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;
Nachdem Mlist nun sortiert ist, verwenden Sie es als Nachschlagetabelle, um in sortierter Reihenfolge auf das Array zuzugreifen:
for i:=0 to Mlist.Count-1 do begin
Something := MyDA[integer(Mlist[i])].SomeField;
end;
Während ich die TList durchlaufe, erhalten wir die Array-Indizes in sortierter Reihenfolge zurück.Wir müssen sie nur wieder in Ganzzahlen umwandeln, da die TList sie für Zeiger hält.
Ich mache das gerne so, aber Sie könnten auch echte Zeiger auf Array-Elemente in der TList setzen, indem Sie die Adresse des Array-Elements anstelle seines Index hinzufügen.Um sie dann zu verwenden, würden Sie sie als Zeiger auf TExample-Datensätze umwandeln.Dies ist es, was Barry Kelly und CoolMagic in ihren Antworten gesagt haben.
Wenn Sie eine Sortierung nach Zeichenfolge benötigen, verwenden Sie sortiert TStringList und fügen Sie den Aufzeichnung von hinzu TString.AddObject(string, Pointer(int_val)).
Aber wenn nötig, sortieren Sie nach Ganzzahlfeld und Zeichenfolge – verwenden Sie TObjectList und nach dem Hinzufügen aller Datensätze aufrufen TObjectList.Sort mit notwendigen sortierten Funktionen als Parameter.
Dies hängt alles von der Anzahl der Datensätze ab, die Sie sortieren.Wenn Sie nur weniger als ein paar Hundert sortieren, funktionieren die anderen Sortiermethoden gut. Wenn Sie mehr sortieren möchten, werfen Sie einen Blick auf den alten, bewährten Turbo Power SysTools Projekt.In der Quelle ist ein sehr guter Sortieralgorithmus enthalten.Eines, das sehr gute Arbeit leistet und Millionen von Datensätzen effizient sortiert.
Wenn Sie die tStringList-Methode zum Sortieren einer Liste von Datensätzen verwenden, stellen Sie sicher, dass Ihre Ganzzahl rechts aufgefüllt wird, bevor Sie sie in die Liste einfügen.Du kannst den ... benutzen format('%.10d',[rec.sortorder]) zum Beispiel rechtsbündig auf 10 Ziffern ausrichten.
Der Quicksort-Algorithmus wird häufig verwendet, wenn eine schnelle Sortierung erforderlich ist.Delphi verwendet (oder nutzte) es beispielsweise für List.Sort.Delphi List kann zum Sortieren aller Dinge verwendet werden, es ist jedoch ein schwerer Container, der wie ein Array von Zeigern auf Strukturen aussehen soll.Es ist ein Schwergewicht, selbst wenn wir Tricks wie Guy Gordon in diesem Thread anwenden (Index oder etwas anderes anstelle von Zeigern einfügen oder Werte direkt einfügen, wenn sie kleiner als 32 Bit sind):Wir müssen eine Liste erstellen und so weiter ...
Eine Alternative zum einfachen und schnellen Sortieren eines Arrays von Strukturen könnte daher die Verwendung von sein qsort C-Laufzeitfunktion von msvcrt.dll.
Hier ist eine Erklärung, die gut sein könnte (Warnung:Code (nur unter 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 Hier.
Beachten Sie, dass das direkte Sortieren des Datensatz-Arrays langsam sein kann, wenn die Datensätze groß sind.In diesem Fall kann das Sortieren eines Arrays mit Zeigern auf die Datensätze schneller sein (ähnlich wie beim Listenansatz).
Bei einem Array würde ich beides verwenden quicksort oder möglicherweise heapsort, und ändern Sie einfach den zu verwendenden Vergleich TExample.SortOrder, wird der Swap-Teil immer noch nur auf das Array und die Swap-Zeiger einwirken.Wenn das Array sehr groß ist, empfiehlt sich möglicherweise eine verknüpfte Listenstruktur, wenn häufig eingefügt und gelöscht wird.
C-basierte Routinen gibt es hier mehrerehttp://www.yendor.com/programming/sort/
Eine andere Seite, aber mit Pascal-Quellehttp://www.dcc.uchile.cl/~rbaeza/handbook/sort_a.html
Verwenden Sie einen der von vorgeschlagenen Sortieralgorithmen Wikipedia.Die Swap-Funktion sollte Array-Elemente unter Verwendung einer temporären Variablen desselben Typs wie die Array-Elemente austauschen.Verwenden Sie eine stabile Sortierung, wenn Sie möchten, dass Einträge mit demselben Ganzzahlwert „SortOrder“ in der Reihenfolge bleiben, in der sie ursprünglich waren.
TStringList verfügen über eine effiziente Sortiermethode.
Wenn Sie Sortieren möchten, verwenden Sie a TStringList Objekt mit Sorted Eigenschaft auf True.
NOTIZ:Für mehr Geschwindigkeit fügen Sie Objekte in einer nicht sortierten Reihenfolge hinzu TStringList und ändern Sie am Ende die Eigenschaft in True.
NOTIZ:Um nach Ganzzahlfeld zu sortieren, konvertieren Sie es in einen String.
NOTIZ:Wenn doppelte Werte vorhanden sind, ist diese Methode nicht gültig.
Grüße.
Wenn Sie Delphi XE2 oder neuer haben, können Sie Folgendes 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;
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;
