Blasensortierung

1. Algorithmusbeschreibung

Blasensortierung: Vergleichen Sie nacheinander benachbarte Daten, stellen Sie kleine Daten nach vorne und große Daten nach hinten, dh vergleichen Sie die 1. und 2. Zahl im ersten Durchgang Die Zahl steht an letzter Stelle, die Dezimalzahl steht an erster Stelle, dann wird die zweite Zahl mit der dritten Zahl verglichen, die große Zahl steht an letzter Stelle, die Dezimalzahl steht an erster Stelle usw. Die größte Zahl wird an die letzte Stelle „gerollt“. Bei einem Durchgang wird die nächstgrößere Zahl an die vorletzte Position gescrollt ... Die n-1 (n ist die Anzahl der ungeordneten Daten) Durchgänge können die Sortierung abschließen.

Nehmen Sie die folgenden 5 ungeordneten Daten als Beispiel:

40 8 15 18 12 (Der Artikel beschreibt nur den Vergleichsprozess des ersten Durchgangs)

Der 1. Durchgang: 8 15 18 12 40

Die 2. Fahrt: 8 15 12 18 40

Die 3. Fahrt: 8 12 15 18 40

Die 4. Reise: 8 12 15 18 40

2. Algorithmusanalyse

Durchschnittliche Zeitkomplexität: O(n2)

Raumkomplexität: O(1) ( Wird für den Austausch verwendet )

Stabilität: Stabil

3. Algorithmusimplementierung

//交换data1和data2所指向的整形  
void DataSwap(int* data1, int* data2)  
{  
    int temp = *data1;  
    *data1 = *data2;  
    *data2 = temp;  
}  
  
/******************************************************** 
*函数名称：BubbleSort 
*参数说明：pDataArray 无序数组； 
*          iDataNum为无序数据个数 
*说明：    Blasensortierung 
*********************************************************/  
void BubbleSort(int* pDataArray, int iDataNum)  
{  
    for (int i = 0; i < iDataNum - 1; i++)   //走iDataNum-1趟  
        for (int j = 0; j < iDataNum - i - 1; j++)      
            if (pDataArray[j] > pDataArray[j + 1])  
                DataSwap(&pDataArray[j], &pDataArray[j + 1]);  
}

4. Algorithmusoptimierung

kann auch für den Blasensortierungsalgorithmus verwendet werden Führen Sie a aus Einfache Optimierung und Verwendung einer Markierung, um zu protokollieren, ob während eines Vergleichs ein Austausch erfolgt. Wenn kein Austausch erfolgt, hat das gesamte Array den Sortiervorgang ordnungsgemäß verlassen. Andernfalls fahren Sie mit dem nächsten Vergleich fort.

/******************************************************** 
*函数名称：BubbleSort 
*参数说明：pDataArray 无序数组； 
*          iDataNum为无序数据个数 
*说明：    Blasensortierung 
*********************************************************/  
void BubbleSort(int* pDataArray, int iDataNum)  
{  
    BOOL flag = FALSE;    //记录是否存在交换  
    for (int i = 0; i < iDataNum - 1; i++)    //走iDataNum-1趟  
    {  
        flag = FALSE;  
        for (int j = 0; j < iDataNum - i - 1; j++)      
            if (pDataArray[j] > pDataArray[j + 1])  
            {  
                flag = TRUE;  
                DataSwap(&pDataArray[j], &pDataArray[j + 1]);  
            }  
          
        if (!flag)    //上一趟比较中不存在交换，则退出排序  
            break;  
    }  
}

Weitere Artikel zum Thema Blasensortierung finden Sie auf der chinesischen PHP-Website!