Βίντεο: Week 4 2024
Εδώ μπορείτε να μάθετε πώς λειτουργεί μία από τις πιο διαδεδομένες τεχνικές διαλογής στην Java. Αυτή η τεχνική ονομάζεται Quicksort, και είναι μια πολύ έξυπνη χρήση της υποτροπής.
Για τους περισσότερους από εμάς, υπολογίζοντας πώς οι αλγόριθμοι ταξινόμησης όπως η εργασία Quicksort είναι απλώς μια πνευματική άσκηση. Το API Java έχει ήδη ενσωματωθεί στην ταξινόμηση.
Η τεχνική Quicksort ταξινομεί μια σειρά τιμών χρησιμοποιώντας την επανάληψη. Τα βασικά του βήματα είναι έτσι:
-
Επιλέξτε μια αυθαίρετη τιμή που βρίσκεται μέσα στο εύρος τιμών στον πίνακα.
Αυτή η τιμή είναι το σημείο περιστροφής . Ο πιο συνηθισμένος τρόπος επιλογής του σημείου περιστροφής είναι η απλή επιλογή της πρώτης τιμής στη συστοιχία. Οι λαοί έχουν γράψει διδακτορικά διπλώματα με πιο εξελιγμένους τρόπους να επιλέξουν ένα σημείο περιστροφής που οδηγεί σε ταχύτερη διαλογή. Προσέξτε με τη χρήση του πρώτου στοιχείου στη συστοιχία.
-
Αλλάξτε τις τιμές στη συστοιχία έτσι ώστε όλες οι τιμές που είναι μικρότερες από το σημείο περιστροφής να βρίσκονται στην αριστερή πλευρά του πίνακα και όλες οι τιμές που είναι μεγαλύτερες ή ίσες με το σημείο περιστροφής βρίσκονται στη δεξιά πλευρά του πίνακα παράταξη.
Η τιμή στροφέα υποδεικνύει το όριο μεταξύ της αριστερής πλευράς και της δεξιάς πλευράς του πίνακα. Πιθανότατα δεν θα είναι νεκρό σημείο, αλλά αυτό δεν έχει σημασία. Αυτό το βήμα ονομάζεται διαίρεση , και η αριστερή και η δεξιά πλευρά των συστοιχιών είναι διαμερίσματα .
-
Τώρα αντιμετωπίστε το καθένα από τα δύο τμήματα της συστοιχίας ως ξεχωριστή συστοιχία και ξεκινήστε από το Βήμα 1 για αυτό το τμήμα.
Αυτό είναι το αναδρομικό κομμάτι του αλγορίθμου.
38 17 58 22 69 31 88 28 86 12
Εδώ το σημείο περιστροφής είναι 38 και η εργασία του βήματος διαμέρισης είναι η αναδιάταξη του πίνακα σε κάτι σαν αυτό: 17 12 22 28 31 38 88 69 86 58
Παρατηρήστε ότι οι τιμές παραμένουν εκτός λειτουργίας. Ωστόσο, ο πίνακας διαιρείται γύρω από την τιμή 38: Όλες οι τιμές που είναι μικρότερες από 38 είναι στα αριστερά των 38 και όλες οι τιμές που είναι μεγαλύτερες από 38 είναι δεξιά του 38.
Τώρα μπορείτε να διαιρέσετε σε δύο διαμερίσματα στην τιμή 38 και επαναλάβετε τη διαδικασία για κάθε πλευρά. Η ίδια τιμή pivot πηγαίνει με το αριστερό διαμέρισμα, έτσι το αριστερό διαμέρισμα είναι το εξής:
17 12 22 28 31 38
Αυτή τη φορά το βήμα κατανομής διαχωρίζει το 17 ως σημείο περιστροφής και αναδιατάσσει τα στοιχεία ως εξής: > 12 17 22 28 31 38
Όπως μπορείτε να δείτε, αυτό το τμήμα του πίνακα είναι ταξινομημένο τώρα.Δυστυχώς, η Quicksort δεν συνειδητοποιεί ότι σε αυτό το σημείο, γι 'αυτό χρειάζονται μερικές ακόμα αναδρομές για να είναι σίγουροι. Αλλά αυτή είναι η βασική διαδικασία.
