Κορυφαίες δομές δεδομένων και αλγόριθμοι στην Java που πρέπει να γνωρίζετε

Αν έπρεπε να διαλέξω το πιο σημαντικό θέμα στην ανάπτυξη λογισμικού, θα ήταν δομές δεδομένων και αλγόριθμοι. Μπορείτε να το θεωρήσετε ως το βασικό εργαλείο που είναι διαθέσιμο σε κάθε προγραμματιστή υπολογιστών. Κατά τον προγραμματισμό, χρησιμοποιούμε ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ για αποθήκευση και οργάνωση δεδομένων, και αλγόριθμοι για χειρισμό των δεδομένων σε αυτές τις δομές. Αυτό το άρθρο περιέχει μια λεπτομερή ανασκόπηση όλων των κοινών δομών και αλγορίθμων δεδομένων στο για να επιτρέψει στους αναγνώστες να είναι καλά εξοπλισμένοι.

Παρακάτω αναφέρονται τα θέματα που συζητούνται σε αυτό το άρθρο:

• Δομές δεδομένων σε Java
  • Γραμμικές δομές δεδομένων
  • Ιεραρχικές δομές δεδομένων
• Αλγόριθμοι σε Java
  • Αλγόριθμοι ταξινόμησης
  • Αναζήτηση αλγορίθμων

Δομές δεδομένων σε Java

Η δομή δεδομένων είναι ένας τρόπος αποθήκευσης και οργάνωσης δεδομένων σε έναν υπολογιστή, ώστε να μπορεί να χρησιμοποιηθεί αποτελεσματικά. Παρέχει ένα μέσο για την αποτελεσματική διαχείριση μεγάλων ποσοτήτων δεδομένων. Και οι αποδοτικές δομές δεδομένων είναι το κλειδί για το σχεδιασμό αποτελεσματικών αλγορίθμων.

Σεαυτό το άρθρο «Δομές δεδομένων και αλγόριθμοι στην Java», θα καλύψουμε βασικές δομές δεδομένων όπως:

• Γραμμικές δομές δεδομένων
  • Συνδεδεμένη λίστα
  • Στοίβες
  • Ουρές

• Ιεραρχικές δομές δεδομένων
  • Δυαδικά δέντρα
  • Πλήθος
  • Πίνακες κατακερματισμού

Ας δούμε κάθε ένα από αυτά.

Γραμμικές δομές δεδομένων στην Java

Γραμμικές δομές δεδομένων σε είναι εκείνα των οποίων τα στοιχεία είναι διαδοχικά και ταξινομημένα με τέτοιο τρόπο ώστε: υπάρχει μόνο ένα πρώτο στοιχείο και έχει μόνο ένα επόμενο στοιχείο , υπάρχει μόνο ένα τελευταίο στοιχείο και έχει μόνο ένα προηγούμενο στοιχείο , ενώ όλα τα άλλα στοιχεία έχουν Επόμενο και ένα προηγούμενος στοιχείο.

Πίνακες

Ενα πίνακας είναι μια γραμμική δομή δεδομένωνπου αντιπροσωπεύει μια ομάδα παρόμοιων στοιχείων, στα οποία έχει πρόσβαση το ευρετήριο. Το μέγεθος ενός πίνακα πρέπει να παρέχεται πριν από την αποθήκευση δεδομένων. Παρακάτω αναφέρονται οι ιδιότητες ενός πίνακα:

• Κάθε στοιχείο σε έναν πίνακα έχει τον ίδιο τύπο δεδομένων και έχει το ίδιο μέγεθος
• Τα στοιχεία του πίνακα αποθηκεύονται σε γειτονικές θέσεις μνήμης με το πρώτο στοιχείο να ξεκινά από τη μικρότερη θέση μνήμης
• Τα στοιχεία του πίνακα μπορούν να προσπελαστούν τυχαία
• Η δομή δεδομένων πίνακα δεν είναι εντελώς δυναμική

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

Συνδεδεμένη λίστα

ΠΡΟΣ ΤΟ είναι μια γραμμική δομή δεδομένων με τη συλλογή πολλαπλών κόμβων, όπου eΤο στοιχείο ach αποθηκεύει τα δικά του δεδομένα και έναν δείκτη στη θέση του επόμενου στοιχείου. Ο τελευταίος σύνδεσμος σε μια συνδεδεμένη λίστα δείχνει το μηδέν, υποδεικνύοντας το τέλος της αλυσίδας. Ένα στοιχείο σε μια συνδεδεμένη λίστα ονομάζεται a κόμβος . Ο πρώτος κόμβος ονομάζεται κεφάλι .Ο τελευταίος κόμβος ονομάζεταιο ουρά .

