Maison > Tutoriel système > Linux > Utiliser la force brute pour résoudre les problèmes de tri de sélection

Utiliser la force brute pour résoudre les problèmes de tri de sélection

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
Libérer: 2024-02-18 09:27:11
avant
932 Les gens l'ont consulté

Utiliser la force brute pour résoudre les problèmes de tri de sélection

La méthode par force brute est une manière simple et directe de résoudre un problème, souvent basée directement sur la description du problème et la définition des concepts impliqués.

Idée de tri sélection :

Au début du tri par sélection, parcourez toute la liste pour trouver le plus petit élément, puis échangez-le avec le premier élément, et placez le plus petit élément à sa position finale dans la liste ordonnée. Ensuite, nous parcourons la liste à partir du deuxième élément, trouvons la valeur minimale des derniers (n-1) éléments, l'échangeons avec le deuxième élément et plaçons le deuxième plus petit élément à sa position finale dans la liste. De manière générale, lors du parcours de la liste pour la ième fois (la valeur de i est comprise entre 0 et n-2), l'algorithme recherche le plus petit élément parmi les (n-i) derniers éléments, puis l'échange avec Ai, en (Après n-1) passage, la liste est triée.

Ce qui suit est l'implémentation de mon code : C++
#include 
using namespace std;
int main()
{
    int i,j,temp,minn,N;
    cin>>N;
    int *Arr=new int[N];
    for(i=0;i<n cin>>Arr[i];
 
    for(i=0;iArr[j])
                minn=j;//记录最小值的下标
        }
        temp=Arr[minn];     //交换Arr[minn]和Arr[i]。
        Arr[minn]=Arr[i];
        Arr[i]=temp;
    }
 
    for(i=0;i<n cout return>
<div style="margin-top: 2em; margin-bottom: 1em;"><span style="color: #1e1e1e; letter-spacing: 2px; border-left: #FF3030 3px solid; border-right: #FF3030 3px solid; padding-left: 8px; padding-right: 8px; font-size: 12pt;"><strong>Analyse d'algorithme :</strong></span></div>
<p>La taille de l'entrée est déterminée par le nombre d'éléments n. L'opération de base est la comparaison des valeurs clés Arr[minn]>Arr[j]. Le nombre de fois que cette comparaison est effectuée dépend uniquement de la taille du tableau, </p>
<p>C(n)=∑[i=0,i=N-2] ∑[j=i+1,j=N-1]=∑[i=0,i=N-2] ((N-1 )-(i+1)+1))=∑[i=0,i=N-2](N-i-1)=(n-1)*n/2</p>
<p> Autrement dit, pour toute entrée, le tri par sélection est un algorithme avec une complexité temporelle de Θ (n2). Le nombre d'échanges de clés est Θ(n) <i>Cela améliore les performances du tri par sélection. </i></p></n></n>
Copier après la connexion

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Derniers numéros
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal