编程知识 cdmana.com

Diagramme d'algorithme 2 - tri de sélection

Table des matières

2.,Sélectionner le tri

2.1Comment fonctionne la mémoire

2.2Tableaux et listes de liens

2.2.1Liste des liens

2.2.2Tableau

2.2.3Terminologie

2.2.4Insérer au milieu

2.2.5Supprimer

2.3Sélectionner le tri

2.3.1Illustration

2.3.2Code

2.4Résumé


2.,Sélectionner le tri

2.1Comment fonctionne la mémoire

Si vous voulez voir un spectacle, , Dépôt requis . Il y a beaucoup de casiers au dépôt. , Il y a beaucoup de tiroirs dans le placard. .

Chaque tiroir peut contenir une chose,Tu as deux, Deux tiroirs. .

Tu mets tes affaires ici. .

La mémoire de l'ordinateur fonctionne de la même façon,Les ordinateurs sont comme une collection de tiroirs, Chaque tiroir a une adresse .


2.2Tableaux et listes de liens

Parfois...,Une série d'éléments doit être stockée en mémoire.Supposons que vous écriviez un programme pour gérer vos tâches,Pour ce faire, gardez ces choses en mémoire,Utilisez - vous un tableau ou une liste liée?

Supposons que vous vouliez ajouter un quatrième article maintenant,Mais le tiroir arrière contient les affaires de quelqu'un d'autre.

 

C'est comme aller au cinéma avec un ami,J'ai trouvé un endroit où m'asseoir et un autre ami est venu,Mais il n'y a pas de place libre où s'asseoir,Je dois trouver un autre endroit où tout le monde peut s'asseoir.Dans ce cas,,Vous devez demander à l'ordinateur de réattribuer un bloc qui peut contenir4 Mémoire pour les tâches ,Déplacer toutes les choses à faire là - Bas.
Si un autre ami arrive, ,Et il n'y a pas de place disponible pour le moment, Vous devrez vous déplacer à nouveau. ! C'est très gênant. .Encore une fois,Ajouter de nouveaux éléments à un tableau peut également être difficile. S'il n'y a pas d'espace ,Il faut aller ailleurs dans la mémoire,Ainsi, l'ajout de nouveaux éléments sera lent. Une solution est “ Sièges réservés ”: Même si seulement 3À faire, Veuillez également demander à l'ordinateur de fournir 10Position,Au cas où vous auriez besoin d'ajouter une note.Voilà., Tant que la liste des tâches ne dépasse pas 10- Oui., Il n'y a pas de transfert. .C'est une bonne mesure de contingence, Mais tu devrais comprendre. , Il présente deux inconvénients: .
1,L'emplacement de votre demande supplémentaire pourrait ne pas fonctionner du tout, Cela gaspillera la mémoire .Tu n'as pas utilisé, Personne d'autre ne peut l'utiliser. .
2, À faire plus que 10 Derrière. , Tu dois encore te déplacer. .

Donc,,Ce genre d'expédient, bien que bon,Mais ce n'est pas la solution parfaite.Pour cette question, Peut être résolu à l'aide d'une liste de liens .

2.2.1Liste des liens

.Chaque élément de la liste contient l'adresse de l'élément suivant,De sorte qu'une série d'adresses de mémoire aléatoires sont groupées.

C'est comme une chasse au trésor. . Vous allez à la première adresse , Il y a un mot qui dit: “L'adresse de l'élément suivant est123".Donc,, Vous allez à l'adresse 123, Il y a un autre mot. ,C'est écrit:“L'adresse de l'élément suivant est847",Et ainsi de suite..Il est facile d'ajouter des éléments à la liste: Il suffit de le mettre en mémoire ,Et stocke son adresse dans l'élément précédent.
Lors de l'utilisation d'une liste de liens ,Il n'est pas nécessaire de déplacer les éléments du tout.Cela évite également un autre problème.Supposons que vous alliez voir un film passionnant avec cinq amis.Vous voulez vous asseoir ensemble, Mais plus de gens regardent des films ,Il n'y a pas six sièges ensemble.Cela arrive parfois lors de l'utilisation d'un tableau.Supposons que vous vouliez assigner un tableau1000Emplacement, En mémoire 10 000Position, Mais pas tous ensemble. .Dans ce cas,,Vous ne pourrez pas allouer de mémoire à ce tableau! Une liste de liens équivaut à dire “ On va s'asseoir séparément. ”,Donc, tant qu'il y a assez de mémoire, Peut allouer de la mémoire à une liste liée .

2.2.2Tableau