Τύποι συνδεδεμένης λίστας

Singly Linked List (Μονοκατευθυντική)

Διπλή συνδεδεμένη λίστα (αμφίδρομη)

Κυκλική συνδεδεμένη λίστα

Εδώ είναι ένα απλό παράδειγμα: Φανταστείτε μια συνδεδεμένη λίστα όπως μια αλυσίδα συνδετήρων που συνδέονται μεταξύ τους. Μπορείτε εύκολα να προσθέσετε ένα άλλο συνδετήρα πάνω ή κάτω. Είναι ακόμη γρήγορο να εισάγετε ένα στη μέση. Το μόνο που έχετε να κάνετε είναι απλώς να αποσυνδέσετε την αλυσίδα στη μέση, να προσθέσετε το νέο συνδετήρα και, στη συνέχεια, να επανασυνδέσετε το άλλο μισό. Μια συνδεδεμένη λίστα είναι παρόμοια.

Στοίβες

Σωρός, μια αφηρημένη δομή δεδομένων, είναι μια συλλογή από αντικείμενα που εισάγονται και αφαιρούνται σύμφωνα με το τελευταίο-σε-πρώτο-out (LIFO) αρχή. Τα αντικείμενα μπορούν να εισαχθούν σε μια στοίβα ανά πάσα στιγμή, αλλά μόνο το αντικείμενο που έχει εισαχθεί πρόσφατα (δηλαδή, «τελευταίο») μπορεί να αφαιρεθεί ανά πάσα στιγμή.Παρακάτω αναφέρονται οι ιδιότητες μιας στοίβας:

• Είναι μια λίστα παραγγελιών στην οποίαεισαγωγή και διαγραφή μπορεί να πραγματοποιηθεί μόνο στο ένα άκρο που ονομάζεται μπλουζα
• Αναδρομική δομή δεδομένων με δείκτη στο κορυφαίο του στοιχείο
• Ακολουθεί το τελευταίο-σε-πρώτο-out (LIFO) αρχή
• Υποστηρίζει δύο πιο θεμελιώδεις μεθόδους
  • push (e): Εισαγάγετε το στοιχείο e, στην κορυφή της στοίβας
  • pop (): Αφαιρέστε και επιστρέψτε το επάνω στοιχείο στη στοίβα

Πρακτικά παραδείγματα της στοίβας περιλαμβάνουν κατά την αντιστροφή μιας λέξης,για να ελέγξετε την ορθότητα του παρενθέσειςαλληλουχία,εφαρμογή της λειτουργικότητας πίσω σε προγράμματα περιήγησης και πολλά άλλα.

Ουρές

είναι επίσης ένας άλλος τύπος αφηρημένης δομής δεδομένων. Σε αντίθεση με μια στοίβα, η ουρά είναι μια συλλογή αντικειμένων που εισάγονται και αφαιρούνται σύμφωνα με το Πρώτο σε πρώτο (FIFO) αρχή. Δηλαδή, τα στοιχεία μπορούν να εισαχθούν ανά πάσα στιγμή, αλλά μόνο το στοιχείο που βρίσκεται στην ουρά το μεγαλύτερο μπορεί να αφαιρεθεί ανά πάσα στιγμή.Παρακάτω αναφέρονται ιδιότητες μιας ουράς:

• Συχνά αναφέρεται ως το Πρώτο σε πρώτο λίστα
• Υποστηρίζει δύο πιο θεμελιώδεις μεθόδους
  • enqueue (e): Εισαγάγετε το στοιχείο e, στο όπισθεν της ουράς
  • dequeue (): Αφαιρέστε και επιστρέψτε το στοιχείο από το εμπρός της ουράς

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

Ιεραρχικές δομές δεδομένων στην Ιάβα

Δυαδικό δέντρο

Το δυαδικό δέντρο είναι έναιεραρχικές δομές δεδομένων δένδρων στις οποίες κάθε κόμβος έχει το πολύ δύο παιδιά , που αναφέρονται ως αριστερό παιδί και το σωστό παιδί . Κάθε δυαδικό δέντρο έχει τις ακόλουθες ομάδες κόμβων:

