Algorithmus und Code für die Blasensortierung in C-Sprache

Blasensortierung ist ein Sortieralgorithmus mit klaren Ideen und prägnantem Code. Er wird häufig in Computerkursen für Studenten verwendet.

Der Name „Blase“ kommt von der Tatsache, dass größere Elemente durch Austausch langsam an die Spitze der Sequenz „schweben“, daher der Name.

Hier ist ein Beispiel für die Sortierung von klein nach groß.

Grundlegende Ideen und Beispiele

Die Grundidee der Blasensortierung besteht darin, zwei benachbarte Zahlen kontinuierlich zu vergleichen, sodass sich das größere Element weiter zurückbewegt. Nach einer Vergleichsrunde wird die größte Zahl ausgewählt; nach der zweiten Vergleichsrunde wird die zweitgrößte Zahl ausgewählt und so weiter.

Das Folgende ist eine Beschreibung der Blasensortierung 3 2 4 1.

Erste Runde des Sortierprozesses
3 2 4 1 (zunächst)
2 3 4 2 (Vergleiche 3 und 2, tausche)
2 3 4 1 (Vergleiche 3 und 4, nicht Tauschen)
2 3 1 4 (4 und 1 vergleichen, tauschen)
Die erste Runde ist vorbei, die größte Zahl 4 ist bereits am Ende, sodass in der zweiten Sortierrunde nur noch die ersten drei Zahlen verglichen werden müssen wieder.

Zweite Sortierrunde
2 3 1 4 (Sortierergebnis der ersten Runde)
2 3 1 4 (Vergleiche 2 und 3, kein Austausch)
2 1 3 4 (Vergleiche 3 und 1, Austausch
Die zweite Runde ist vorbei, die zweitgrößte Zahl wurde an der vorletzten Position platziert, sodass in der dritten Runde nur die ersten beiden Elemente verglichen werden müssen

Die dritte Sortierrunde Prozess.
2 1 3 4 (Zweite Runde der Sortierergebnisse)
1 2 3 4 (Vergleiche 2 und 1, Austausch)
Dies ist das Ende der Sortierung

Zusammenfassung und Umsetzung des Algorithmus

Führen Sie für ein Array R[n] mit N Elementen bis zu N-1 Vergleichsrunden durch

Vergleichen Sie in der ersten Runde (R[1], R[; 2]) eins nach dem anderen, (R[ 2], R[3]), (R[3], R[4]), … (R[N-1], R[N]); wird nach R[N] verschoben

Vergleichen Sie in der zweiten Runde (R[1], R[2]), (R[2], R[3]), (R[3] , R[4]), … …. (R[N-2], R[N-1]); das zweitgrößte Element wird nach R[N-1] verschoben, bis das gesamte Array vorhanden ist sortiert von klein nach groß. Die allgemeine Implementierung und die optimierte Implementierung der Blasensortierung sind gängige Implementierungsmethoden in Lehrbüchern, unabhängig davon, ob das Array sortiert ist oder nicht Die optimierte Implementierung beendet den Vergleich frühzeitig, wenn das Array sortiert wurde, wodurch die zeitliche Komplexität des Algorithmus reduziert wird

#include<stdio.h>
#include<stdlib.h>

#define N 8

void bubble_sort(int a[],int n);


//一般实现
void bubble_sort(int a[],int n)//n为数组a的元素个数
{
//一定进行N-1轮比较
for(int i=0; i<n-1; i++)
{
//每一轮比较前n-1-i个，即已排序好的最后i个不用比较
for(int j=0; j<n-1-i; j++)
{
if(a[j] > a[j+1])
{
int temp = a[j];
a[j] = a[j+1];
a[j+1]=temp;
}
}
}
}

//优化实现
void bubble_sort_better(int a[],int n)//n为数组a的元素个数
{
//最多进行N-1轮比较
for(int i=0; i<n-1; i++)
{
bool isSorted = true;
//每一轮比较前n-1-i个，即已排序好的最后i个不用比较
for(int j=0; j<n-1-i; j++)
{
if(a[j] > a[j+1])
{
isSorted = false;
int temp = a[j];
a[j] = a[j+1];
a[j+1]=temp;
}
}
if(isSorted) break; //如果没有发生交换，说明数组已经排序好了
}
}


int  main()
{
int num[N] = {89, 38, 11, 78, 96, 44, 19, 25};

bubble_sort(num, N); //或者使用bubble_sort_better(num, N);

for(int i=0; i<N; i++)
printf("%d  ", num[i]);

printf("\n");


system("pause");
return 0;
}

Weitere Artikel zum C-Sprachblasensortieralgorithmus und -code finden Sie auf der chinesischen PHP-Website