Γρήγορη ταξινόμηση σε Java επεξηγείται

Σύμβαση κατά το ήμισυ

Όταν ο αριθμός των στοιχείων σε μια λίστα είναι ζυγός, το ήμισυ της λίστας σημαίνει ότι το κυριολεκτικό πρώτο μισό της λίστας είναι το πρώτο μισό και το κυριολεκτικό δεύτερο μισό της λίστας είναι το δεύτερο μισό. Το μεσαίο (μεσαίο) στοιχείο ολόκληρης της λίστας, είναι το τελευταίο στοιχείο της πρώτης λίστας. Αυτό σημαίνει ότι ο μεσαίος δείκτης είναι μήκος / 2 - 1, καθώς η καταμέτρηση του δείκτη ξεκινά από το μηδέν. Το μήκος είναι ο αριθμός των στοιχείων στη λίστα. Για παράδειγμα, εάν ο αριθμός των στοιχείων είναι 8, τότε το πρώτο μισό της λίστας έχει 4 στοιχεία και το δεύτερο μισό της λίστας έχει επίσης 4 στοιχεία. Αυτό είναι εντάξει. Δεδομένου ότι η καταμέτρηση του δείκτη ξεκινά από το 0, ο μέσος δείκτης είναι 3 = 8 /2 - 1.

Τι γίνεται με την περίπτωση, όταν ο αριθμός των στοιχείων στη λίστα ή υπο-λίστα είναι περιττός; Στην αρχή, το μήκος εξακολουθεί να διαιρείται με 2. Κατά συνθήκη, ο αριθμός των στοιχείων στο πρώτο μισό αυτής της διαίρεσης είναι μήκος / 2 + 1/2. Η καταμέτρηση του δείκτη ξεκινά από το μηδέν. Ο μεσαίος δείκτης δίνεται κατά μήκος / 2 - 1/2. Αυτό θεωρείται ως μεσοπρόθεσμος, κατά σύμβαση. Για παράδειγμα, εάν ο αριθμός των στοιχείων σε μια λίστα είναι 5, τότε ο μεσαίος δείκτης είναι 2 = 5/2 - 1/2. Και, υπάρχουν τρία στοιχεία στο πρώτο μισό της λίστας και δύο στοιχεία στο δεύτερο μισό. Το μεσαίο στοιχείο ολόκληρης της λίστας είναι το τρίτο στοιχείο στο ευρετήριο, 2, το οποίο είναι το μεσαίο ευρετήριο επειδή η καταμέτρηση του δείκτη ξεκινά από το 0.

Η διαίρεση με αυτόν τον τρόπο είναι ένα παράδειγμα ακέραιας αριθμητικής.

Μέση τιμή τριών αξιών

Ερώτηση: Ποια είναι η διάμεσος της ακολουθίας:

Γ Β Α

Λύση:
Τακτοποιήστε τη λίστα με αύξουσα σειρά:

Α Β Γ

Ο μεσαίος όρος, Β, είναι ο διάμεσος. Είναι το μέγεθος που βρίσκεται ανάμεσα στα άλλα δύο μεγέθη.

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

Με τη Γρήγορη Ταξινόμηση, απαιτείται η μέση τιμή για ολόκληρη τη λίστα και τις υπο-λίστες. Ο ψευδοκώδικας για να αναζητήσετε τη διάμεσο των τριών τιμών που απέχουν σε μια λίστα (πίνακας) είναι:

Ο όρος arr σημαίνει πίνακας. Αυτό το τμήμα κώδικα αναζητά τη διάμεσο και κάνει επίσης κάποια ταξινόμηση. Αυτό το τμήμα κώδικα φαίνεται απλό, αλλά μπορεί να είναι αρκετά μπερδεμένο. Λοιπόν, δώστε προσοχή στην ακόλουθη εξήγηση:

Η ταξινόμηση σε αυτό το σεμινάριο θα παράγει μια λίστα όπου η πρώτη τιμή είναι η μικρότερη τιμή και η τελευταία τιμή είναι η μεγαλύτερη τιμή. Με το αλφάβητο, το Α είναι μικρότερο από το Ζ.

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