• Root Node: Είναι ο κορυφαίος κόμβος και συχνά αναφέρεται ως ο κύριος κόμβοςγιατί όλοι οι άλλοι κόμβοι είναι προσβάσιμοι από τη ρίζα
• Αριστερό υπο-δέντρο, το οποίο είναι επίσης δυαδικό δέντρο
• Right Sub-Tree, το οποίο είναι επίσης δυαδικό δέντρο

Παρακάτω αναφέρονται οι ιδιότητες ενός δυαδικού δέντρου:

• Ένα δυαδικό δέντρο μπορεί να διασχιστεί με δύο τρόπους:
  • Πρώτο πέρασμα βάθους : Σε σειρά (Αριστερή-Ρίζα-Δεξιά), Προπαραγγελία (Root-Left-Right) και Postorder (Left-Right-Root)
  • Πρώτο πέρασμα Breadth : Διαδρομή επιπέδου στάθμης
• Χρόνος πολυπλοκότητας της διέλευσης δέντρων: O (n)
• Ο μέγιστος αριθμός κόμβων στο επίπεδο «l» = 2^l-1.

Οι εφαρμογές δυαδικών δέντρων περιλαμβάνουν:

• Χρησιμοποιείται σε πολλές εφαρμογές αναζήτησης όπου τα δεδομένα εισέρχονται / εξέρχονται συνεχώς
• Ως ροή εργασίας για τη σύνθεση ψηφιακών εικόνων για οπτικά εφέ
• Χρησιμοποιείται σχεδόν σε κάθε δρομολογητή υψηλού εύρους ζώνης για αποθήκευση πινάκων δρομολογητών
• Χρησιμοποιείται επίσης σε ασύρματη δικτύωση και κατανομή μνήμης
• Χρησιμοποιείται σε αλγόριθμους συμπίεσης και πολλά άλλα

Δυαδικός σωρός

Το Binary Heap είναι πλήρεςδυαδικό δέντρο, που απαντά στην ιδιότητα σωρού. Με απλούς όρουςείναι μια παραλλαγή ενός δυαδικού δέντρου με τις ακόλουθες ιδιότητες:

• Ο σωρός είναι ένα πλήρες δυαδικό δέντρο: Ένα δέντρο λέγεται ότι είναι πλήρες εάν όλα τα επίπεδα, εκτός από το βαθύτερο, είναι πλήρες. Τη ιδιοκτησία του Binary Heap το καθιστά κατάλληλο για αποθήκευση σε .
• Ακολουθεί την ιδιότητα σωρού: Ο δυαδικός σωρός είναι είτε α Ελάχιστο σωρό ή α Μέγιστο σωρό .
  • Ελάχιστο δυαδικό σωρό: ΣΤή κάθε κόμβος σε έναν σωρό, η τιμή του κόμβου είναι μικρότερο από ή ίσο με αξίες των παιδιών
  • Μέγιστο δυαδικό σωρό: Fή κάθε κόμβος σε έναν σωρό, η τιμή του κόμβου είναι μεγαλύτερο ή ίσο με αξίες των παιδιών

Οι δημοφιλείς εφαρμογές του δυαδικού σωρού περιλαμβάνουνεφαρμόζοντας αποτελεσματικές ουρές προτεραιότητας, βρίσκοντας αποτελεσματικά τα k μικρότερα (ή μεγαλύτερα) στοιχεία σε έναν πίνακα και πολλά άλλα.

Πίνακες κατακερματισμού

Φανταστείτε ότι έχετε ένα αντικείμενο και θέλετε να εκχωρήσετε ένα κλειδί για να κάνετε την αναζήτηση πολύ εύκολη. Για να αποθηκεύσετε αυτό το ζεύγος κλειδιών / τιμών, μπορείτε να χρησιμοποιήσετε έναν απλό πίνακα όπως μια δομή δεδομένων όπου τα κλειδιά (ακέραιοι αριθμοί) μπορούν να χρησιμοποιηθούν απευθείας ως ευρετήριο για την αποθήκευση τιμών δεδομένων. Ωστόσο, σε περιπτώσεις όπου τα πλήκτρα είναι πολύ μεγάλα και δεν μπορούν να χρησιμοποιηθούν απευθείας ως ευρετήριο, χρησιμοποιείται μια τεχνική που ονομάζεται κατακερματισμός.