Avantages de la liste liée en termes d'insertion d'éléments,Quel est l'avantage du tableau?

Les sites de classement utilisent des moyens mesquins pour augmenter le nombre de pages vues.Ils n'affichent pas le classement complet en une seule page,Et mettre chaque élément du classement sur une page, Et vous permet de cliquer Next Pour voir ce qui suit .Par exemple, Quand il y a dix grands méchants ,Ne pas afficher le classement complet en une seule page,Mais d'abord montrer le dixième méchant( Newman),Vous devez cliquer surNext, Pour voir le premier méchant (Gustavo Fring). Cela permet au site Web de 10 Annonces affichées sur les pages , Mais l'utilisateur doit cliquer sur NextNeuf fois pour voir le premier, C'est vraiment ennuyeux. .Si tout le classement est affiché sur une seule page, Ce sera beaucoup plus pratique. .Voilà.,.L'utilisateur peut cliquer sur le nom de la personne dans le classement pour obtenir des informations plus détaillées.

La liste des liens a des problèmes similaires .Quand il faut lire le dernier élément de la liste, Vous ne pouvez pas lire directement ,Parce que vous ne savez pas où il est, L'élément doit être accédé en premier #1, Obtenir des éléments à partir de #2Adresse, Élément de ré - accès #2 Et obtenir des éléments #3Adresse,Et ainsi de suite.,Jusqu'à ce que vous accédez au dernier élément.Quand tous les éléments doivent être lus en même temps, La liste est très efficace : Vous lisez le premier élément ,Lisez le premier élément en fonction de son adresse,Et ainsi de suite.. Mais si vous avez besoin de sauter , La liste est vraiment inefficace .

Le tableau est différent :Vous connaissez l'adresse de chacun de ces éléments.Par exemple,Supposons qu'il y ait un tableau, Il contient cinq éléments ,L'adresse de départ est00,Alors, quelle est l'adresse de l'élément?

Il suffit d'effectuer des opérations mathématiques simples pour savoir;04.Lorsqu'un élément doit être lu au hasard, Le tableau est très efficace ,Parce que tout élément du tableau peut être trouvé en arrière. Dans la liste des liens , La corde n'est pas liée. ,Vous ne pouvez pas calculer rapidement l'adresse mémoire du cinquième élément,Vous devez d'abord accéder au premier élément pour obtenir l'adresse du deuxième élément,Accédez à nouveau au deuxième élément pour obtenir l'adresse du troisième élément,Et ainsi de suite., Jusqu'au cinquième yuan. .

2.2.3Terminologie

Élément de tableau numéroté , Le numéro est de 0C'est parti.,Par exemple, Dans le tableau ci - dessous ,Élément20 Est situé à 1.

Temps d'exécution des opérations du tableau et de la liste de liens énumérées ci - dessous.

2.2.4Insérer au milieu

Élément à insérer au milieu ,Lequel des tableaux et des listes liées est le meilleur? Lors de l'utilisation d'une liste de liens , Insérer un élément est simple ,Il suffit de modifier l'adresse à laquelle l'élément précédent pointe.

Lors de l'utilisation d'un tableau ,L'élément suivant doit être déplacé vers l'arrière.

S'il n'y a pas assez d'espace,Peut également faire copier le tableau entier ailleurs.

2.2.5Supprimer

Et si vous supprimez un élément ? Les listes de liens sont aussi de meilleurs choix ,.Parce qu'il suffit de modifier l'adresse à laquelle l'élément précédent pointe. Lorsque vous utilisez un tableau , Après suppression de l'élément ,Les éléments suivants doivent être déplacés vers l'avant.
Différent de l'insertion , Supprimer les éléments réussit toujours .S'il n'y a pas assez d'espace en mémoire, L'opération d'insertion peut échouer ,Mais l'élément peut être supprimé dans tous les cas.
Voici le temps d'exécution des opérations courantes de tableau et de liste liée.

Il faut souligner que,Seulement si l'élément à supprimer est immédiatement accessible,Le temps d'exécution de l'opération de suppression est O(1).Habituellement, nous enregistrons le premier et le dernier élément de la liste liée,Par conséquent, le temps d'exécution de la suppression de ces métalignes estO(1).Lequel des tableaux et des listes de liens utilise le plus? Ça dépend. . Mais les tableaux sont très utilisés , Parce qu'il supporte l'accès aléatoire .Il y a deux façons d'y accéder: Accès aléatoire et séquentiel .L'accès séquentiel consiste à lire les éléments un par un à partir du premier élément. La liste des liens ne peut être consultée que dans le sens des aiguilles d'une montre. :Pour lire le dixième élément de la liste liée, Les neuf premiers éléments doivent être lus en premier ,Et suivez le lien pour trouver le dixième élément.L'accès aléatoire signifie que vous pouvez passer directement au dixième élément.On dit souvent que les tableaux sont lus plus rapidement,C'est parce qu'ils seront accessibles au hasard.Beaucoup de situations exigent un accès aléatoire, Donc le tableau est beaucoup plus .