Έτσι, ο διάμεσος που πρέπει να ληφθεί είναι μεταξύ της τιμής του χαμηλότερου δείκτη, της τιμής του μεσαίου δείκτη και της τιμής του υψηλότερου δείκτη.

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

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

Γ Β Α

Γνωρίζουμε ήδη ότι ο διάμεσος είναι ο Β. Ωστόσο, αυτό πρέπει να αποδειχθεί. Ο στόχος εδώ είναι να λάβουμε τη διάμεσο αυτών των τριών τιμών χρησιμοποιώντας το παραπάνω τμήμα κώδικα. Η πρώτη αν-δήλωση συγκρίνει τα Β και Γ. Αν το Β είναι μικρότερο από το Γ, τότε οι θέσεις των Β και Γ πρέπει να αλλάξουν. Το Β είναι μικρότερο από το C, οπότε η νέα διάταξη γίνεται:

Β Γ Α

Σημειώστε ότι οι τιμές για τον χαμηλότερο και τον μεσαίο δείκτη έχουν αλλάξει. Η δεύτερη αν-δήλωση συγκρίνει τα Α και Β. Εάν το Α είναι μικρότερο από το Β, τότε οι θέσεις των Α και Β πρέπει να αλλάξουν. Το A είναι μικρότερο από το B, οπότε η νέα διάταξη γίνεται:

Α Γ Β

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

Α Γ Β

Το Β είναι ο διάμεσος, δηλαδή ο Α [ψηλός], και είναι ο άξονας περιστροφής. Έτσι, ο άξονας γεννιέται στο ακραίο τέλος της λίστας ή της υπο-λίστας.

Η λειτουργία ανταλλαγής

Ένα άλλο χαρακτηριστικό που χρειάζεται το Quick Sort είναι η λειτουργία ανταλλαγής. Η συνάρτηση εναλλαγής, ανταλλάσσει τις τιμές δύο μεταβλητών. Ο ψευδοκώδικας για τη λειτουργία ανταλλαγής είναι:

Εδώ, τα x και y αναφέρονται στις πραγματικές τιμές και όχι στα αντίγραφα.

Η ταξινόμηση σε αυτό το άρθρο θα παράγει μια λίστα όπου η πρώτη τιμή είναι η μικρότερη τιμή και η τελευταία τιμή είναι η μεγαλύτερη τιμή.

Περιεχόμενο άρθρου

• Αλγόριθμος γρήγορης ταξινόμησης
• Partευδοκώδικας διαμερίσματος
• Εικονογράφηση της γρήγορης ταξινόμησης
• Κωδικοποίηση Java
• συμπέρασμα

Αλγόριθμος γρήγορης ταξινόμησης

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

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

Τα βήματα για τον αλγόριθμο quicksort έχουν ως εξής:

1. Βεβαιωθείτε ότι υπάρχουν τουλάχιστον 2 αριθμοί για ταξινόμηση στη λίστα χωρίς ταξινόμηση.
2. Λάβετε μια εκτιμώμενη κεντρική τιμή για τη λίστα, που ονομάζεται περιστροφική. Ο διάμεσος, όπως περιγράφηκε παραπάνω, είναι ένας τρόπος απόκτησης του άξονα. Διαφορετικοί τρόποι έρχονται με τα πλεονεκτήματα και τα μειονεκτήματά τους. - Δείτε αργότερα.
3. Διαμερίστε τη λίστα. Αυτό σημαίνει, τοποθετήστε τον άξονα περιστροφής στη λίστα. Με αυτόν τον τρόπο, όλα τα στοιχεία στα αριστερά είναι μικρότερα από την τιμή περιστροφής και όλα τα στοιχεία στα δεξιά είναι μεγαλύτερα ή ίσα με την τιμή περιστροφής. Υπάρχουν διάφοροι τρόποι καταμερισμού. Κάθε μέθοδος διαμερίσματος έχει τα πλεονεκτήματα και τα μειονεκτήματά της. Ο διαχωρισμός χωρίζεται στο παράδειγμα διαίρει και κατακτά.
4. Επαναλάβετε τα βήματα 1, 2 και 3 αναδρομικά για τα νέα ζεύγη υπο-λίστας που εμφανίζονται μέχρι να ταξινομηθεί ολόκληρη η λίστα. Αυτό είναι κατακτητικό στο παράδειγμα διαίρει και κατακτά.

