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>

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!