Verwenden Sie rohe Gewalt, um Auswahlsortierungsprobleme zu lösen

Die Brute-Force-Methode ist eine einfache und direkte Möglichkeit, ein Problem zu lösen, die oft direkt auf der Beschreibung des Problems und der Definition der beteiligten Konzepte basiert.

Idee zum Sortieren der Auswahl:

Scannen Sie zu Beginn der Auswahlsortierung die gesamte Liste, um das kleinste Element zu finden, tauschen Sie es dann mit dem ersten Element aus und platzieren Sie das kleinste Element an seiner endgültigen Position in der geordneten Liste. Dann durchsuchen wir die Liste beginnend mit dem zweiten Element, ermitteln den Mindestwert der letzten (n-1) Elemente, tauschen ihn mit dem zweiten Element aus und platzieren das zweitkleinste Element an seiner endgültigen Position in der Liste. Im Allgemeinen sucht der Algorithmus beim i-ten Durchsuchen der Liste (der Wert von i liegt zwischen 0 und n-2) nach dem kleinsten Element unter den letzten (n-i) Elementen und tauscht es dann mit Ai aus (Nach n-1) Durchläufen wird die Liste sortiert.

Das Folgende ist meine Code-Implementierung: 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>Algorithmusanalyse:</strong></span></div>
<p>Die Größe der Eingabe wird durch die Anzahl der Elemente n bestimmt. Die Grundoperation ist der Schlüsselwertvergleich Arr[minn]>Arr[j]. Wie oft dieser Vergleich durchgeführt wird, hängt nur von der Größe des Arrays ab, </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>Das heißt, für jede Eingabe ist die Auswahlsortierung ein Algorithmus mit einer Zeitkomplexität von Θ(n2). Die Anzahl der Schlüsselaustausche beträgt Θ(n) <i>Dadurch wird die Leistung der Auswahlsortierung verbessert. </i></p></n></n>

Das obige ist der detaillierte Inhalt vonVerwenden Sie rohe Gewalt, um Auswahlsortierungsprobleme zu lösen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!