Ο ψευδοκώδικας Quick Sort είναι:

Partευδοκώδικας διαμερίσματος

Ο ψευδοκώδικας διαμερίσματος που χρησιμοποιείται σε αυτό το σεμινάριο είναι:

Στην εικόνα του Quick Sort παρακάτω, χρησιμοποιείται αυτός ο κωδικός:

Εικονογράφηση της γρήγορης ταξινόμησης

Εξετάστε την ακόλουθη μη ταξινομημένη λίστα (πίνακας) αλφαβητικών γραμμάτων:

Q W E R T Y U I P

Κατά επιθεώρηση, η ταξινομημένη λίστα είναι:

E I O P Q R T U W Y

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

Q W E R T Y U I P

Ο πρώτος άξονας προσδιορίζεται από arr [0] = Q, arr [4] = T, και arr [9] = P, και προσδιορίζεται ως Q και τοποθετείται στην άκρη δεξιά της λίστας. Έτσι, η λίστα με οποιαδήποτε ταξινόμηση συνάρτησης περιστροφής γίνεται:

P W E R T Y U I O Q

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

Οι χαμηλοί και υψηλοί δείκτες είναι τώρα 0 και 9. Έτσι, ο υπολογιστής θα ξεκινήσει με σάρωση από το ευρετήριο 0 έως ότου φτάσει σε έναν δείκτη, του οποίου η τιμή είναι ίση ή μεγαλύτερη από τον περιστροφικό και σταματά εκεί προσωρινά. Θα σαρώσει επίσης από το υψηλό (δεξί) άκρο, δείκτης 9, κατεβαίνοντας, έως ότου φτάσει σε έναν δείκτη του οποίου η τιμή είναι μικρότερη ή ίση με τον άξονα και σταματά εκεί προσωρινά. Αυτό σημαίνει δύο θέσεις στάσης. Εάν i, η μεταβλητή του πρόσθετου δείκτη, από χαμηλά δεν είναι ακόμη ίση ή μεγαλύτερη από τη μεταβαλλόμενη μεταβλητή δείκτη, j από υψηλή, τότε αυτές οι δύο τιμές εναλλάσσονται. Στην τρέχουσα κατάσταση, η σάρωση και από τα δύο άκρα σταμάτησε στο W και O. Έτσι, η λίστα γίνεται:

P O E R T Y U I W Q

Ο άξονας είναι ακόμα Q. Η σάρωση σε αντίθετες κατευθύνσεις συνεχίζεται και σταματά ανάλογα. Εάν το i δεν είναι ακόμη ίσο ή μεγαλύτερο από το j, τότε οι δύο τιμές στις οποίες σταμάτησε η σάρωση και από τα δύο άκρα εναλλάσσονται. Αυτή τη φορά, η σάρωση και από τα δύο άκρα σταμάτησε στο R και I. Έτσι, η διάταξη της λίστας γίνεται:

P O E I T Y U R W Q

Ο άξονας είναι ακόμα Q. Η σάρωση σε αντίθετες κατευθύνσεις συνεχίζεται και σταματά ανάλογα. Εάν το i δεν είναι ακόμη ίσο ή μεγαλύτερο από το j, τότε οι δύο τιμές στις οποίες σταμάτησε η σάρωση, αλλάζουν. Αυτή τη φορά, η σάρωση και από τα δύο άκρα σταμάτησε στο T για i και I για j. έχω γνωρίσει ή περάσει. Άρα, δεν μπορεί να υπάρξει ανταλλαγή. Η λίστα παραμένει η ίδια με:

