Tri rapide (non récursif) et tri de fusion

Nous savons que,Plus il y a de niveaux récursifs de tri rapide,Alors la pile pourrait déborder.Alors nous devons écrire un non récursif.

1. Tri rapide(Non récursif)

Comment changer la récursion en non - récursion？
Nous devons utiliser la pile de cette structure de données.
Regardons l'ensemble de données ci - dessous：

Tout d'abord,,Nous mettons l'indice du premier élément et l'indice du dernier élément dans la pile：

Et puis,On va9Sortez - le et mettez - leright,Oui.0Sortez - le et mettez - leleft- Oui., Et faire un tri unique .
C'est comme ça que ça se passe ：

Et puis,Nous allons6 Qu'en est - il de l'ordre des intervalles de gauche et de droite ？On va0Etkey-1En pile,Et ensuite,key+1Etn-1En pile.

Si on sort de la pile 9Mets - le.right,Oui.6 Sortez de la pile et mettez - la left, Encore un seul tour de tri .
C'est - à - dire6 Trier un seul passage dans la section droite de ：

Et puis,On va le refaire.9 La section gauche de la pile ,9 La section droite de la pile .
Parce que,9 Il n'y a qu'un seul nombre dans l'intervalle de droite qui n'a pas besoin d'être empilé , Dans la section gauche seulement .

Et puis,On va7 Sortez de la pile et mettez - la right- Oui.,Oui.6 Sortez de la pile et mettez - la left- Oui.. Encore un seul tour de tri ：

En ce moment,On va8 Pile à gauche et à droite de ,8 Il n'y a qu'une seule section gauche qui n'entre pas dans la pile ,8 La section droite de n'a pas et n'est pas empilée .En ce moment, Il y a encore 0Et4,C'est - à - dire6Section gauche de,C'est la même idée..
Code complet：

C'est la même chose., On peut aussi utiliser des files d'attente pour .

2. Ordre de fusion

2.1 L'idée de base

Le tri de fusion est un algorithme de tri efficace basé sur l'opération de fusion,Cet algorithme est une application très typique de la méthode de division et de traitement.Fusionner les sous - séquences ordonnées,Pour obtenir une séquence parfaitement ordonnée;C'est - à - dire que chaque sous - séquence est ordonnée en premier,Ensuite, l'ordre entre les sous - séquences.Si vous combinez deux tableaux en un seul tableau,Appelé fusion à deux voies. Fusionner et trier les étapes de base：

Démonstration de diagrammes mobiles：

2.2 Mise en œuvre concrète de la version récursive

En fait, nous décomposons la séquence en sous - problèmes qui ne peuvent pas être décomposés .C'est juste que1 Quand il n'y en a pas , On pourrait commencer à fusionner .
Nous allons ouvrir un tableau supplémentaire lors de la fusion , Parce que si vous fusionnez dans le tableau original , Il va passer outre les valeurs .
Tout d'abord,, Regardons le Code décomposé ：

QuandbeginEtendTous.0Heure,Je reviens, Et Récursivement à droite ,beginEtendTous.1Heure,Retour.En ce moment, On pourrait fusionner [0,0]Et[1,1] Deux valeurs d'intervalle . D'autres choses sont similaires .

Alors, Comment fusionner ：

Prenons par exemple cet ensemble de séquences ：
Tout d'abord,,Nous devons[0,0]Et[1,1]Fusionner, Est de comparer la taille , Les petits d'abord tmpDans le tableau,Et puis continuer à comparer. Quand la fusion sera terminée ,On vatmp Les données sont copiées dans le tableau original .

Voilà.[0,1] Les intervalles sont ordonnés , On va commencer à fusionner. [0,1]Et[2,2]

Voilà.[0,2]C'est l'ordre, Nous devons fusionner [3,3]Et[4,4]

Voilà.[0,2]Et[3,4] Tout est en ordre , Nous devons fusionner [0,2]Et[3,4]

De cette façon, la Section de gauche est ordonnée , C'est la même chose pour la section droite .
Le code complet est le suivant：

2.3 Version non récursive mise en oeuvre concrète

Tout d'abord,, Regardons cet ensemble de données ：

Si on revient , Besoin d'un retour ,10Et6Retour à,7Et1Retour à,3Et9Retour à,4Et2Retour à.
Alors nous pouvons définir gap Représente le nombre de personnes à fusionner .
QuandgapPour1Heure, C'est - à - dire un par un pour fusionner .

Et puis,On vagapPour2, C'est comme ça que les deux fusionnent .
C'est - à - dire[0,1]Et[2,3]Fusionner,[4,5]Et[6,7]Fusionner.

Puis il y a la fusion du 4 - 4 ,[0,3]Et[4,7]Fusionner.

