bubble sort java java sorting algorithms code examples
Αυτό το σεμινάριο θα εξηγήσει το Bubble Sort στην Java μαζί με το Major Java Sorting Algorithm, Bubble Sort Implementation & Code Παραδείγματα:
Ένας αλγόριθμος ταξινόμησης μπορεί να οριστεί ως ένας αλγόριθμος ή μια διαδικασία για την τοποθέτηση στοιχείων μιας συλλογής σε μια συγκεκριμένη σειρά. Για παράδειγμα, εάν έχετε μια αριθμητική συλλογή όπως μια λίστα ακέραιων αριθμών, τότε ίσως θελήσετε να τακτοποιήσετε τα στοιχεία του ArrayList σε αύξουσα ή φθίνουσα σειρά.
Ομοίως, ίσως θελήσετε να τακτοποιήσετε συμβολοσειρά μιας συλλογής συμβολοσειρών με αλφαβητική ή λεξικογραφική σειρά. Εδώ εμφανίζονται οι αλγόριθμοι ταξινόμησης στην Java.
άνοιγμα αρχείων βάζων στα παράθυρα 10
Τι θα μάθετε:
Σημαντικοί αλγόριθμοι ταξινόμησης στην Ιάβα
Οι αλγόριθμοι ταξινόμησης συνήθως αξιολογούνται ανάλογα με την πολυπλοκότητα χρόνου και χώρου. Η Java υποστηρίζει διάφορους αλγόριθμους ταξινόμησης που χρησιμοποιούνται για την ταξινόμηση ή την τακτοποίηση των συλλογών ή των δομών δεδομένων.
Ο παρακάτω πίνακας δείχνει τους κύριους αλγόριθμους ταξινόμησης που υποστηρίζονται στην Java μαζί με τις καλύτερες / χειρότερες περιπλοκές τους.
Χρόνος πολυπλοκότητας | ||||
---|---|---|---|---|
Ταξινόμηση Radix | Γραμμικός αλγόριθμος ταξινόμησης. | O(nk) | O(nk) | O(nk) |
Αλγόριθμος ταξινόμησης | Περιγραφή | Καλύτερη περίπτωση | Χειρότερη περίπτωση | Μέση θήκη |
Ταξινόμηση φυσαλίδων | Συγκρίνει το τρέχον στοιχείο με τα παρακείμενα στοιχεία επανειλημμένα. Στο τέλος κάθε επανάληψης, το βαρύτερο στοιχείο αναβλύζει στη σωστή του θέση. | Επί) | O (n ^ 2) | O (n ^ 2) |
Ταξινόμηση εισαγωγής | Εισάγει κάθε στοιχείο της συλλογής στη σωστή του θέση. | Επί) | O (n ^ 2) | O (n ^ 2) |
Συγχώνευση ταξινόμησης | Ακολουθεί την προσέγγιση διαίρεσης και κατάκτησης. Χωρίζει τη συλλογή σε απλούστερες υπο-συλλογές, τις ταξινομεί και στη συνέχεια συγχωνεύει τα πάντα | O (nlogn) | O (nlogn) | O (nlogn) |
Γρήγορη ταξινόμηση | Η πιο αποτελεσματική και βελτιστοποιημένη τεχνική ταξινόμησης. Χρησιμοποιεί διαίρεση και κατάκτηση για να ταξινομήσετε τη συλλογή. | O (nlogn) | O (n ^ 2) | O (nlogn) |
Ταξινόμηση επιλογής | Βρίσκει το μικρότερο στοιχείο στη συλλογή και το τοποθετεί στη σωστή του θέση στο τέλος κάθε επανάληψης | Ο (Ν ^ 2) | Ο (Ν ^ 2) | Ο (Ν ^ 2) |
Ταξινόμηση σωρού | Τα στοιχεία ταξινομούνται με βάση τον ελάχιστο σωρό ή το μέγιστο σωρό. | O (nlogn) | O (nlogn) | O (nlogn) |
Εκτός από τις τεχνικές ταξινόμησης που δίνονται στον παραπάνω πίνακα, η Java υποστηρίζει επίσης τις ακόλουθες τεχνικές ταξινόμησης:
- Ταξινόμηση κάδου
- Καταμέτρηση Ταξινόμηση
- Ταξινόμηση κελύφους
- Ταξινόμηση χτενών
Αλλά αυτές οι τεχνικές χρησιμοποιούνται με φειδώ σε πρακτικές εφαρμογές, επομένως αυτές οι τεχνικές δεν θα είναι μέρος αυτής της σειράς.
Ας συζητήσουμε την τεχνική Bubble Sort στην Java.
Ταξινόμηση φυσαλίδων στην Ιάβα
Το Bubble sort είναι η απλούστερη όλων των τεχνικών ταξινόμησης στην Java. Αυτή η τεχνική ταξινομεί τη συλλογή συγκρίνοντας επανειλημμένα δύο παρακείμενα στοιχεία και εναλλάσσοντάς τα εάν δεν είναι στην επιθυμητή σειρά. Έτσι, στο τέλος της επανάληψης, το βαρύτερο στοιχείο αναβλύζει για να διεκδικήσει τη σωστή του θέση.
Εάν υπάρχουν n στοιχεία στη λίστα Α που δίνονται από τα A (0), A (1), A (2), A (3),… .A (n-1), τότε το A (0) συγκρίνεται με το A (1 ), Το A (1) συγκρίνεται με το A (2) και ούτω καθεξής. Αφού συγκρίνετε εάν το πρώτο στοιχείο είναι μεγαλύτερο από το δεύτερο, τότε τα δύο στοιχεία ανταλλάσσονται εάν δεν είναι σωστά.
Αλγόριθμος ταξινόμησης φυσαλίδων
Ο γενικός αλγόριθμος για Bubble Sort Technique δίνεται παρακάτω:
Βήμα 1: Για i = 0 έως N-1 επαναλάβετε το Βήμα 2
Βήμα 2: Για J = i + 1 έως N - επαναλαμβάνω
Βήμα 3: αν A (J)> A (i)
Ανταλλαγή A (J) και A (i)
(Τέλος εσωτερικού για βρόχο)
(Τερματισμός εάν Outer for loop)
Βήμα 4: Εξοδος
Τώρα ας δείξουμε την τεχνική Bubble Sort χρησιμοποιώντας ένα ενδεικτικό παράδειγμα.
Παίρνουμε μια σειρά μεγέθους 5 και επεξηγούμε τον αλγόριθμο ταξινόμησης φυσαλίδων.
Ταξινόμηση μιας σειράς χρησιμοποιώντας Bubble είδος
Η ακόλουθη λίστα πρέπει να ταξινομηθεί.
καλύτερο δωρεάν εργαλείο επισκευής windows 7
Όπως μπορείτε να δείτε παραπάνω, ο πίνακας έχει ταξινομηθεί πλήρως.
Η παραπάνω εικόνα μπορεί να συνοψιστεί σε μορφή πίνακα όπως φαίνεται παρακάτω:
Πέρασμα | Μη ταξινομημένη λίστα | σύγκριση | Ταξινομημένη λίστα |
---|---|---|---|
{3,6,11,4,15} | {11.4} | {3,6,4,11,15} | |
1 | {11, 3, 6,15,4} | {11.3} | {3,11,6,15,4} |
{3,11,6,15,4} | {11.6} | {3,6,11,15,4} | |
{3,6,11,15,4} | {11.15} | {3,6,11,15,4} | |
{3,6,11,15,4} | {15.4} | {3,6,11,4,15} | |
δύο | {3,6,11,4,15} | {3,6} | {3,6,11,4,15} |
{3,6,11,4,15} | {6.11} | {3,6,11,4,15} | |
3 | {3,6,4,11,15} | {3,6} | {3,6,4,11,15} |
{3,6,4,11,15} | {6.4} | {3,4,6,11,15} | |
{3,4,6,11,15} | ΚΑΤΑΧΩΡΙΣΜΕΝΟ |
Όπως φαίνεται στο παραπάνω παράδειγμα, το μεγαλύτερο στοιχείο βράζει μέχρι τη σωστή του θέση με κάθε επανάληψη / πέρασμα. Σε γενικές γραμμές, όταν φτάσουμε στο Ν-1 (όπου το Ν είναι ένας συνολικός αριθμός στοιχείων στη λίστα) περνάει. θα έχουμε ταξινομήσει ολόκληρη τη λίστα.
Παράδειγμα κώδικα ταξινόμησης Bubble
Το παρακάτω πρόγραμμα δείχνει την υλοποίηση Java του αλγορίθμου ταξινόμησης φυσαλίδων. Εδώ, διατηρούμε μια σειρά αριθμών και χρησιμοποιούμε δύο για βρόχους για να διασχίσουμε τα παρακείμενα στοιχεία του πίνακα. Εάν δύο παρακείμενα στοιχεία δεν είναι σωστά, τότε ανταλλάσσονται.
import java.util.*; class Main{ // Driver method to test above public static void main(String args()) { //declare an array of integers int intArray() = {23,43,13,65,11,62,76,83,9,71,84,34,96,80}; //print original array System.out.println('Original array: ' + Arrays.toString(intArray)); int n = intArray.length; //iterate over the array comparing adjacent elements for (int i = 0; i intArray(j+1)) { int temp = intArray(j); intArray(j) = intArray(j+1); intArray(j+1) = temp; } //print the sorted array System.out.println('Sorted array: ' + Arrays.toString(intArray)); } }
Παραγωγή:
Αρχική σειρά: (23, 43, 13, 65, 11, 62, 76, 83, 9, 71, 84, 34, 96, 80)
Ταξινομημένη σειρά: (9, 11, 13, 23, 34, 43, 62, 65, 71, 76, 80, 83, 84, 96)
Συχνές Ερωτήσεις
Ε # 1) Ποιοι είναι οι Αλγόριθμοι Ταξινόμησης στην Java;
Απάντηση: Ο αλγόριθμος ταξινόμησης μπορεί να οριστεί ως αλγόριθμος ή διαδικασία με την οποία τα στοιχεία μιας συλλογής μπορούν να ταξινομηθούν ή να τακτοποιηθούν με τον επιθυμητό τρόπο.
Παρακάτω δίνονται μερικοί από τους αλγόριθμους ταξινόμησης που υποστηρίζονται στο Java:
- Ταξινόμηση φυσαλίδων
- Είδος εισαγωγής
- Επιλογή είδους
- Συγχώνευση ταξινόμησης
- Γρήγορη ταξινόμηση
- Radix είδος
- Χάψορτ
Q # 2) Ποιος είναι ο καλύτερος αλγόριθμος ταξινόμησης στην Java;
Απάντηση: Το Merge Sort υποτίθεται ότι είναι ο ταχύτερος αλγόριθμος ταξινόμησης στην Java. Στην πραγματικότητα, το Java 7 έχει χρησιμοποιήσει εσωτερικά το είδος συγχώνευσης για να εφαρμόσει τη μέθοδο Collections.sort (). Το Quick Sort είναι επίσης ένας άλλος καλύτερος αλγόριθμος ταξινόμησης.
Q # 3) Τι είναι το είδος Bubble στην Java;
Απάντηση: Το Bubble sort είναι ο απλούστερος αλγόριθμος στην Java. Το Bubble sort συγκρίνει πάντα δύο παρακείμενα στοιχεία στη λίστα και τα ανταλλάσσει αν δεν είναι στην επιθυμητή σειρά. Έτσι, στο τέλος κάθε επανάληψης ή περάσματος, το βαρύτερο στοιχείο διοχετεύεται στη σωστή του θέση.
Q # 4) Γιατί είναι το Bubble sort Nδύο;
Απάντηση: Για την εφαρμογή ταξινόμησης φυσαλίδων, χρησιμοποιούμε δύο για βρόχους.
ποιος είναι ο καλύτερος μετατροπέας mp3
Η συνολική δουλειά μετράται από:
Ποσό της εργασίας που πραγματοποιείται από τον εσωτερικό βρόχο * συνολικός αριθμός φορών που εκτελείται ο εξωτερικός βρόχος.
Για μια λίστα στοιχείων n, ο εσωτερικός βρόχος λειτουργεί για O (n) για κάθε επανάληψη. Ο εξωτερικός βρόχος τρέχει για επανάληψη O (n). Ως εκ τούτου, η συνολική εργασία που έγινε είναι O (n) * O (n) = O (nδύο)
Ερ # 15) Ποια είναι τα πλεονεκτήματα του είδους Bubble;
Απάντηση: Τα πλεονεκτήματα του Bubble Sort είναι τα εξής:
- Εύκολη κωδικοποίηση και κατανόηση.
- Απαιτούνται λίγες γραμμές κώδικα για την εφαρμογή του αλγορίθμου.
- Η ταξινόμηση γίνεται επιτόπου, δηλαδή δεν απαιτείται πρόσθετη μνήμη και συνεπώς δεν υπάρχει γενική μνήμη.
- Τα ταξινομημένα δεδομένα είναι άμεσα διαθέσιμα για επεξεργασία.
συμπέρασμα
Μέχρι στιγμής, συζητήσαμε τον αλγόριθμο ταξινόμησης Bubble Sort στην Java. Εξετάσαμε επίσης τον αλγόριθμο και λεπτομερή απεικόνιση της ταξινόμησης ενός πίνακα χρησιμοποιώντας την τεχνική Bubble Sort. Στη συνέχεια, εφαρμόσαμε το πρόγραμμα Java στο Bubble Sort.
Στο επόμενο σεμινάριο, θα συνεχίσουμε με τις άλλες τεχνικές ταξινόμησης στην Java.
=> Ελέγξτε ΟΛΑ τα Εκπαιδευτικά Java εδώ.
Συνιστώμενη ανάγνωση
- Επιλογή Ταξινόμησης σε Java - Αλγόριθμος & Παραδείγματα Ταξινόμησης Επιλογής
- Ταξινόμηση εισαγωγής σε Java - Αλγόριθμος και παραδείγματα εισαγωγής
- Ταξινόμηση φυσαλίδων σε C ++ με παραδείγματα
- Πώς να ταξινομήσετε μια σειρά σε Java - Tutorial με παραδείγματα
- Εκμάθηση μήκους σειράς Java με παραδείγματα κώδικα
- MongoDB Sort () Μέθοδος με παραδείγματα
- Unix Sort Command με Σύνταξη, Επιλογές και Παραδείγματα
- Java «αυτό» Λέξη-κλειδί: Εκμάθηση με παραδείγματα κώδικα