P O E I T Y U R W Q

Σε αυτό το σημείο, ο άξονας, Q, πρέπει να τοποθετηθεί στην τελική του θέση κατά τη διαλογή. Αυτό γίνεται με την εναλλαγή arr [i] με arr [υψηλό], εναλλαγή T και Q. Η λίστα γίνεται:

P O E I Q Y U R W T

Σε αυτό το σημείο, η κατάτμηση για ολόκληρη τη λίστα έχει τελειώσει. Το pivot = Q έχει παίξει το ρόλο του. Υπάρχουν τώρα τρεις υπο-λίστες, οι οποίες είναι:

P O E I Q Y U R W T

Το διαμέρισμα είναι διαίρεση και κατάκτηση (ταξινόμηση) στο παράδειγμα. Το Q βρίσκεται στη σωστή θέση ταξινόμησης. Κάθε στοιχείο στα αριστερά του Q είναι μικρότερο από το Q και κάθε στοιχείο στα δεξιά του Q είναι μεγαλύτερο από το Q. Ωστόσο, η αριστερή λίστα δεν έχει ταξινομηθεί ακόμα. και η σωστή λίστα εξακολουθεί να μην έχει ταξινομηθεί. Ολόκληρη η λειτουργία Γρήγορης Ταξινόμησης πρέπει να κληθεί αναδρομικά για να ταξινομήσει την αριστερή υπο-λίστα και τη δεξιά υπο-λίστα. Αυτή η ανάκληση του Quick Sort πρέπει να συνεχιστεί. θα αναπτυχθούν νέες υπο-λίστες μέχρι να ταξινομηθεί πλήρως ολόκληρη η αρχική λίστα. Για κάθε ανάκληση της λειτουργίας Γρήγορης Ταξινόμησης, παρακολουθείται πρώτα η αριστερή υπο-λίστα πριν από την αντίστοιχη δεξιά υπο-λίστα. Πρέπει να ληφθεί ένας νέος άξονας για κάθε υπο-λίστα.

Για την υπο-λίστα:

Π Ο Ε Ι

Ο άξονας περιστροφής (διάμεσος) των Ρ, Ο και Ι καθορίζεται. Ο άξονας περιστροφής θα ήταν O. Για αυτήν την υπο-λίστα και σχετικά με την πλήρη λίστα, το νέο arr [low] είναι arr [0] και το νέο arr [high] είναι το τελευταίο arr [i-1] = arr [ 4-1] = arr [3], όπου i είναι ο τελικός δείκτης περιστροφής από το προηγούμενο διαμέρισμα. Αφού κληθεί η λειτουργία pivot (), η νέα τιμή pivot, pivot = O. Μην συγχέετε μεταξύ της συνάρτησης περιστροφής και της τιμής περιστροφής. Η λειτουργία περιστροφής μπορεί να κάνει κάποια μικρή ταξινόμηση και να τοποθετήσει τον άξονα στα άκρα δεξιά της υπο-λίστας. Αυτή η υπο-λίστα γίνεται,

Ι Π Ε Ο

Με αυτό το σχήμα, ο περιστροφικός άξονας τελειώνει πάντα στο δεξί άκρο της δευτερεύουσας λίστας ή λίστας μετά την κλήση συνάρτησης. Η σάρωση και από τα δύο άκρα ξεκινά από arr [0] και arr [3] έως ότου i και j συναντηθούν ή διασταυρωθούν. Η σύγκριση γίνεται με pivot = O. Οι πρώτες στάσεις είναι στο P και E. Αντικαθίστανται και η νέα υπο-λίστα γίνεται:

Ι Ε Ρ Ο

Η σάρωση και από τα δύο άκρα συνεχίζεται και οι νέες στάσεις είναι στο P για i και στο E για j. Τώρα εγώ και ο j έχουμε συναντηθεί ή διασταυρωθεί. Έτσι, η υπο-λίστα παραμένει η ίδια με:

Ι Ε Ρ Ο

