Πώς να κάνει ένα είδος φούσκα

Bubble sort είναι ένας από τους ευκολότερους αλγορίθμων ταξινόμησης . Λέγεται bubble sort , διότι οι τιμές θα είναι «φούσκα» στη λίστα σας στην κορυφή ( ή κάτω ανάλογα με το πώς σκέφτεστε αυτό) . Ενώ είναι εύκολο είδος , δεν είναι σχεδόν τόσο αποτελεσματική όσο πιο προηγμένα είδη , και θα πρέπει πραγματικά να χρησιμοποιηθούν μόνο για τους σκοπούς της μάθησης ( εκτός αν ξέρετε λίστα σας είναι σχεδόν ταξινόμηση , οπότε δεν είναι κακό ) , τι χρειάζεστε
Ένας υπολογιστής που μπορεί να συγκεντρώσει κάποια γλώσσα προγραμματισμού ή
Μολύβι και χαρτί για να πάει μέσα από το παράδειγμα
Η Εμφάνιση Περισσότερες οδηγίες
Η 1

Νομίζω ότι ο καλύτερος τρόπος για να συζητήσουν bubble sort είναι με ένα παράδειγμα. Θα δώσω μια γενική εικόνα του αλγορίθμου , και στη συνέχεια θα δουλέψουμε μέσα από ένα παράδειγμα βήμα- βήμα για να σας δώσει μια ιδέα για το πώς λειτουργεί . Έτσι, η πρώτη , η ιδέα . 2

Bubble είδος χρησιμοποιείται για να ταξινομήσετε μια λίστα των στοιχείων σε αύξουσα ή φθίνουσα σειρά . Ας υποθέσουμε για αυτού του είδους που θέλετε να βάλετε τη λίστα σε αύξουσα σειρά ( δηλαδή 1,2,3 , κλπ. ) . Το είδος λειτουργεί με το πέρασμα πάνω από κάθε στοιχείο στη λίστα σας και να το συγκρίνει με το επόμενο στοιχείο στη λίστα . Εάν το πρώτο στοιχείο είναι μεγαλύτερη από το δεύτερο στοιχείο , τα δύο είναι ενεργοποιημένα . Εάν το πρώτο στοιχείο είναι μικρότερο από ή ίσο με το δεύτερο , δεν συμβαίνει τίποτα. Μετά την εξέταση σε αυτό το στοιχείο , το επόμενο στοιχείο είναι κοίταξε , και η διαδικασία επαναλαμβάνεται .
Εικόνων 3

Όταν το είδος έχει εξετάσει κάθε στοιχείο , ένα « πέρασμα » έχει ολοκληρωθεί . Μετά από ένα πέρασμα , το ξέρεις στα σίγουρα ότι ένας αριθμός πρέπει να είναι στη σωστή θέση . Σε αύξουσα σειρά μας , η μεγαλύτερη τιμή θα «φούσκα» στο τέλος της λίστας . Δυστυχώς , δεν ξέρω αν το υπόλοιπο της λίστα είναι ταξινομημένη , οπότε θα πρέπει να λάβει μια άλλη πέρασμα. Ωστόσο , σε αυτό το πέρασμα , μπορείτε να σταματήσετε ένα στοιχείο πριν από το τέλος , αφού γνωρίζετε ότι ο αριθμός είναι ήδη στη σωστή θέση .
Η 4

Bubble sort ( συνήθως ) απαιτεί αρκετά περάσματα για να ολοκληρωθεί . Το πιο περνά θα απαιτήσει είναι ίσος με τον αριθμό των στοιχείων στη λίστα μείον 1 . Έτσι, αν έχετε 10 στοιχεία στη λίστα σας , θα μπορούσε να λάβει 9 περάσματα για να ολοκληρωθεί το είδος . Ας πάμε μέσα από ένα παράδειγμα για να το εξηγήσω καλύτερα
5

Ας χρησιμοποιήσουμε την παρακάτω λίστα αδιαχώριστα : . 6 , 3 , 1 , 8 , 2 , 4

Θα θέλαμε τη λίστα με μοιάζει με αυτό : 1 , 2 , 3 , 4 , 6 , 8

στο πρώτο πέρασμα , θα συγκρίνουμε τους αριθμούς , ένα κάθε φορά , και γνωρίζουμε ότι μετά από ένα πέρασμα θα πρέπει να έχουμε το μεγαλύτερο αριθμό σε όλη τη διαδρομή προς τα δεξιά , οπότε σε αυτή την περίπτωση , αυτό θα είναι 8 . Για το παράδειγμά μας , το σύμβολο ^ θα επισημαίνουν την θέση στη λίστα που εξετάζουν επί του παρόντος .
Η

