Gunakan kekerasan untuk menyelesaikan jenis gelembung

Bubble sort ialah satu lagi penjelmaan klasik kaedah brute force.

Idea algoritma: Bandingkan elemen bersebelahan dalam senarai, dan jika ia dalam susunan terbalik, tukar kedudukannya. Selepas mengulanginya berkali-kali, elemen terbesar diletakkan pada kedudukan terakhir. Operasi kedua mengalihkan elemen kedua ke kedudukan kedua terakhir, dan perbandingan diteruskan sehingga n-1 kali, dan keseluruhan senarai diisih.

Berikut ialah pelaksanaan kod saya: 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>Analisis algoritma: Saiz input ditentukan sepenuhnya oleh N. Operasi asas ialah perbandingan: Arr[j]>Arr[j+1], kerumitan masa C(n)=Θ(n2).</p>
<p>Tetapi bilangan pertukaran kunci bergantung pada input khusus Kes yang paling teruk adalah bertentangan dengan pengisihan yang kami perlukan Pada masa ini, bilangan pertukaran kunci = bilangan perbandingan kunci = Θ(n2).</p>.
<p>Tetapi dalam beberapa situasi input, jika selepas membandingkan senarai, kedudukan elemen tidak ditukar, maka senarai itu sudah teratur, dan kita boleh menghentikan algoritma. Versi khusus yang dipertingkatkan adalah seperti berikut: </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>Tetapi dalam kes yang paling teruk, kerumitan masa masih Θ(n2).</p></n></n></n>

Atas ialah kandungan terperinci Gunakan kekerasan untuk menyelesaikan jenis gelembung. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!