Η διαίρεση μιας υπο-λίστας ή λίστας τελειώνει όταν ο άξονας έχει τεθεί στην τελική του θέση. Έτσι, οι νέες τιμές για arr [i] και arr [high] αλλάζουν. Δηλαδή, τα P και O ανταλλάσσονται. Η νέα υπο-λίστα γίνεται:

Ι Ε Ο Ρ

Το O βρίσκεται τώρα στην τελική του θέση για ολόκληρη τη λίστα. Ο ρόλος του ως άξονα έχει τελειώσει. Η υπο-λίστα χωρίζεται επί του παρόντος σε τρεις ακόμη λίστες, οι οποίες είναι:

Ι Ε Ο Ρ

Σε αυτό το σημείο, πρέπει να κληθεί το Quick Sort της πρώτης δεξιάς υπο-λίστας. Ωστόσο, δεν θα κληθεί. Αντ 'αυτού, θα σημειωθεί και θα διατηρηθεί, για να κληθεί αργότερα. Καθώς εκτελούνταν οι δηλώσεις της συνάρτησης διαμερίσματος, από την κορυφή της συνάρτησης, είναι η Γρήγορη Ταξινόμηση για την αριστερή υπο-λίστα που πρέπει να κληθεί τώρα (μετά την κλήση του περιστροφικού ()). Θα κληθεί για τη λίστα:

Ι Ε

Θα ξεκινήσει αναζητώντας τη διάμεσο I και E. Εδώ, arr [low] = I, arr [mid] = I and arr [high] = E. , I. Ωστόσο, ο παραπάνω ψευδοκώδικας περιστροφής θα καθορίσει τον άξονα ως Ε. Αυτό το σφάλμα συμβαίνει εδώ επειδή ο παραπάνω ψευδοκώδικας προορίζεται για τρία στοιχεία και όχι για δύο. Στην παρακάτω εφαρμογή, υπάρχει κάποια προσαρμογή στον κώδικα. Η υπο-λίστα γίνεται,

Ε Ι

Ο περιστροφικός άξονας τελειώνει πάντα στο δεξί άκρο της δευτερεύουσας λίστας ή λίστας μετά την κλήση της λειτουργίας του. Η σάρωση και από τα δύο άκρα ξεκινά από arr [0] και arr [1] αποκλειστικά έως ότου i και j συναντηθούν ή διασταυρωθούν. Η σύγκριση γίνεται με pivot = I. Οι πρώτες και μοναδικές στάσεις είναι στο I και E: στο I για i και στο E για το j. Τώρα εγώ και ο j έχουμε συναντηθεί ή περάσει. Έτσι, η υπο-λίστα παραμένει η ίδια με:

Ε Ι

Η διαίρεση μιας υπο-λίστας ή λίστας τελειώνει όταν ο άξονας έχει τεθεί στην τελική του θέση. Έτσι, οι νέες τιμές για arr [i] και arr [high] αλλάζουν. Συμβαίνει εδώ ότι arr [i] = I και arr [high] = I. Έτσι, η ίδια τιμή ανταλλάσσεται με τον εαυτό της. Η νέα υπο-λίστα γίνεται:

Ε Ι

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

Ε Ι

Τώρα, οι άξονες μέχρι τώρα ήταν Q, O και I. Οι περιστροφές τελειώνουν στις τελικές τους θέσεις. Ένας υπο-κατάλογος ενός μεμονωμένου στοιχείου, όπως το παραπάνω παραπάνω, τελειώνει επίσης στην τελική του θέση.

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

E I O P Q Y U R W T

Η πρώτη δεξιά υπο-λίστα:

Y U R W T

πρέπει ακόμα να τακτοποιηθεί.