2.3Sélectionner le tri

2.3.1Illustration

Supposons qu'il y ait beaucoup de chansons dans vos calculs, Pour chaque chanson ,Vous enregistrez tous leurs temps de diffusion.

Vous voulez trier cette liste par le nombre de lectures de plus ou moins, Comment faites - vous? ?

Une façon de traverser cette liste,Découvrez les chansons les plus jouées à ajouter à une nouvelle liste.

Continue comme ça. ,Trouver le deuxième.

Et nous avons finalement obtenu le résultat que nous voulions.

Du point de vue de l'informatique, Voyez combien de temps ça prendra. .

Pour trouver la chanson la plus jouée,Chaque élément de la liste doit être vérifié,Ça prendra du temps.O(n).Pour ce type d'opération, vous devez effectuernUne fois.

                                            Moins d'éléments à vérifier

Au fur et à mesure que le tri progresse ,Le nombre d'éléments à vérifier à chaque fois diminue progressivement, Il n'y a qu'un seul élément à vérifier pour la dernière fois.Dans ce cas,, Quand est - ce qu'il fonctionne?  O (n^2)Et alors?? C'est une bonne question. , C'est avec big O Corrélation constante en notation . Les détails seront expliqués plus loin. , C'est une simple remarque. .Tu as raison.,Il n'est pas toujours nécessaire de vérifier les éléments. Première inspection requise  n Éléments,Mais ensuite, l'enseignement élémentaire de l'enfant estn-l,n-2…, 2Et1.Le nombre moyen d'éléments par inspection est de1 / 2 *(n+1), Donc le temps d'exécution est le même O(  n *1 / 2 *(n+1))Mais grand O  La notation omet des éléments tels que: 1/2 Ces constantes , Donc écrivez simplement  O(n × n ).

2.3.2Code

Sélectionner le tri( Selection sort)Est un algorithme de tri simple et intuitif.Il fonctionne en choisissant le plus petit des éléments de données à trier à chaque fois(Ou Max.)Un élément de,L'ordre est placé à la fin d'une séquence ordonnée,Jusqu'à ce que tous les éléments de données à trier soient alignés.

1,Sélectionnez d'abord le plus petit1Données, Et la somme de 1 Échange de données pour les emplacements .

2, Et le reste n-1Sélectionnez la plus petite des données1Éléments, Et 2L'échange de données entre les emplacements et.

3,Ça se répète,Jusqu'à ce que les deux dernières données soient échangées.Enfin,Et j'ai fini de trier le tableau original de petit à grand.

#include<stdio.h>

void SelectSort(int a[],int n)
{
    int i,j,temp,min;
    for(i=0;i<n-1;i++)
    {
        min=i;
        for(j=i+1;j<n;j++)    // Trouver l'emplacement du plus petit élément 
            while(a[j]<a[min])
                min=j;
        if(min!=i)
        {
            temp=a[min];     // Échange d'éléments 
            a[min]=a[i];
            a[i]=temp;
        }
    }
}

void main()
{
    int a[10],i;
    printf("please input 10 numbers:\n");
    for(i=0;i<10;i++)
        scanf("%d",&a[i]);
    printf("The array is:\n");
    for(i=0;i<10;i++)
        printf("%-4d",a[i]);
    SelectSort(a,10);
    printf("\nAfter sort the array is:\n");
    for(i=0;i<10;i++)
        printf("%-4d",a[i]);
    printf("\n");
}


2.4Résumé

1,La mémoire de l'ordinateur est comme une pile de tiroirs.

2, Lorsque plusieurs éléments doivent être stockés , Vous pouvez utiliser un tableau ou une liste liée .

3, Les éléments du tableau sont réunis .

4, Les éléments de la liste sont séparés ,Le tableau des ports d'adresse où chaque élément stocke l'élément suivant se lit rapidement.

5,Les listes enchaînées sont insérées et supprimées rapidement.

6, Dans le même tableau ,Tous les éléments doivent être du même type.

版权声明
本文为[- Non.]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/10/20211013211336261f.html

Scroll to Top