Modo migliore per ordinare un array
https://stackoverflow.com/questions/41733
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Dire che ho un array di record che voglio ordinamento basato su uno dei campi del record.Qual è il modo migliore per raggiungere questo obiettivo?
TExample = record
SortOrder : integer;
SomethingElse : string;
end;
var SomeVar : array of TExample;
Soluzione
È possibile aggiungere i puntatori agli elementi dell'array a una TList, quindi chiamare TList.Sort con una funzione di confronto, e, infine, creare un nuovo array e copiare i valori di TList nell'ordine desiderato.
Tuttavia, se si sta utilizzando la versione successiva, D2009, c'è una nuova collezioni di una biblioteca, che può ordinare gli array.Ci vuole un optional IComparer<TExample> attuazione per l'ordinamento personalizzato ordini.Qui è in azione per il tuo caso specifico:
TArray.Sort<TExample>(SomeVar , TDelegatedComparer<TExample>.Construct(
function(const Left, Right: TExample): Integer
begin
Result := TComparer<Integer>.Default.Compare(Left.SortOrder, Right.SortOrder);
end));
Altri suggerimenti
(So che questo è un anno più tardi, ma ancora in utile.)
Skamradt suggerimento per pad valori interi si presuppone che si sta andando a ordinare utilizzando una stringa confrontare.Questo potrebbe essere lento.Chiama format() per ogni inserimento, ancora più bassa.Invece, si vuole fare un intero confrontare.
Si inizia con un tipo di record:
TExample = record
SortOrder : integer;
SomethingElse : string;
end;
Non stato come i record sono stati memorizzati, o come si voleva accedere loro una volta che ordinate.Quindi partiamo da li metti in un Array Dinamico:
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;
Ora si desidera ordinare l'array con il valore intero Ordinamento.Se quello che vuoi è una TStringList (in modo da poter utilizzare il ts.Metodo di ricerca), allora si dovrebbe aggiungere ogni stringa elenco e aggiungere l'Ordinamento alfabetico, come un puntatore.Quindi ordinare il puntatore:
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;
Nota il trucco di colata, l'Intero Ordinamento alfabetico in un TObject puntatore, che è memorizzato nel TStringList.Proprietà dell'oggetto.(Questo dipende dal fatto che Interi e Puntatore sono della stessa dimensione.) Da qualche parte si deve definire una funzione per confrontare il TObject puntatori:
function CompareObjects(ts:tStringList; Item1,Item2: integer): Integer;
var i,j: integer;
begin
Result := integer(ts.Objects[i]) - integer(ts.Objects[j];
end;
Ora, siamo in grado di ordinare il tsList su .Oggetto chiamando .CustomSort invece di .Sort (che sarebbe sorta sul valore stringa.)
tsExample.CustomSort(@CompareObjects); //Sort the list
Il TStringList è ora ordinato, in modo che si può scorrere su di esso da 0 a .Count-1 e leggere le stringhe in modo ordinato.
Ma supponiamo che non vuoi una TStringList, solo un array ordinato.O il record di contenere più dati di quelli che solo una stringa in questo esempio, e il vostro ordine è più complesso.È possibile saltare la fase di aggiunta di ogni stringa, e aggiungere solo l'indice di un array come Elementi di una TList.Fare tutto allo stesso modo, con l'eccezione di usare una TList invece di 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;
Ora che Mlist è ordinato, usarlo come una tabella di ricerca per accedere all'array ordinato:
for i:=0 to Mlist.Count-1 do begin
Something := MyDA[integer(Mlist[i])].SomeField;
end;
Come ho scorre il TList, si ottiene la matrice di indici ordinati.Abbiamo solo bisogno di gettare di nuovo a numeri interi, poiché TList pensa di puntatori.
Mi piace farlo in questo modo, ma si potrebbe anche mettere reale puntatori agli elementi di un array TList aggiungendo l'Indirizzo dell'elemento di matrice invece è indice.Poi loro utilizzo si sarebbe gettato come puntatori a TExample record.Questo è ciò che Barry Kelly e CoolMagic ha detto di farlo nelle loro risposte.
Se la vostra necessità ordinati per stringa, utilizzare ordinati TStringList e
aggiungere record TString.AddObject(string, Pointer(int_val)).
Ma, Se necessario, ordina per intero campo e di stringa - utilizzare TObjectList e dopo l'aggiunta di tutti i record di chiamata TObjectList.Sort con servizi ordinati funzioni come parametro.
Tutto questo dipende dal numero di record che si sta ordinando.Se solo l'ordinamento di meno di un paio di centinaia di allora l'ordinamento di altri metodi di funzionare bene, se avete intenzione di essere in ordinamento di più, quindi prendere una buona occhiata al vecchio fidato Turbo Potenza SysTools progetto.C'è un ottimo algoritmo di ordinamento incluso nel sorgente.Uno che fa un ottimo lavoro di ordinamento milioni di record in un modo efficiente.
Se avete intenzione di utilizzare il tStringList metodo di ordinamento di un elenco di record, assicurarsi che il vostro intero imbottito, a destra prima di inserirlo in lista.È possibile utilizzare il format('%.10d',[rec.ordinamento]) per allineare a destra di 10 cifre, per esempio.
L'algoritmo quicksort è spesso utilizzato quando il fast ordinamento, è necessario.Delphi è (O era) utilizzando per la Lista.Ordina per esempio.Delphi Elenco può essere utilizzato per ordinare nulla, ma è uno dei pesi massimi del contenitore, che si suppone a guardare come un array di puntatori a strutture.È pesante, anche se usiamo trucchi come il Ragazzo Gordon in questo thread (Mettendo indice o di qualsiasi altro luogo di puntatori, o mettere direttamente i valori, se sono di dimensioni inferiori a 32 bit):abbiamo bisogno di costruire una lista, e così via...
Di conseguenza, un'alternativa facilmente e velocemente ordinare un array di struct potrebbe essere qsort funzione di runtime C da msvcrt.dll.
Qui è una dichiarazione che potrebbe essere un bene (Attenzione:codice portatile solo per windows).
type TComparatorFunction = function(lpItem1: Pointer; lpItem2: Pointer): Integer; cdecl;
procedure qsort(base: Pointer; num: Cardinal; size: Cardinal; lpComparatorFunction: TComparatorFunction) cdecl; external 'msvcrt.dll';
Esempio completo qui.
Si noti che direttamente ordinamento di array di record può essere lento se i record sono grandi.In questo caso, l'ordinamento di un array di puntatore al record può essere più veloce (un po ' come approccio).
Con un array, mi piacerebbe utilizzare quicksort o forse heapsort, e basta cambiare il confronto per l'uso TExample.SortOrder, la swap è ancora andando ad agire su una matrice di swap e puntatori.Se l'array è molto grande, si potrebbe voler un elenco collegato struttura se c'è un sacco di inserimento e cancellazione.
C a base di routine, ci sono diversi qui http://www.yendor.com/programming/sort/
Un altro sito, ma è in pascal http://www.dcc.uchile.cl/~rbaeza/handbook/sort_a.html
Utilizzare uno del genere alorithms proporre, entro il Wikipedia.La funzione di scambio di swap di elementi di un array utilizzando una variabile temporanea dello stesso tipo, come gli elementi della matrice.Utilizzare uno stabile ordinamento se vuoi che le voci con lo stesso Ordinamento alfabetico valore intero per rimanere nell'ordine in cui sono state in primo luogo.
TStringList dispongono di un efficiente Metodo di Ordinamento.
Se si desidera utilizzare una Sorta TStringList oggetto Sorted proprietà a True.
NOTA:Per di più la velocità, aggiungere gli oggetti in un non Ordinati TStringList e alla fine cambiare la proprietà su True.
NOTA:Per ordinare dal Campo intero, la conversione di Stringa.
NOTA:Se ci sono valori duplicati, questo metodo non è Valido.
Per quanto riguarda.
Se si dispone di Delphi XE2 o più recente, si può provare:
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;
Ho creato un esempio molto semplice che funziona correttamente se il tipo di campo è una stringa.
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;
