Bubble Sort ist eine der einfachsten Sortieralgorithmen . Es heißt Bubble Sort , weil die wird es "Blase" Werte in der Liste nach oben ( oder unten , je nachdem wie Sie denken, es ) . Während es eine einfache Art ist, ist es bei weitem nicht so effizient wie fortgeschrittenere Art, und sollte wirklich nur zu Lernzwecken eingesetzt werden (es sei denn Sie Ihre Liste fast sortiert ist , in welchem Fall es nicht schlecht wissen ) Was Sie brauchen
Ein Computer, der eine Programmiersprache oder in Bleistift und Papier durch das Beispiel
gehen kompilieren anzeigen Weitere Anweisungen
1
ich denke, der beste Weg, um bubble sort diskutieren ist mit einem Beispiel. Ich gebe einen Überblick über den Algorithmus , und dann werden wir anhand eines Beispiels Schritt -für-Schritt , um Ihnen eine Vorstellung davon, wie es funktioniert zu arbeiten. Also erstens, die Idee .
2
Bubble Sort wird verwendet, um eine Liste der Elemente in aufsteigender oder absteigender Reihenfolge zu sortieren. Lassen Sie uns für diese Art an, dass Sie die Liste in aufsteigender Reihenfolge (dh 1,2,3 , etc.) setzen wollen . Die Sortierung funktioniert, indem über jedes Element in der Liste und vergleicht es mit dem nächsten Element in der Liste. Wenn das erste Element größer ist als das zweite Element sind die beiden umgeschaltet. Wenn das erste Element kleiner oder gleich dem zweiten , geschieht nichts. Nach einem Blick auf dieses Element , wird das nächste Element betrachtet , und der Vorgang wiederholt sich .
3
Wenn die Art hat bei jedem Element sah , einen "Pass" ist abgeschlossen. Nach einem Pass , wissen Sie sicher , dass eine Zahl in der richtigen Position sein muss. In unserem aufsteigender Reihenfolge , wird der größte Wert "Blase" an das Ende der Liste. Leider weiß man nicht, ob der Rest der Liste ist sortiert , so müssen Sie einen weiteren Durchgang zu nehmen. Doch auf diesem Pass können Sie ein Element vor dem Ende zu stoppen, da Sie wissen, dass Nummer ist bereits in der richtigen Position .
4
Bubble Sort (in der Regel ) erfordert mehrere Durchläufe , um abzuschließen. Die Durchgänge es erfordert ist gleich der Anzahl der Elemente in der Liste minus 1 . Also, wenn Sie 10 Elemente in Ihrer Liste haben , könnte es nehmen 9 Pässe , um die Art zu vervollständigen. Lassen Sie uns an einem Beispiel gehen, um besser zu erklären, es
5
Lassen Sie uns die folgende unsortierte Liste : . 6, 3, 1, 8 , 2, 4
die Liste möchten sehen wie folgt aus : 1, 2 , 3, 4 , 6, 8
Beim ersten Durchgang , werden wir die Zahlen von eins zu einer Zeit, zu vergleichen, und wir wissen, dass nach einem Durchlauf sollten wir die größte Anzahl haben ganz nach rechts , so dass in diesem Fall wird das 8 sein. Für unser Beispiel wird das Zeichen ^ zu der Stelle in der Liste zu zeigen , dass wir derzeit untersuchen .
6
6, 3, 1, 8 , 2, 4
Pass 1 , Schritt 1) Vergleichen Sie die 6 und die 3 . 6 ist größer als 3, so dass wir them.3 tauschen, ^ 6 , 1, 8, 2 , 4
Pass 1, Schritt 2) Vergleichen Sie die 6 und die 1 . 6 ist größer als 1 , so dass wir tauschen them.3 , 1, ^ 6, 8 , 2, 4
Pass 1 , Schritt 3 ) Vergleichen Sie die 6 und die 8 . 6 ist kleiner als oder gleich 8 , so dass nichts happens.3 , 1, 6, ^ 8 , 2, 4
Pass 1 , Schritt 4) Vergleichen Sie die 8 und die 2 . 8 ist größer als 2 , so tauschen them.3 , 1, 6 , 2, ^ 8 , 4
Pass 1 , Schritt 5) Vergleichen Sie die 8 und die 4 . 8 ist größer als 4 , so tauschen them.3 , 1, 6 , 2, 4 , 8
und du bist der erste Durchlauf fertig!
7
3, 1, 6, 2 , 4, 8 kaum eine sortierte Liste , aber man kann sehen , wie versprochen, ist der 8 am Ende. Ich werde jetzt schreiben, was die Liste wie nach jedem Durchgang aussieht. Probieren Sie es aus und sehen, ob Ihr mir passt : Pass 2: 1, 3, 2, 4, 6, 8 ( sieht besser aus ) Pass 3: 1, 2 , 3, 4 , 6, 8 (fertig) Pass 4 : 1 , 2, 3 , 4, 6, 8 ( umm ... waren wir nicht schon getan? ) Pass 5 : ( ! noch getan ) 1, 2 , 3, 4 , 6, 8
8 < p> Wie Sie sehen können , die Liste wurde nach 3 Durchgängen sortiert , aber die Blase Art in Gang gehalten . Warum ist das so ? Nun, das ist die grundlegende Bubble-Sort -Algorithmus ziemlich dumm . Es will sicherstellen, dass es im schlimmsten Fall zu arbeiten (das ist eine Liste, die ganz nach hinten ist wie 9, 8, 7, 6, 5). Sie können eine Geschwindigkeit von bis zu Ihren bubble sort ein bisschen schneller laufen. Auf jedem Pass , eine Flagge, die auf true gesetzt wird , NUR wenn Sie wechseln tatsächlich zwei Zahlen. Bevor Sie den nächsten Pass zu tun , um zu sehen, ob das Flag wahr oder falsch ist . Wenn es wahr ist , tauschte man zwei Zahlen , und Sie haben einen anderen Pass zu tun. Wenn es falsch ist , wird die Liste sortiert , und Sie können durchgeführt werden. In unserem Beispiel , auch wenn die Liste nach 3 Durchgängen sortiert wurde , würden wir noch brauchen, um einen 4. Pass zu machen, weil wir eine Swap gemacht im 3. Durchgang .
9
Jetzt wissen Sie , wie man ein zu tun bubble sort . Lassen Sie Kommentare mit allen möglichen Fragen , die Sie haben . Danke fürs Lesen !
