Eine Einführung in Sortieralgorithmen: Blasensortierung

In der Entwicklung ist es oft notwendig, einen Datensatz geordnet anzuordnen, daher ist es unbedingt erforderlich, mehrere oder sogar mehr Sortieralgorithmen zu beherrschen

In diesem Artikel wird das Sortieren vorgestellt. Einer der einfacheren Algorithmen: Blasensortierung

Versuchen Sie zunächst, die einfachste Idee zum Implementieren der Sortierung zu verwenden, um die Blasensortierung zu vergleichen und zu lernen

Problem: Angenommen, es gibt ein Array, dessen Daten die Größe 10 haben elements (int str[10]) ist ungeordnet. Jetzt müssen wir dieses ungeordnete Array in ein Array programmieren, das von klein nach groß sortiert ist (beginnend mit dem Index 0)

Idee: Gemäß den Anforderungen der Frage besteht kein Zweifel daran, dass das richtige Ergebnis „Like“ sein sollte Dies: 1 2 3 4 5 6 7 8 9 10 Der einfachste und direkteste Weg, dies zu erreichen, ist Vergleichen und Austauschen.

Setzen Sie zunächst die kleinste Zahl unter den 10 Zahlen an die Position mit dem Index 0 (str[0])

Durch Vergleichen und Austauschen der markierten Zahl mit 0 (str[0]) mit den verbleibenden 9 Zahlen (platzieren Sie die kleinere Zahl an der Position mit dem Index 0), und Sie können die kleinste Zahl unter den 10 erhalten

Nachdem die 10 kleinsten Zahlen ermittelt wurden , besteht der nächste Schritt darin, die verbleibenden 9 kleinsten Zahlen zu finden.

Da eine Mindestzahl festgelegt wurde, berühren Sie str[0] nicht, vergleichen und tauschen Sie mit den verbleibenden 8 Zahlen und ermitteln Sie die kleinste der 9 Zahlen das an der Position mit Index 1 (str[1])

Folgen Sie dieser Idee weiter und Sie können diese zehn Zahlen in ein geordnetes (von klein nach groß) Array umwandeln

Code:

#include <stdio.h>  
  
void swap(int *a, int *b); //交换两个数  
  
int main()  
{  
    int     str[10];  
    int     i, j;  
    //初始化数组为10 9 8 7 6 5 4 3 2 1  
    for (i = 0; i < 10; i++)  
    {  
        str[i] = 10 - i;  
    }  
    //排序，从a[0]开始排，从小到大  
    for (i = 0; i < 10; i++)  
    {  
        for (j = i + 1; j < 10; j++)  
        {  
            if (str[i] > str[j])  
            {  
                swap(&str[i], &str[j]);  
            }  
        }  
    }  
        //将十个数输出  
    for (i = 0; i < 10; i++)  
        printf("%d\n", str[i]);  
    return    0;  
}  
void swap(int *a, int *b)  
{  
    int     c;  
     c = *a;  
    *a = *b;  
    *b =  c;  
}

Diese Methode ist einfacher vorstellbar. Es gibt jedoch einen Mangel: Die ursprünglich vorne befindliche kleinere Nummer wird nach hinten vertauscht

Vorführung:

Beginn: 9 4 5 6 8 3 2 7 10 1 (Die Indizes sind jeweils 0 bis 9 von links nach rechts) Befolgen Sie zum Vergleichen und Austauschen das obige Verfahren

Das erste Mal: ​​4 9 5 6 8 3 2 7 10 1

Das zweite Mal: ​​4 9 5 6 8 3 2 7 10 1

. . . : (kein Umtausch)

Das fünfte Mal: ​​3 9 5 6 8 4 2 7 10 1

Das sechste Mal: ​​2 9 5 6 8 3 4 7 10 1

. . . : (kein Umtausch)

Das zehnte Mal: ​​1 9 5 6 8 3 4 7 10 2

Es ist ersichtlich, dass die ursprüngliche kleinere Zahl nach einer Umtauschrunde vorne liegt Dann Platzieren Sie es auf der Rückseite

Wie lässt sich dieser Mangel beheben? Sie können die Blasensortierung verwenden

Was ist Blasensortierung?

Sie können es so verstehen: (Sortiert von klein nach groß) Es gibt 10 Blasen unterschiedlicher Größe, und die kleineren Blasen werden nach und nach von unten nach oben nach oben bewegt, sodass nach einer Durchquerung die kleinste Blase entsteht wird nach oben (Index 0) und dann wieder von unten nach oben angehoben, und der Zyklus wird fortgesetzt, bis zehn Blasen in Ordnung sind.

Bei der Blasensortierung besteht die wichtigste Idee darin, die beiden zu vergleichen und die kleinere zu fördern

Die zeitliche Komplexität der Blasensortierung im ungünstigsten Fall beträgt O(n²)

Code:

#include <stdio.h>  
void swap(int *a, int *b);  
int main()  
{  
    int    array[10] = {15, 225, 34, 42, 52, 6, 7856, 865, 954, 10};  
    int    i, j;  
    for (i = 0; i < 10; i++)  
    {  
        //每一次由底至上地上升  
        for (j = 9; j > i; j--)  
        {  
            if (array[j] < array[j-1])  
            {  
                    swap(&array[j], &array[j-1]);  
            }  
        }  
    }  
    for (i = 0; i < 10; i++)  
    {  
        printf("%d\n", array[i]);  
    }  
    return    0;  
}  
void swap(int *a, int *b)  
{  
    int    temp;  
    temp = *a;  
      *a = *b;  
      *b = temp;  
}

Der Blasensortierungsalgorithmus verschiebt kleinere Zahlen nur schrittweise nach oben, was nicht zu den zuvor im Artikel erwähnten Mängeln führt und hier nicht demonstriert wird.

Weitere Artikel zum Einstieg in Sortieralgorithmen und Blasensortierung finden Sie auf der chinesischen PHP-Website!