Lösen Sie die Blasensortierung mit roher Gewalt

Bubble Sort ist eine weitere klassische Ausführungsform der Brute-Force-Methode.

Algorithmusidee: Vergleichen Sie benachbarte Elemente in der Liste und tauschen Sie ihre Positionen, wenn sie in umgekehrter Reihenfolge sind. Nach mehrmaliger Wiederholung wird das größte Element als letztes eingestuft. Die zweite Operation verschiebt das zweite Element an die vorletzte Position und der Vergleich wird bis n-1 Mal fortgesetzt und die gesamte Liste wird sortiert.

Das Folgende ist meine Code-Implementierung: C++

#include 
using namespace std;
int main()
{
    int i,j,temp,N;
    cin>>N;
    int *Arr=new int[N];
    for(i=0;i<n cin>>Arr[i];
 
    for(i=0;i<n for if>Arr[j+1])//如果逆序，就交换
            {
                temp=Arr[j];
                Arr[j]=Arr[j+1];
                Arr[j+1]=temp;
            }
        }
    }
 
    for(i=0;i<n cout return>
<p>Algorithmusanalyse: Die Größe der Eingabe wird vollständig durch N bestimmt. Die Grundoperation ist der Vergleich: Arr[j]>Arr[j+1], Zeitkomplexität C(n)=Θ(n2).</p>
<p>Aber die Anzahl der Schlüsselaustausche hängt von der spezifischen Eingabe ab. Der schlimmste Fall ist das Gegenteil der von uns benötigten Sortierung. Zu diesem Zeitpunkt ist die Anzahl der Schlüsselaustausche = die Anzahl der Schlüsselvergleiche = Θ(n2).</p>
<p>Aber in einigen Eingabefällen ist die Liste bereits in Ordnung, wenn nach dem Vergleich der Liste die Positionen der Elemente nicht ausgetauscht werden, und wir können den Algorithmus stoppen. Die spezifische verbesserte Version lautet wie folgt: </p>
<pre class="brush:php;toolbar:false">#include 
using namespace std;
int main()
{
    int i,j,temp,N;
    bool change=false;
    cin>>N;
    int *Arr=new int[N];
    for(i=0;i<n cin>>Arr[i];
 
    for(i=0;i<n change="false;" for if>Arr[j+1])//如果逆序，就交换
            {
                temp=Arr[j];
                Arr[j]=Arr[j+1];
                Arr[j+1]=temp;
                change=true;
            }
        }
        if(!change)//没有发生交换，则不用继续比较了。
        {
            break;
        }
    }
 
    for(i=0;i<n cout return>
<p>Aber im schlimmsten Fall beträgt die Zeitkomplexität immer noch Θ(n2).</p></n></n></n>

Das obige ist der detaillierte Inhalt vonLösen Sie die Blasensortierung mit roher Gewalt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!