6 6 , 3 , 1 , 8 , 2 , 4

περάσει 1 , Στάδιο 1 ) Σύγκρινε το 6 και το 3 . 6 είναι μεγαλύτερη από 3 , οπότε θα ανταλλάξουν them.3 , ^ 6 , 1 , 8 , 2 , 4

Περάστε 1 , Βήμα 2 ) Συγκρίνετε το 6 και το 1 . 6 είναι μεγαλύτερη από 1 , οπότε θα ανταλλάξουν them.3 , 1 , ^ 6 , 8 , 2 , 4

Περάστε 1 , Βήμα 3 ) Συγκρίνετε το 6 και το 8 . 6 είναι μικρότερη από ή ίση με 8 , έτσι τίποτα happens.3 , 1 , 6 , 8 ^ , 2 , 4

Περάστε 1 , Στάδιο 4 ) Σύγκρινε το 8 και το 2 . 8 είναι μεγαλύτερο από 2 , έτσι them.3 swap, 1 , 6 , 2 , ^ 8 , 4

Περάστε 1 , Βήμα 5 ) Συγκρίνετε το 8 και το 4 . 8 είναι μεγαλύτερο από 4 , οπότε them.3 swap, 1 , 6 , 2 , 4 , 8

Και τελειώσατε το πρώτο πέρασμα !
Η 7

3 , 1 , 6 , 2 , 4 , 8 είναι μετά βίας μια ταξινομημένη λίστα , αλλά μπορείτε να δείτε , όπως είχε υποσχεθεί , το 8 είναι για το τέλος. Θα γράφω τώρα από ό, τι ο κατάλογος μοιάζει μετά από κάθε πέρασμα . Δοκιμάστε τον εαυτό σας , και να δούμε αν σου ταιριάζει ορυχείο : Pass 2 : 1 , 3 , 2 , 4 , 6 , 8 (κοιτώντας καλύτερα) Περάστε 3 : 1 , 2 , 3 , 4 , 6 , 8 ( γίνεται ) Περάστε 4 : 1 , 2 , 3 , 4 , 6 , 8 ( ? μμμ ... δεν ήταν ήδη γίνει) Περάστε 5 : 1 , 2 , 3 , 4 , 6 , 8 ( ! εξακολουθεί να γίνεται )
8

Όπως μπορείτε να δείτε , ο κατάλογος ήταν ταξινομημένο μετά από 3 περάσματα , αλλά το bubble sort συνεχίζαμε . Γιατί συμβαίνει αυτό; Λοιπόν , η βασική φούσκα αλγόριθμος ταξινόμησης είναι αρκετά χαζός . Θέλει να βεβαιωθείτε ότι θα λειτουργήσει στη χειρότερη περίπτωση ( η οποία είναι μια λίστα που είναι εντελώς προς τα πίσω , όπως 9 , 8 , 7 , 6 , 5 ) . Μπορείτε να προσθέσετε μια ταχύτητα μέχρι να κάνει φούσκα σας είδος τρέξει λίγο πιο γρήγορα . Σε κάθε πέρασμα , διαθέτει μια σημαία που παίρνει οριστεί σε true μόνο αν αλλάξετε στην πραγματικότητα δύο αριθμούς . Πριν κάνετε το επόμενο πέρασμα , ελέγξτε για να δείτε αν η σημαία είναι αληθής ή ψευδής . Αν είναι αλήθεια , θα ανταλλαχθούν δύο αριθμούς , και θα πρέπει να κάνουμε ένα άλλο πέρασμα. Αν είναι ψευδής , η λίστα σας είναι ταξινομημένο , και θα μπορεί να γίνει . Στο παράδειγμά μας , έστω και αν η λίστα ήταν ταξινομημένο μετά από 3 περάσματα , θα πρέπει ακόμα να κάνει μια 4η πάσα γιατί κάναμε μια συμφωνία ανταλλαγής στο 3ο πέρασμα .
Η 9

Τώρα ξέρετε πώς να κάνει μια bubble sort . Αφήστε τα σχόλια με οποιεσδήποτε απορίες μπορεί να έχετε . Ευχαριστώ για την ανάγνωση !
Η
εικόνων