Drei Implementierungen der Blasensortierung

Blasensortierung ist sehr einfach zu verstehen und zu implementieren. Nehmen Sie als Beispiel die Sortierung von klein nach groß:

Angenommen, die Array-Länge beträgt N.

1． Vergleichen Sie die beiden benachbarten Daten vorher und nachher. Wenn die ersteren Daten größer sind als die letzteren Daten, werden die beiden Daten ausgetauscht.

2． Auf diese Weise „sinken“ die größten Daten nach dem Durchlaufen der 0. Daten zu den N-1. Daten des Arrays zur N-1. Position des Arrays.

3． N = N-1, wenn N nicht 0 ist, wiederholen Sie die beiden vorherigen Schritte, andernfalls ist die Sortierung abgeschlossen.

Es ist einfach, den Code per Definition zu schreiben:

//冒泡排序1  
void BubbleSort1(int a[], int n)  
{  
       int i, j;  
       for (i = 0; i < n; i++)  
              for (j = 1; j < n - i; j++)  
                     if (a[j - 1] > a[j])  
                            Swap(a[j - 1], a[j]);  
}

Lassen Sie uns ihn optimieren und eine Markierung setzen. Wenn es auf dieser Reise zu einem Austausch kommt, wird es so sein wahr, sonst falsch. Wenn bei einer Fahrt kein Umtausch erfolgt, bedeutet dies natürlich, dass die Sortierung abgeschlossen ist.

//冒泡排序2  
void BubbleSort2(int a[], int n)  
{  
       int j, k;  
       bool flag;  
  
       k = n;  
       flag = true;  
       while (flag)  
       {  
              flag = false;  
              for (j = 1; j < k; j++)  
                     if (a[j - 1] > a[j])  
                     {  
                            Swap(a[j - 1], a[j]);  
                            flag = true;  
                     }  
              k--;  
       }  
}

Lassen Sie uns weitere Optimierungen vornehmen. Wenn es ein Array mit 100 Zahlen gibt, nur die ersten 10 ungeordnet sind und die nächsten 90 alle sortiert sind und alle größer als die ersten 10 Zahlen sind, muss nach dem ersten Durchlauf die letzte Position, an der der Austausch stattfindet, kleiner sein als 10, und die Daten nach der Position müssen in Ordnung sein. Beim zweiten Mal müssen Sie nur vom Kopf des Arrays zu dieser Position wechseln.

//冒泡排序3  
void BubbleSort3(int a[], int n)  
{  
    int j, k;  
    int flag;  
      
    flag = n;  
    while (flag > 0)  
    {  
        k = flag;  
        flag = 0;  
        for (j = 1; j < k; j++)  
            if (a[j - 1] > a[j])  
            {  
                Swap(a[j - 1], a[j]);  
                flag = j;  
            }  
    }  
}

Blasensortierung ist schließlich eine ineffiziente Sortiermethode und kann verwendet werden, wenn die Datengröße klein ist. Wenn die Datengröße relativ groß ist, ist es am besten, andere Sortiermethoden zu verwenden.

Weitere Artikel zu den drei Implementierungen der Blasensortierung finden Sie auf der chinesischen PHP-Website!