La meilleure façon de trier un tableau
Dire que j'ai un tableau d'enregistrements qui je veux de tri basé sur l'un des champs de l'enregistrement. Quelle est la meilleure façon d'atteindre cet objectif?
TExample = record
SortOrder : integer;
SomethingElse : string;
end;
var SomeVar : array of TExample;
- Juste allé à travers cet exercice, et trouve la meilleure façon est d'écrire mon propre code. Je ne crois pas que les réponses doivent être recommandée comme meilleur.
- Point de pris. Vous pourriez peut-être ajouter une réponse avec votre solution au problème?
- Il y a quelques bonnes informations dans des Tomes de Delphi Algorithmes et Structures de Données par Julian Bucknall. (s
- Il y a quelques bonnes informations dans des Tomes de Delphi Algorithmes et Structures de Données. (Ici, entre autres: blog.boyet.com/blog/blog/...)
Vous devez vous connecter pour publier un commentaire.
Vous pouvez ajouter des liens vers les éléments de la matrice à une
TList
, puis d'appelerTList.Sort
avec une fonction de comparaison, et finalement de créer un nouveau tableau et de copier les valeurs de la TList dans l'ordre souhaité.Toutefois, si vous utilisez la version suivante, D2009, il y a une nouvelle collections de la bibliothèque qui peut trier des tableaux. Il prend une option
IComparer<TExample>
mise en œuvre pour un tri personnalisé des commandes. Ici, il est en action pour votre cas spécifique:(Je sais que c'est un an plus tard, mais toujours utiles genre de choses.)
Skamradt la suggestion de pad valeurs entières suppose que vous allez trier à l'aide d'une comparaison de chaîne. Ce serait lente. L'appel de format() pour chaque insertion, plus lente encore. Au lieu de cela, vous voulez faire une comparaison d'entiers.
Vous commencez avec un type d'enregistrement:
Vous n'avez pas l'état de la façon dont les enregistrements ont été conservés, ou comment vous avez voulu y accéder une fois triés. Supposons donc que vous les mettez dans un Tableau Dynamique:
Maintenant, vous voulez trier ce tableau par la valeur de l'entier SortOrder. Si ce que vous voulez est un TStringList (de sorte que vous pouvez utiliser le ts.Trouver la méthode), alors vous devez ajouter chaque chaîne à la liste et ajouter les SortOrder comme un pointeur. Faire le tri sur le pointeur:
Note l'astuce de la coulée de l'Entier SortOrder dans un TObject pointeur, qui est stocké dans la TStringList.Propriété de l'objet. (Cela dépend du fait que les Entier et la souris sont de la même taille.) Quelque part, nous devons définir une fonction pour comparer les TObject pointeurs:
Maintenant, nous pouvons trier les tsList sur .Objet en l'appelant .CustomSort au lieu de .De tri (ce qui serait un tri sur la chaîne de valeur.)
La TStringList est maintenant triée, de sorte que vous pouvez parcourir à partir de 0 de .Count-1 et lire les chaînes dans l'ordre de tri.
Mais supposons que vous ne voulez pas un TStringList, juste un tableau dans l'ordre de tri. Ou les enregistrements contiennent plus de données que juste une chaîne de caractères dans cet exemple, et l'ordre de tri est plus complexe. Vous pouvez ignorer l'étape de l'ajout de chaque chaîne, et il suffit d'ajouter les index de tableau comme les Éléments d'une TList. Tout faire au-dessus de la même façon, à l'exception de l'utilisation d'une TList au lieu de TStringList:
Maintenant que Mlist est triée, l'utiliser comme une table de recherche pour accéder au tableau dans l'ordre de tri:
Que je parcourt la TList, on obtient les indices de tableau dans l'ordre de tri. Nous avons juste besoin de les jeter en arrière pour les entiers, depuis le TList pense qu'ils sont des pointeurs.
J'aime le faire de cette façon, mais vous pouvez aussi mettre des pointeurs vers des éléments de tableau dans la TList par l'ajout de l'Adresse de l'élément du tableau à la place de son index. Ensuite pour les utiliser vous jeter comme des pointeurs vers TExample enregistrements. C'est ce que Barry Kelly et CoolMagic dit de le faire dans leurs réponses.
Si votre besoin de trier par chaîne utilisez ensuite triés
TStringList
etajouter un enregistrement par
TString.AddObject(string, Pointer(int_val))
.Mais Si besoin de trier par champ de type entier et chaîne - utiliser
TObjectList
et après l'ajout de tous les enregistrements d'appelsTObjectList.Sort
nécessaires triés fonctions en paramètre.Tout cela dépend du nombre de dossiers à trier. Si vous êtes seulement de tri à moins de quelques centaines de puis de l'autre de tri des méthodes de travail de l'amende, si vous allez être en tri plus, puis prendre un bon coup d'oeil à l'ancien fidèle de la Puissance Turbo SysTools projet. Il y a un très bon algorithme de tri dans la source. Celui qui fait un très bon travail de tri des millions d'enregistrements dans une manière efficace.
Si vous allez utiliser la tStringList méthode de tri d'une liste de documents, assurez-vous que votre entier est rembourré pour le droit avant de l'insérer dans la liste. Vous pouvez utiliser le format('%.10d',[rec.l'ordre de tri]) pour aligner à droite à 10 chiffres par exemple.
L'algorithme quicksort est souvent utilisé lorsque le tri rapide est nécessaire. Delphi est (Ou était) en l'utilisant pour la Liste.Tri par exemple.
Delphi Liste peut être utilisée pour le tri de rien, mais c'est un poids lourd de conteneur, qui est censé ressembler à un tableau de pointeurs sur les structures. C'est lourd, même si nous utilisons des trucs comme Guy Gordon dans ce fil (en Mettant l'indice ou quoi que ce soit à la place des pointeurs, ou en mettant directement les valeurs si elles sont plus petites que 32 bits): nous avons besoin de construire une liste et ainsi de suite...
Par conséquent, une alternative à facilement et rapidement le tri d'un tableau de struct pourrait être d'utiliser qsort runtime C de la fonction de msvcrt.dll.
Voici une déclaration qui pourrait être bon (Avertissement: code portable sur windows uniquement).
Exemple complet ici.
Avis que directement de tri le tableau d'enregistrements peut être lent si les enregistrements sont de grande taille. Dans ce cas, le tri d'un tableau de pointeur sur les registres peut être plus rapide (un peu comme la Liste).
Avec un tableau, je ne l'utiliserais soit
quicksort
ou éventuellementheapsort
, et il suffit de changer le rapport à l'utilisationTExample.SortOrder
, le swap partie est toujours en cours à la juste loi sur le tableau et le swap de pointeurs. Si le tableau est très grand, alors vous voudrez peut-être une liste liée à la structure si il y a beaucoup d'insertion et de suppression.C en fonction des routines, il y a plusieurs ici
http://www.yendor.com/programming/sort/
Un autre site, mais a pascal source
http://www.dcc.uchile.cl/~rbaeza/handbook/sort_a.html
Utiliser une alorithms proposer par Wikipédia. La fonction de permutation devraient échanger des éléments d'un tableau à l'aide d'une variable temporaire du même type que les éléments du tableau. Utiliser un tri stable si vous voulez entrées avec le même ordre de tri de valeur entière séjour dans l'ordre où ils ont été en premier lieu.
TStringList
ont efficace Méthode de Tri.Si vous voulez Trier utiliser un
TStringList
objet avecSorted
True à la propriété.REMARQUE: Pour plus de vitesse, ajouter des objets dans un pas Triés
TStringList
et à la fin du changement de la propriété à True.REMARQUE: Pour que le tri par Champ de type entier, de les convertir en Chaîne de caractères.
REMARQUE: Si il y a des valeurs en double, cette méthode n'est pas Valide.
Ce qui concerne.
Si vous avez Delphi XE2 ou plus récent, vous pouvez essayer:
J'ai créé un exemple très simple qui fonctionne correctement que si le champ de tri est une chaîne de caractères.