Στο κατακερματισμό, τα μεγάλα πλήκτρα μετατρέπονται σε μικρά πλήκτρα χρησιμοποιώντας λειτουργίες κατακερματισμού . Οι τιμές στη συνέχεια αποθηκεύονται σε μια δομή δεδομένων που ονομάζεταιπρος το πίνακας κατακερματισμού. Ένας πίνακας κατακερματισμού είναι μια δομή δεδομένων που εφαρμόζει ένα λεξικό ADT, μια δομή που μπορεί να αντιστοιχίσει μοναδικά κλειδιά σε τιμές.

Γενικά, ένας πίνακας κατακερματισμού έχει δύο βασικά στοιχεία:

1. Διάταξη κάδου: Ένας πίνακας κάδου για έναν πίνακα κατακερματισμού είναι ένας πίνακας Α μεγέθους Ν, όπου κάθε κελί του Α θεωρείται ως 'κάδος', δηλαδή μια συλλογή ζευγών κλειδιών-τιμών. Ο ακέραιος Ν ορίζει την χωρητικότητα του πίνακα.
2. Λειτουργία Hash: Είναι οποιαδήποτε λειτουργία που αντιστοιχίζει κάθε πλήκτρο k στον χάρτη μας σε ακέραιο αριθμό στην περιοχή [0, N & μείον 1], όπου N είναι η χωρητικότητα του πίνακα κάδων για αυτόν τον πίνακα.

Όταν τοποθετούμε αντικείμενα σε hashtable, είναι πιθανό διαφορετικά αντικείμενα να έχουν τον ίδιο κωδικό κατακερματισμού. Αυτό ονομάζεται a σύγκρουση . Για την αντιμετώπιση της σύγκρουσης, υπάρχουν τεχνικές όπως η αλυσίδα και η ανοιχτή αντιμετώπιση.

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

Αλγόριθμοι σε Java

Ιστορικά χρησιμοποιείται ως εργαλείο για την επίλυση πολύπλοκων μαθηματικών υπολογισμών, οι αλγόριθμοι συνδέονται βαθιά με την επιστήμη των υπολογιστών και ειδικότερα με τις δομές δεδομένων. Ένας αλγόριθμος είναι μια ακολουθία οδηγιών που περιγράφει έναν τρόπο επίλυσης ενός συγκεκριμένου προβλήματος σε μια πεπερασμένη χρονική περίοδο. Αντιπροσωπεύονται με δύο τρόπους:

• Διαγράμματα ροής - Είναι έναοπτική αναπαράσταση της ροής ελέγχου ενός αλγορίθμου
• Ψευδοκώδικας - Αυτόείναι μια αναπαράσταση κειμένου ενός αλγορίθμου που προσεγγίζει τον τελικό πηγαίο κώδικα

Σημείωση: Η απόδοση του αλγορίθμου μετριέται με βάση την πολυπλοκότητα του χρόνου και την πολυπλοκότητα του χώρου. Κυρίως, η πολυπλοκότητα οποιουδήποτε αλγορίθμου εξαρτάται από το πρόβλημα και από τον ίδιο τον αλγόριθμο.

Ας εξερευνήσουμε τις δύο κύριες κατηγορίες αλγορίθμων στην Java, οι οποίες είναι:

• Ταξινόμηση αλγορίθμων σε Java
• Αναζήτηση αλγορίθμων σε Java

Ταξινόμηση αλγορίθμων σε Java

Οι αλγόριθμοι ταξινόμησης είναι αλγόριθμοι που τοποθετούν στοιχεία μιας λίστας σε συγκεκριμένη σειρά. Οι παραγγελίες που χρησιμοποιούνται συχνότερα είναι αριθμητική σειρά και λεξικογραφική σειρά. Σε αυτό το άρθρο «Δομές δεδομένων και αλγόριθμοι» μπορείτε να εξερευνήσετε μερικούς αλγόριθμους ταξινόμησης.

Ταξινόμηση φυσαλίδων στην Ιάβα

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

Εδώ είναιΨευδοκώδικας που αντιπροσωπεύει Αλγόριθμο Ταξινόμησης Bubble (ανερχόμενο περιβάλλον ταξινόμησης).