D'ici,Nous pouvons voirgapDe1Devenir2Et ça devient4- Oui.2Doublement.
Alors on pourra d'abord contrôler gapC'est：

Et puis, Nous devons contrôler l'indice du tableau ,On peut définir uniPour contrôler, La première étape est l'indice 0Et indice1Fusionner, La deuxième étape est l'indice 2Et indice3Fusionner…C'est - à - direi=0,i=2,i=4…
Quand les deux fusionnent ,[0,1]Et[2,3],[4,5]Et[6,7],C'est - à - direi=0,i=4,i=8…
Alors nous pouvons contrôler l'indice ：

Y a - t - il un problème à écrire ainsi ？ Regardons les données ci - dessous ：

SigapPour2Heure, C'est - à - dire la fusion des deux .[0,1]Et[2,3]Fusionner,[4,5]Et[6,7]Fusionner,[8,9]Et[10,11]Fusionner,Mais[10,11]begin2Etend2J'ai dépassé les bornes.

QuandgapPour4Heure,C'est[0,3]Et[4,7]Fusionner,Et puis[8,11]Et[12,15]Fusionner.À ce moment - là,end1,begin,end2J'ai dépassé les bornes..

Alors nous devons réfléchir à la façon de résoudre ce problème transfrontalier .
D'après l'analyse ci - dessus, nous pouvons conclure que ,end1,begin2,end2 Peut franchir la ligne . Donc ces trois - là sont hors de portée et nous avons tous besoin de contrôle .
Il y a trois situations ：
Dans le premier cas：end1Pas trop loin.,begin2Pas trop loin.,end2Hors de portée.Donc siend2>=nHeure,On vaend2Assigner àn-1

Dans le deuxième cas：end1Pas trop loin.,begin2Hors de portée,end2Hors de portée. Alors le second intervalle n'existe pas , On va faire du second intervalle un intervalle inexistant

Le troisième scénario：end1Hors de portée,Alorsbegin2,end2 J'ai dû franchir la ligne .Alors nous devons mettreend1Assigner àn-1,begin2Etend2 Suivez les modifications ci - dessus .

Cela permet de contrôler les problèmes de limite non récursifs .Le code complet est le suivant：

2.4 Analyse de la complexité

2.4.1 Complexité temporelle

Parlons d'abord de la complexité temporelle .

Le tri de fusion est divisé en décomposition et fusion . Tout d'abord, nous pouvons voir que c'est quadratiquement équidistant à chaque fois .TotalnNombre,Deux points à chaque fois,C'est - à - dire2^x=n,x=logn.Alors..., Décomposition oui lognCouche.

La fusion est en fait similaire à la décomposition , Mais la fusion nécessite un tri , C'est - à - dire que chaque fusion passe par n,Et puis il y alognCouche,C'est - à - diren*logn.

Donc la complexité temporelle estlogn+nlogn,En grosOLa représentation asymptotique deO(nlogn).

2.4.2 Complexité spatiale

La complexité spatiale est simple , Nous pouvons voir qu'il a besoin d'une ouverture supplémentaire nEspace pour les données. Et ensuite nous allons voir sa profondeur récursive , On peut voir qu'il y a Récursivement lognCouche, L'espace dans chaque récursion est un nombre constant ,C'est - à - direO(1),Alors..., La complexité spatiale est n+logn,Encore parce quenBeaucoup plus grand quelogn,Donc la complexité spatiale estO(N).

2.5 Tri externe du tri de fusion

Parmi ces algorithmes courants de tri dont nous parlons , Peut réaliser le tri interne . Qu'est - ce que le tri interne ？
Tri interne： C'est que les données sont en mémoire .Index accès aléatoire,Vite!.
Mais, Seul le tri de fusion peut faire le tri externe .
Qu'est - ce qu'un tri externe ？
Tri externe：Trop d'éléments de données à mettre en mémoire en même temps, Et sur le disque ,Accès série,Lent..

Il y a un problème：
10 Un milliard de fichiers entiers ,C'est tout.1GMémoire de fonctionnement pour, S'il vous plaît 10Des centaines de millions en ordre.
Comment résoudre ce problème ？
Tout d'abord,,Nous devons savoir10 Combien de mémoire Avons - nous besoin d'un milliard d'entiers ？
1G=1024MB,1024MB=10241024KB,1024KB=10241024*1024byte
Alors...1GC'est à peu près égal à10Gigaoctet.Alors10 Un milliard d'entiers est 40Gigaoctet,Presque.4G.
Solutions：Diviser le fichier en4Partage égal,Chaque1G, Trier en mémoire séparément ,Fin de la séquence, Écrivez à nouveau sur le petit fichier disque . Et ensuite, il est fusionné sur le disque .