Κατάκτηση της πρώτης δεξιάς υπο-λίστας
Θυμηθείτε ότι η κλήση γρήγορης ταξινόμησης για την πρώτη δεξιά υπο-λίστα σημειώθηκε και δεσμεύτηκε αντί να εκτελεστεί. Σε αυτό το σημείο, θα εκτελεστεί. Και έτσι, το νέο arr [low] = arr [5] = arr [QPivotIndex+1], και το νέο arr [high] παραμένει arr [9]. Ένα παρόμοιο σύνολο δραστηριοτήτων που συνέβη για την πρώτη αριστερή υπο-λίστα θα συμβεί εδώ. Και αυτή η πρώτη δεξιά υπο-λίστα ταξινομείται ως εξής:

R T U W Y

Και η αρχική λίστα χωρίς ταξινόμηση έχει ταξινομηθεί ως εξής:

E I O P Q R T U W Y

Κωδικοποίηση Java

Η τοποθέτηση του αλγορίθμου στην Java είναι απλώς η τοποθέτηση όλων των παραπάνω τμημάτων ψευδοκώδικα σε μεθόδους Java σε μια κλάση. Μην ξεχνάτε ότι πρέπει να υπάρχει μια μέθοδος main () στην κλάση που θα καλεί τη συνάρτηση quicksort () με τον μη ταξινομημένο πίνακα.

Η μέθοδος περιστροφής ()

Η μέθοδος Java pivot () που επιστρέφει την τιμή, pivot, πρέπει να είναι:

Μέθοδος swap ()

Η μέθοδος swap () πρέπει να είναι:

Η μέθοδος quicksort ()

Η μέθοδος quicksort () πρέπει να είναι:

Μέθοδος διαμερίσματος ()

Η μέθοδος διαμερίσματος () πρέπει να είναι:

Η κύρια () μέθοδος

Η κύρια () μέθοδος μπορεί να είναι:

Όλες οι παραπάνω μέθοδοι μπορούν να ενταχθούν σε μία κατηγορία.

συμπέρασμα

Το Quick Sort είναι ένας αλγόριθμος ταξινόμησης που χρησιμοποιεί το παράδειγμα διάσπασης και κατάκτησης. Ξεκινά με τη διαίρεση μιας μη ταξινομημένης λίστας σε δύο ή τρεις υπο-λίστες. Σε αυτό το σεμινάριο, το Quick Sort έχει χωρίσει μια λίστα σε τρεις υπο-λίστες: μια αριστερή υπο-λίστα, μια μεσαία λίστα ενός μεμονωμένου στοιχείου και μια δεξιά υπο-λίστα. Η κατάκτηση σε γρήγορη ταξινόμηση είναι η διαίρεση μιας λίστας ή υπο-λίστας κατά την ταξινόμησή της, χρησιμοποιώντας μια τιμή περιστροφής. Αυτό το σεμινάριο έχει εξηγήσει μια εφαρμογή του Quick Sort στη γλώσσα υπολογιστή Java.

Σχετικά με τον Συγγραφέα

Chrysanthus Forcha

Ανακαλυπτής μαθηματικών Ολοκλήρωση από τις πρώτες αρχές και σχετικές σειρές. Μεταπτυχιακό στην Τεχνική Εκπαίδευση, με ειδίκευση στα Ηλεκτρονικά και Λογισμικό Υπολογιστών. BSc Electronics. Έχω επίσης γνώσεις και εμπειρία σε επίπεδο Master σε Υπολογιστή και Τηλεπικοινωνίες. Από τους 20.000 συγγραφείς, ήμουν ο 37ος καλύτερος συγγραφέας στο devarticles.com. Εργάζομαι σε αυτούς τους τομείς για περισσότερα από 10 χρόνια.

ΣΧΕΤΙΚΕΣ ΑΝΑΡΤΗΣΕΙΣ LINUX HINT

• Σύγκριση συμβολοσειρών στην Java
• Πώς να χρησιμοποιήσετε το HashMap στην Java
• Γρήγορη ταξινόμηση σε Java επεξηγείται
• Δυαδικό δέντρο Preorder Traversal στην Java
• Συγχώνευση ταξινόμησης σε Java Explained
• Πώς να χρησιμοποιήσετε το σαρωτή στην Java
• Java εγγραφή στο αρχείο