a [] είναι ένας πίνακας μεγέθους N ξεκινήστε BubbleSort (a []) δηλώστε ακέραιο i, j για i = 0 έως N - 1 για j = 0 έως N - i - 1 εάν ένα [j]> a [j + 1 ] στη συνέχεια, ανταλλάξτε ένα [j], ένα [j + 1] τέλος αν τελειώσετε για να επιστρέψετε ένα τέλος BubbleSort

Αυτός ο κωδικός παραγγέλνει μια μονοδιάστατη σειρά στοιχείων δεδομένων Ν σε αύξουσα σειρά. Ένας εξωτερικός βρόχος κάνει το Ν-1 να περνά πάνω από τον πίνακα. Κάθε πάσο χρησιμοποιεί έναν εσωτερικό βρόχο για να ανταλλάσσει στοιχεία δεδομένων έτσι ώστε το επόμενο μικρότερο στοιχείο δεδομένων «φυσαλίδες» προς την αρχή του πίνακα. Αλλά το πρόβλημα είναι ότι ο αλγόριθμος χρειάζεται ένα ολόκληρο πέρασμα χωρίς ανταλλαγή για να γνωρίζει ότι η λίστα είναι ταξινομημένη.

Χειρότερη και μέση πολυπλοκότητα χρόνου υπόθεσης: O (n * n). Η χειρότερη περίπτωση εμφανίζεται όταν μια σειρά αντιστρέφεται.

Καλύτερη πολυπλοκότητα χρόνου περιπτώσεων: Επί). Η καλύτερη περίπτωση εμφανίζεται όταν έχει ήδη ταξινομηθεί ένας πίνακας.

Επιλογή Ταξινόμηση σε Java

Η επιλογή ταξινόμησης είναι ένας συνδυασμός αναζήτησης και ταξινόμησης. Ο αλγόριθμος ταξινομεί έναν πίνακα με την επανειλημμένη εύρεση του ελάχιστου στοιχείου (εξετάζοντας την αύξουσα σειρά) από το μη ταξινομημένο τμήμα και τοποθετώντας τον σε μια σωστή θέση στον πίνακα.

Εδώ είναι ο ψευδοκώδικας που αντιπροσωπεύει τον αλγόριθμο επιλογής ταξινόμησης (αύξουσα ταξινόμηση περιβάλλοντος).

a [] είναι ένας πίνακας μεγέθους N start SelectionSort (a []) για i = 0 έως n - 1 / * ορίστε το τρέχον στοιχείο ως ελάχιστο * / min = i / * βρείτε το ελάχιστο στοιχείο * / για j = i + 1 στο n αν η λίστα [j]
Όπως μπορείτε να καταλάβετε από τον κώδικα, ο αριθμός των φορών που περνά η ταξινόμηση μέσω του πίνακα είναι μικρότερος από τον αριθμό των στοιχείων στον πίνακα. Ο εσωτερικός βρόχος βρίσκει την επόμενη μικρότερη τιμή και ο εξωτερικός βρόχος τοποθετεί αυτήν την τιμή στη σωστή του θέση. Το είδος επιλογής δεν κάνει ποτέ περισσότερα από τα ανταλλακτικά O (n) και μπορεί να είναι χρήσιμο όταν η εγγραφή μνήμης είναι μια δαπανηρή λειτουργία.
 Χρόνος πολυπλοκότητας: Επί2) καθώς υπάρχουν δύο ένθετοι βρόχοι.
 Βοηθητικός χώρος: Ή (1).
 Ταξινόμηση εισαγωγής σε Java 
