-1
Quel est le meilleur algorithme pour trier une liste de liens [en C/C++]?Quelle est la meilleure façon de trier la liste de liens?
A
Répondre
6
Mieux encore, il suffit d'utiliser std::list et sa méthode sort().
+1
Souhaitez-vous expliquer la raison du tri de la fusion?Merci de suggérer STL, mais je ne peux pas l'utiliser car c'est le devoir –
+1
@Cory: des trois algorithmes courants (heapsort, quicksort, mergesort) c'est le seul qui fonctionne bien sans accès aléatoire – Christoph
11
Le tri par fusion convient au tri des listes liées. Quelques détails here. Exemple de code C here.
Pourquoi est-ce approprié? Eh bien, pour simplifier, le composant principal de mergesort - la fusion de sous-séquences triées - peut être facilement fait sur deux listes chaînées, car tout ce dont il a besoin est de comparer les éléments principaux, il n'a donc pas besoin d'un accès aléatoire.
En outre, voici un article nommé A COMPARATIVE STUDY OF LINKED LIST SORTING ALGORITHMS que vous pouvez trouver intéressant.
+0
Je ne sais pas pourquoi les gens continuent lien vers ce site - la mise en œuvre craint car elle est trop compliquée et traverse inutilement la liste; l'algorithme utilisé est équivalent à la version itérative basée sur les tableaux - qui n'est pas adaptée aux listes chaînées car celles-ci ne permettent pas l'accès aléatoire - et devrait être remplacée par une implémentation basée sur une pile; même la vanille récursive devrait mieux fonctionner – Christoph
1
Dépend de ce que vous entendez par "meilleur". Voulez-vous dire le plus rapide à implémenter, ou le plus efficace? La taille et les caractéristiques de ce que vous triez jouent également un rôle. Le tri de 10 éléments par rapport au tri de 10 millions d'éléments conduira probablement à un algorithme "meilleur" différent. Pour les grands ensembles de données où «meilleur» signifie l'exécution la plus rapide, j'aime le tri rapide.
+0
Je pense que je me souviens avoir entendu que quicksort fonctionne lentement sur des données triées (ou presque triées). Ainsi, comme l'a dit bpv, les caractéristiques des données joueraient en effet un grand rôle dans votre décision. – ialm
+1
@veol: Un quicksort naïf fonctionne lentement, la plupart des implémentations pratiques utilisent un pivotement aléatoire. – MAK
+0
@MAK: Il semble que je ne faisais pas attention en classe à nouveau :) – ialm
1
Une implémentation de mergesort basée sur une pile est l'arme de choix.
Il y a quelque temps, j'avais besoin de trier une liste doublement liée. Wikipédia m'a dit d'utiliser Mergesort car c'est le seul des trois algorithmes communs de tri général (heapsort, mergesort et quicksort) qui fonctionne bien quand l'accès aléatoire est lent et fournit même un lien vers Simon Tatham's implementation.
D'abord, je re-implemented son algorithme, qui a montré qu'il était fondamentalement la version itérative bien connue. C'est un mauvais choix car il repose sur un accès aléatoire et fonctionne donc mal.
Le recursive version est mieux adapté pour les listes chaînées car il ne parcourt inutilement l'une des listes lors de la division et non les deux (comme le fait la variante de Simon).
Ce que vous devez utiliser est un stack-based version car cette implémentation est entièrement débarrassée des traversées de liste inutiles.
0
Cela vaut la peine de réfléchir à la façon dont vous êtes arrivé à ce point. Si vous avez besoin de trier vos articles d'une manière particulière, pensez à garder la liste triée et à les insérer directement dans la liste triée. De cette façon, vous n'avez pas à le trier quand vous en avez besoin.
Questions connexes
- 1. Quelle est la meilleure façon de trier par date?
- 2. Quelle est la meilleure façon de trier une liste partiellement ordonnée?
- 3. La meilleure façon de trier NSMutableArray?
- 4. Quelle est la meilleure façon de trier une table de données dans ADO.NET
- 5. Quelle est la meilleure façon de trier un IList <T> dans .Net 2.0?
- 6. Quelle est la meilleure façon de trier les éléments sur l'un des éléments valeurs
- 7. Meilleure façon de trier une liste de mots par apparition
- 8. Quelle est la meilleure façon d'apprendre WCF?
- 9. Quelle est la meilleure façon d'exécuter `sum_by_sql`?
- 10. Quelle est la meilleure façon d'implémenter hashCode()?
- 11. Quelle est la meilleure façon d'apprendre CUDA?
- 12. Quelle est la meilleure façon de charger la balance? PHP
- 13. Quelle est la meilleure façon de détecter la couleur blanche?
- 14. Quelle est la meilleure façon d'automatiser le remplacement de texte?
- 15. quelle est la meilleure façon de modifier le fichier csv
- 16. Quelle est la meilleure façon de localiser un IEnumerable?
- 17. Meilleure façon de trier une longue liste de chaînes
- 18. Quelle est la meilleure façon de faire ce programme Java?
- 19. Quelle est la meilleure façon de faire XMLObject Validation
- 20. Quelle est la meilleure façon de trouver l'inverse de datetime.isocalendar()?
- 21. Quelle est la meilleure façon de sel mot de passe?
- 22. Migration de données: Quelle est la meilleure façon de migrer?
- 23. Quelle est la meilleure façon de récupérer ces données?
- 24. Quelle est la meilleure façon de lire les données CSV?
- 25. quelle est la meilleure façon de créer un menu javascript?
- 26. Quelle est la meilleure façon de gérer les images cassées?
- 27. Quelle est la meilleure façon de filer des tweets?
- 28. Quelle est la meilleure façon de tester les réponses XML?
- 29. Quelle est la meilleure façon de gérer les chaînes temporaires?
- 30. Quelle est la meilleure façon d'instancier de nombreux objets JavaScript?
Vous devrez peut-être spécifier quelle langue vous voulez (C ou C++) puisque les solutions seront très différentes. –
Peut-être que John peut vous aider: http://stackoverflow.com/questions/1733420/where-can-i-get-cc-sample-code-for-merge-sort-a-link-list –
Ceci est un doublon de http://stackoverflow.com/questions/1525117/whats-the-fastest-algorithm-for-sorting-a-linked-list –