Το Insertion Sort είναι ένας απλός αλγόριθμος ταξινόμησης που επαναλαμβάνει τη λίστα με την κατανάλωση ενός στοιχείου εισόδου κάθε φορά και δημιουργεί τον τελικό πίνακα ταξινόμησης. Είναι πολύ απλό και πιο αποτελεσματικό σε μικρότερα σύνολα δεδομένων. Είναι σταθερή και επιτόπια τεχνική διαλογής.
Εδώ είναι ο ψευδοκώδικας που αντιπροσωπεύει τον αλγόριθμο εισαγωγής ταξινόμησης (αύξουσα ταξινόμηση περιβάλλοντος).
a [] είναι ένας πίνακας μεγέθους N start InsertionSort (a []) for i = 1 to N key = a [i] j = i - 1 while (j> = 0 and a [j]> key0 a [j + 1] = x [j] j = j - 1 τέλος ενώ ένα [j + 1] = τέλος κλειδιού για το τέλος InsertionSort
Όπως μπορείτε να καταλάβετε από τον κώδικα, ο αλγόριθμος ταξινόμησης εισαγωγήςαφαιρεί ένα στοιχείο από τα δεδομένα εισαγωγής, βρίσκει τη θέση στην οποία ανήκει στη λίστα ταξινόμησης και το εισάγει εκεί. Επαναλαμβάνεται έως ότου κανένα στοιχείο εισόδου δεν παραμένει ταξινομημένο.
 Καλύτερη περίπτωση: Η καλύτερη περίπτωση είναι όταν η είσοδος είναι ένας πίνακας που έχει ήδη ταξινομηθεί. Σε αυτήν την περίπτωση, το είδος εισαγωγής έχει γραμμικό χρόνο εκτέλεσης (δηλαδή, & Theta (n)).
 Χειρότερη περίπτωση:  Η απλούστερη χειρότερη περίπτωση είναι ένας πίνακας ταξινομημένος με αντίστροφη σειρά.
 QuickSort σε Java 
Ο αλγόριθμος Quicksort είναι ένας γρήγορος, αναδρομικός, μη σταθερός αλγόριθμος ταξινόμησης που λειτουργεί σύμφωνα με την αρχή διαίρεσης και κατάκτησης. Διαλέγει ένα στοιχείο ως άξονα και χωρίζει τον δεδομένο πίνακα γύρω από αυτόν τον επιλεγμένο άξονα.
 Βήματα για την εφαρμογή Γρήγορης ταξινόμησης:  
 
Διαλέξτε ένα κατάλληλο 'σημείο περιστροφής'.
Χωρίστε τις λίστες σε δύο λίστεςμε βάση αυτό το στοιχείο περιστροφής. Κάθε στοιχείο που είναι μικρότερο από το στοιχείο περιστροφής τοποθετείται στην αριστερή λίστα και κάθε στοιχείο που είναι μεγαλύτερο τοποθετείται στη δεξιά λίστα. Εάν ένα στοιχείο είναι ίσο με το στοιχείο περιστροφής, τότε μπορεί να συμπεριληφθεί σε οποιαδήποτε λίστα. Αυτό ονομάζεται λειτουργία διαμέρισης.
Ταξινομήστε αναδρομικά κάθε μία από τις μικρότερες λίστες. 
Εδώ είναι ο ψευδοκώδικας που αντιπροσωπεύει τον αλγόριθμο Quicksort.
QuickSort (Α ως πίνακας, χαμηλή ως int, υψηλή ως int) {εάν (χαμηλή
Στον παραπάνω ψευδοκώδικα, χώρισμα() Η λειτουργία εκτελεί λειτουργία διαμέρισης και Γρήγορη ταξινόμηση() Η λειτουργία καλεί επανειλημμένα τη λειτουργία διαμέρισης για κάθε μικρότερη λίστα που δημιουργείται. Η πολυπλοκότητα της γρήγορης ταξινόμησης στη μέση περίπτωση είναι & Theta (n log (n)) και στη χειρότερη περίπτωση είναι & Theta (n2).
 Συγχώνευση ταξινόμησης σε Java 
Το Mergesort είναι ένας γρήγορος, αναδρομικός, σταθερός αλγόριθμος που λειτουργεί επίσης σύμφωνα με την αρχή διαίρεση και κατάκτηση. Παρόμοια με το quicksort, η συγχώνευση ταξινομεί τη λίστα στοιχείων σε δύο λίστες. Αυτές οι λίστες ταξινομούνται ανεξάρτητα και στη συνέχεια συνδυάζονται. Κατά τη διάρκεια του συνδυασμού των λιστών, τα στοιχεία εισάγονται (ή συγχωνεύονται) στη σωστή θέση στη λίστα.
Εδώ είναι ο ψευδοκώδικας που αντιπροσωπεύει τον αλγόριθμο συγχώνευσης ταξινόμησης.
διαδικασία MergeSort (a ως array) εάν (n == 1) επιστρέψει ένα var l1 ως array = a [0] ... a [n / 2] var l2 as array = a [n / 2 + 1] ... a [n] l1 = mergesort (l1) l2 = mergesort (l2) return merge (l1, l2) end prosedur διαδικασίας συγχώνευσης (a ως array, b as array) var c ως array ενώ (a και b έχουν στοιχεία) εάν ( a [0]> b [0]) προσθέστε b [0] στο τέλος του c αφαιρέστε b [0] από b αλλιώς προσθέστε ένα [0] στο τέλος του c αφαιρέστε ένα [0] από το τέλος εάν τελειώσει ενώ (a έχει στοιχεία) προσθέστε ένα [0] στο τέλος του c αφαιρέστε ένα [0] από το τέλος ενώ ενώ (b έχει στοιχεία) προσθέστε b [0] στο τέλος του c αφαιρέστε το b [0] από το b τέλος ενώ επιστρέφετε γ τελική διαδικασία
 mergesort () Η συνάρτηση χωρίζει τη λίστα σε δύο, κλήσεις mergesort () σε αυτές τις λίστες ξεχωριστά και στη συνέχεια τις συνδυάζει στέλνοντάς τις ως παραμέτρους για συγχώνευση ().Ο αλγόριθμος έχει πολυπλοκότητα του O (n log (n)) και έχει ένα ευρύ φάσμα εφαρμογών.
 Ταξινόμηση σωρού στην Ιάβα 
Το Heapsort είναι ένας αλγόριθμος ταξινόμησης που βασίζεται σε σύγκρισηΔομή δεδομένων δυαδικού σωρού. Μπορείτε να το θεωρήσετε ως βελτιωμένη έκδοση για την επιλογή, όπουδιαιρεί την είσοδό του σε μια ταξινομημένη και μια μη ταξινομημένη περιοχή και συρρικνώνει επαναληπτικά την μη ταξινομημένη περιοχή εξάγοντας το μεγαλύτερο στοιχείο και μετακινώντας την στην ταξινομημένη περιοχή.
 Βήματα για την εφαρμογή του Quicksort (σε αυξανόμενη σειρά): 
Δημιουργήστε έναν μέγιστο σωρό με τον πίνακα ταξινόμησης
Σε αυτά τα σημείαt, το μεγαλύτερο αντικείμενο αποθηκεύεται στη ρίζα του σωρού. Αντικαταστήστε το με το τελευταίο στοιχείο του σωρού και μειώστε το μέγεθος του σωρού κατά 1. Τέλος, heapify η ρίζα του δέντρου
Επαναλάβετε τα παραπάνω βήματα μέχρι το μέγεθος του σωρού να είναι μεγαλύτερο από 1
Εδώ είναι ο ψευδοκώδικας που αντιπροσωπεύει τον αλγόριθμο Heap Sort.
Heapsort (a ως πίνακας) για (i = n / 2 - 1) έως i> = 0 heapify (a, n, i) για i = n-1 έως 0 swap (a [0], a [i]) heapify (a, i, 0) end for end για heapify (a ως πίνακας, n ως int, i ως int) μεγαλύτερο = i // Αρχικοποιήστε το μεγαλύτερο ως root int l eft = 2 * i + 1 // αριστερά = 2 * i + 1 int δεξιά = 2 * i + 2 // δεξιά = 2 * i + 2 εάν (αριστερά ένα [μεγαλύτερο]) μεγαλύτερο = αριστερά εάν (δεξιά ένα [μεγαλύτερο]) μεγαλύτερο = δεξιά εάν (μεγαλύτερο! = I) ανταλλαγή ( a [i], A [μεγαλύτερο]) Heapify (a, n, μεγαλύτερο) τέλος heapify
Εκτός από αυτούς, υπάρχουν και άλλοι αλγόριθμοι ταξινόμησης που δεν είναι τόσο γνωστοί, όπως, Introsort, Counting Sort κ.λπ.
 Αναζήτηση αλγορίθμων σε Java 
Η αναζήτηση είναι μια από τις πιο κοινές και συχνές ενέργειες σε κανονικές επιχειρηματικές εφαρμογές. Οι αλγόριθμοι αναζήτησης είναι αλγόριθμοι για την εύρεση ενός αντικειμένου με καθορισμένες ιδιότητες μεταξύ μιας συλλογής αντικειμένων. Ας εξερευνήσουμε δύο από τους πιο συχνά χρησιμοποιούμενους αλγόριθμους αναζήτησης.
 Γραμμικός αλγόριθμος αναζήτησης σε Java 
Η γραμμική αναζήτηση ή η διαδοχική αναζήτηση είναι ο απλούστερος αλγόριθμος αναζήτησης. Περιλαμβάνει διαδοχική αναζήτηση ενός στοιχείου στη δεδομένη δομή δεδομένων έως ότου βρεθεί το στοιχείο ή φτάσει στο τέλος της δομής. Αν το στοιχείο βρεθεί, τότε η θέση του αντικειμένου επιστρέφεται διαφορετικά ο αλγόριθμος επιστρέφει NULL.
Εδώ είναι ο ψευδοκώδικας που αντιπροσωπεύει τη Γραμμική αναζήτηση σε Java:
καλέστε με αναφορά στο c ++
διαδικασία linear_search (a [], value) για i = 0 έως n-1 αν a [i] = value τότε print 'Found' return i end if print 'Not found' end for end linear_search
Είναι ένααλγόριθμος brute-force.Αν και είναι σίγουρα το πιο απλό, σίγουρα δεν είναι το πιο κοινό, λόγω της αναποτελεσματικότητάς του. Ο χρόνος πολυπλοκότητας της γραμμικής αναζήτησης είναι ΕΠΙ) .
 Δυαδικός αλγόριθμος αναζήτησης στην Ιάβα 
Η δυαδική αναζήτηση, επίσης γνωστή ως λογαριθμική αναζήτηση, είναι ένας αλγόριθμος αναζήτησης που βρίσκει τη θέση μιας τιμής στόχου μέσα σε έναν ήδη ταξινομημένο πίνακα. Χωρίζει τη συλλογή εισόδου σε ίσα μισά και το στοιχείο συγκρίνεται με το μεσαίο στοιχείο της λίστας. Εάν το στοιχείο βρεθεί, η αναζήτηση τελειώνει εκεί. Διαφορετικά, συνεχίζουμε να ψάχνουμε το στοιχείο διαιρώντας και επιλέγοντας το κατάλληλο διαμέρισμα του πίνακα, με βάση το εάν το στοιχείο στόχος είναι μικρότερο ή μεγαλύτερο από το μεσαίο στοιχείο.
Ακολουθεί ο ψευδοκώδικας που αντιπροσωπεύει τη δυαδική αναζήτηση στην Java:
Διαδικασία binary_search a sorted array n size of array x value to searchedBound = 1 upperBound = n ενώ x not found if upperBound
Η αναζήτηση τερματίζεται όταν το upperBound (ο δείκτης μας) περνά από το LowerBound (τελευταίο στοιχείο), πράγμα που σημαίνει ότι έχουμε πραγματοποιήσει αναζήτηση σε ολόκληρο τον πίνακα και το στοιχείο δεν υπάρχει.Είναι οι πιο συχνά χρησιμοποιούμενοι αλγόριθμοι αναζήτησης κυρίως λόγω του γρήγορου χρόνου αναζήτησης. Η χρονική πολυπλοκότητα της δυαδικής αναζήτησης είναι ΕΠΙ) που είναι μια σημαντική βελτίωση στο ΕΠΙ) χρονική πολυπλοκότητα της γραμμικής αναζήτησης.
Αυτό μας φέρνει στο τέλος αυτού του άρθρου «Δομές δεδομένων και αλγόριθμοι σε Java». Έχω καλύψει ένα από τα πιο θεμελιώδη και σημαντικά θέματα της Java.Ελπίζω να είστε ξεκάθαροι με όλα όσα έχουν κοινοποιηθεί σε εσάς σε αυτό το άρθρο.
  Βεβαιωθείτε ότι ασκείστε όσο το δυνατόν περισσότερο και επαναφέρετε την εμπειρία σας.   
 Δείτε το    από την Edureka, μια αξιόπιστη διαδικτυακή εταιρεία εκμάθησης με δίκτυο περισσότερων από 250.000 ικανοποιημένων μαθητών σε όλο τον κόσμο. Είμαστε εδώ για να σας βοηθήσουμε σε κάθε βήμα του ταξιδιού σας, για να γίνετε εκτός από αυτές τις ερωτήσεις της συνέντευξης java, έχουμε ένα πρόγραμμα σπουδών που έχει σχεδιαστεί για φοιτητές και επαγγελματίες που θέλουν να γίνουν προγραμματιστές Java. 
 Έχετε μια ερώτηση για εμάς; Παρακαλώ αναφέρετέ το στην ενότητα σχολίων αυτού του «Δομές δεδομένων και αλγόριθμοι στην Java»  άρθρο και θα επικοινωνήσουμε μαζί σας το συντομότερο δυνατό.