[Powered by Google Translate] TOMMY: Ας ρίξουμε μια ματιά στο είδος επιλογής, ένας αλγόριθμος
για τη λήψη μια λίστα αριθμών και τη διαλογή τους.
Ένας αλγόριθμος, να θυμάστε, είναι απλά ένα βήμα-προς-βήμα
Διαδικασία για την πραγματοποίηση μιας εργασίας.
Η βασική ιδέα πίσω από τέτοια επιλογή είναι να διαιρέσει
κατάλογος μας σε δύο μέρη -
ένα ταξινομημένο τμήμα και ένα τμήμα αδιαχώριστα.
Σε κάθε βήμα του αλγορίθμου, ένας αριθμός μεταφέρεται από το πλαίσιο
αδιαχώριστα τμήμα στο ταξινομημένο τμήμα έως ότου τελικά η
Ολόκληρη η λίστα είναι ταξινομημένο.
Έτσι, εδώ είναι μια λίστα με έξι αριθμούς -
23, 42, 4, 16, 8, και 15.
Αυτή τη στιγμή το σύνολο του καταλόγου θεωρείται ότι έχουν υποστεί διαλογή.
Ακόμα κι αν ένας αριθμός στο 16 μπορεί να είναι ήδη στη σωστή του
θέση, ο αλγόριθμος μας δεν έχει καμία δυνατότητα να γνωρίζει ότι μέχρι το
Ολόκληρη η λίστα είναι ταξινομημένο.
Γι 'αυτό και θα εξετάσουμε κάθε αριθμός να ανακατεμένα μέχρι να ταξινομήσετε
μόνοι μας.
Ξέρουμε ότι θέλουμε ο κατάλογος να είναι σε αύξουσα σειρά.
Γι 'αυτό και θα θέλουν να χτίσουν το ταξινομημένο τμήμα του καταλόγου μας
από αριστερά προς τα δεξιά, το μικρότερο στο μεγαλύτερο.
Για να γίνει αυτό, θα πρέπει να βρείτε το ελάχιστο στοιχείο αδιαχώριστα
και να το θέσω στο τέλος της ταξινομημένο τμήμα.
Δεδομένου ότι ο κατάλογος αυτός δεν είναι ταξινομημένο, ο μόνος τρόπος για να γίνει αυτό είναι να
εξετάσουμε κάθε στοιχείο στο τμήμα αδιαχώριστα, θυμόμαστε
στοιχείο το οποίο είναι το χαμηλότερο και συγκρίνοντας
κάθε στοιχείο σε αυτό.
Γι 'αυτό και θα εξετάσουμε πρώτα την 23.
Αυτό είναι το πρώτο στοιχείο που έχουμε δει, έτσι θα θυμόμαστε
ως το ελάχιστο.
Στη συνέχεια θα εξετάσουμε στο 42.
42 είναι μεγαλύτερο από 23, οπότε 23 εξακολουθεί να είναι το ελάχιστο.
Επόμενη είναι η 4, η οποία είναι μικρότερη από 23, έτσι θα θυμόμαστε 4
ως το νέο ελάχιστο.
Επόμενο είναι 16 που είναι μεγαλύτερο από 4, έτσι 4
εξακολουθεί να είναι το ελάχιστο.
8 είναι μεγαλύτερο από 4, και 15 είναι μεγαλύτερο από 4, οπότε θα πρέπει να είναι 4
το μικρότερο στοιχείο αδιαχώριστα.
Έτσι ακόμα κι αν οι άνθρωποι μπορούμε να δούμε αμέσως ότι το 4 είναι
το ελάχιστο στοιχείο, ο αλγόριθμος μας θα πρέπει να εξετάσουμε
αδιαχώριστα κάθε στοιχείο, ακόμη και μετά βρήκαμε τα 4 - το
ελάχιστο στοιχείο.
Έτσι, τώρα που βρήκαμε το ελάχιστο στοιχείο, 4, θα ήθελα
για να προχωρήσουμε προς το ταξινομημένο τμήμα του καταλόγου.
Δεδομένου ότι αυτό είναι το πρώτο βήμα, αυτό σημαίνει θέλουμε να θέσουμε σε 4
η αρχή της λίστας.
23 τώρα είναι στην αρχή της λίστας, έτσι
ας ανταλλάξουν το 4 και το 23.
Έτσι τώρα λίστα μας μοιάζει με αυτό.
Γνωρίζουμε ότι το 4 θα πρέπει να είναι στην τελική θέση του, επειδή είναι
τόσο το μικρότερο στοιχείο και το στοιχείο κατά την έναρξη
του καταλόγου.
Έτσι, αυτό σημαίνει ότι δεν θα χρειαστεί ποτέ να το μετακινήσετε πάλι.
Ας επαναλάβετε αυτή τη διαδικασία για να προσθέσετε ένα άλλο στοιχείο για την
ταξινομημένο τμήμα του καταλόγου.
Γνωρίζουμε ότι δεν χρειάζεται να εξετάσουμε το 4, γιατί είναι
ήδη ταξινομημένο.
Έτσι, μπορούμε να ξεκινήσουμε από την 42, η οποία θα θυμούνται ως το
ελάχιστο στοιχείο.
Έτσι, το επόμενο θα εξετάσουμε την 23 η οποία είναι μικρότερη από 42, έτσι ώστε να
23 είναι να θυμάστε το νέο ελάχιστο.
Επόμενο βλέπουμε την 16 η οποία είναι μικρότερη από 23, έτσι
16 είναι το νέο ελάχιστο.
Τώρα κοιτάξουμε την 8 η οποία είναι μικρότερη από 16, έτσι
8 είναι το νέο ελάχιστο.
Και τέλος 8 είναι μικρότερη από 15, έτσι ξέρουμε ότι το 8 είναι ένα ελάχιστο
αδιαχώριστα στοιχείο.
Έτσι, αυτό σημαίνει ότι θα πρέπει να προσαρτήσει 8 στην ταξινόμηση
μέρος της λίστας.
Αυτή τη στιγμή 4 είναι το μόνο στοιχείο ταξινομημένο, έτσι θέλουμε να τοποθετήσετε
το 8 δίπλα στο 4.
Από το 42 είναι το πρώτο στοιχείο στην αδιαχώριστων τμήμα του
λίστα, θα θέλετε να ανταλλάξετε το 42 και το 8.
Έτσι τώρα λίστα μας μοιάζει με αυτό.
4 και 8 αντιπροσωπεύουν την ταξινόμηση τμήμα του καταλόγου, και το
υπόλοιποι αριθμοί αντιπροσωπεύουν τη μη ταξινομημένα
μέρος της λίστας.
Ας συνεχίσουμε με μια άλλη επανάληψη.
Ξεκινάμε με 23 αυτή τη φορά, από τη στιγμή που δεν χρειάζεται να εξετάσουμε
το 4 και το 8 πια γιατί έχω
ήδη ταξινομημένο.
16 είναι μικρότερο από 23, έτσι θα θυμόμαστε
16 ως το νέο ελάχιστο.
16 είναι μικρότερη από 42, αλλά 15 είναι μικρότερη από 16, οπότε θα πρέπει να είναι 15
το ελάχιστο στοιχείο αδιαχώριστα.
Έτσι, τώρα θέλουμε να ανταλλάξουν το 15 και το 23 για να
να μας δώσει αυτή τη λίστα.
Η ταξινόμηση τμήμα του κατάλογος αποτελείται από 4, 8 και 15, και
Τα στοιχεία αυτά εξακολουθούν να έχουν υποστεί διαλογή.
Αλλά είναι ακριβώς έτσι συμβαίνει ότι το επόμενο στοιχείο αδιαχώριστα, 16,
είναι ήδη ταξινομημένο.
Ωστόσο, δεν υπάρχει κανένας τρόπος για τον αλγόριθμο μας να γνωρίζουμε ότι 16
είναι ήδη σε σωστή θέση του, γι 'αυτό πρέπει ακόμα να
επαναλάβετε ακριβώς την ίδια διαδικασία.
Έτσι βλέπουμε ότι το 16 είναι μικρότερη από 42, και 16 είναι μικρότερη από 23, έτσι
16 πρέπει να είναι το ελάχιστο στοιχείο.
Είναι αδύνατο να ανταλλάξετε το στοιχείο αυτό με τον εαυτό του, ώστε να μπορούμε να
απλά αφήστε το σε αυτήν τη θέση.
Έτσι, χρειαζόμαστε ένα ακόμα πέρασμα του αλγορίθμου μας.
42 είναι μεγαλύτερη από 23, οπότε 23 πρέπει να είναι η
αδιαχώριστα ελάχιστο στοιχείο.
Μόλις έχουμε ανταλλάξει το 23 και το 42, θα καταλήξουμε με την τελική μας
ταξινομημένη λίστα -
4, 8, 15, 16, 23, 42.
Γνωρίζουμε 42 πρέπει να είναι στη σωστή θέση, δεδομένου ότι είναι η
μόνο στοιχείο που έφυγε, και αυτό είναι το είδος επιλογής.
Ας επισημοποιήσει τώρα αλγόριθμος μας με κάποια
ψευδοκώδικα.
On line ένα, μπορούμε να δούμε ότι πρέπει να ενσωματωθούν σε
κάθε στοιχείο της λίστας.
Εκτός από το τελευταίο στοιχείο, δεδομένου ότι το στοιχείο 1
κατάλογος είναι ήδη ταξινομημένο.
On line δύο, θεωρούμε ότι το πρώτο στοιχείο της μη διαχωρισμένων
τμήμα του πίνακα να είναι η ελάχιστη, όπως κάναμε με μας
παράδειγμα, έτσι ώστε να έχουμε κάτι να συγκριθεί με.
Γραμμή τρία αρχίζει μια δεύτερη θηλιά στην οποία θα επαναλάβει πάνω
κάθε στοιχείο αδιαχώριστα.
Γνωρίζουμε ότι μετά από i επαναλήψεις, το ταξινομημένο τμήμα
του καταλόγου μας θα πρέπει να έχουν i στοιχεία σε αυτό, δεδομένου ότι κάθε βήμα
ταξινομεί ένα στοιχείο.
Έτσι, το πρώτο στοιχείο αδιαχώριστα πρέπει να είναι σε θέση i συν 1.
On line τέσσερα, συγκρίνουμε το τρέχον στοιχείο στο ελάχιστο
στοιχείο που έχουμε δει μέχρι τώρα.
Εάν το τρέχον στοιχείο είναι μικρότερη από την ελάχιστη
στοιχείου, τότε θυμόμαστε το τρέχον στοιχείο ως νέα
ελάχιστο στη γραμμή πέντε.
Τέλος, στις γραμμές έξι και επτά, έχουμε ανταλλάξει το ελάχιστο
στοιχείου με το πρώτο στοιχείο αδιαχώριστα, έτσι
προσθήκη του στην ταξινόμηση μέρος της λίστας.
Μόλις έχουμε έναν αλγόριθμο, ένα σημαντικό ερώτημα που τίθεται
τους εαυτούς μας ως προγραμματιστές είναι πόσο καιρό έκανε να πάρει;
Θα ρωτήσω πρώτα το ερώτημα πόσο καιρό παίρνει για αυτό
αλγόριθμο για να τρέξει στη χειρότερη περίπτωση;
Ανάκληση εμείς εκπροσωπούμε την λειτουργία
χρόνο με μεγάλο συμβολισμό O.
Προκειμένου να προσδιορισθεί η ελάχιστη αδιαχώριστα στοιχείου, εμείς
ουσιαστικά έπρεπε να συγκρίνει κάθε στοιχείο στη λίστα για να
κάθε άλλο στοιχείο στη λίστα.
Διαισθητικά, αυτό ακούγεται σαν ένα O n τετράγωνο του λειτουργία.
Κοιτάζοντας ψευδοκώδικα μας, έχουμε επίσης ένα βρόχο ένθετα στο εσωτερικό
άλλο βρόχο, η οποία μάλιστα ακούγεται σαν O
κ τετράγωνο λειτουργίας.
Ωστόσο, να θυμάστε ότι δεν χρειάζεται να κοιτάξουν πέρα ​​από το
Ολόκληρη η λίστα για τον καθορισμό της ελάχιστης αδιαχώριστα στοιχείο;
Μόλις γνωρίζαμε ότι το 4 ήταν ταξινομημένο, για παράδειγμα, δεν
πρέπει να το δει κανείς και πάλι.
Έτσι το κάνει αυτό κάτω το χρόνο λειτουργίας;
Για την λίστα μας μήκους 6, έπρεπε να κάνω πέντε
συγκρίσεις για το πρώτο στοιχείο, τέσσερις για συγκρίσεις
το δεύτερο στοιχείο, και ούτω καθεξής.
Αυτό σημαίνει ότι ο συνολικός αριθμός των σταδίων είναι το άθροισμα των
οι ακέραιοι από το 1 έως το μήκος του καταλόγου μείον 1.
Μπορούμε να αντιπροσωπεύει αυτό με μια άθροιση.
Δεν θα υπεισέλθω σε αθροίσματα εδώ.
Αλλά φαίνεται ότι αυτή η άθροιση είναι ίσο με n φορές
n μείον 1 σε 2.
Ή ισοδύναμα, n τετράγωνο πάνω από 2 μείον n πάνω από 2.
Όταν μιλάμε για ασυμπτωτική runtime, αυτό το τετράγωνο n όρος
πρόκειται να κυριαρχήσει αυτό το ν όρο.
Έτσι, είναι είδος επιλογή του n O τετράγωνο.
Υπενθυμίζουμε ότι στο παράδειγμά μας, το είδος επιλογής εξακολουθούν να χρειάζονται να
ελέγχει αν ένας αριθμός που ήταν ήδη ταξινομημένο
που απαιτούνται για να μετακινηθούν.
Έτσι, αυτό σημαίνει ότι αν τρέξαμε είδος επιλογής κατά τη διάρκεια μιας ήδη
ταξινομημένο κατάλογο, θα απαιτούσε τον ίδιο αριθμό βημάτων όπως είναι
όταν θα τρέχει πάνω από ένα εντελώς αδιαχώριστα λίστα.
Έτσι, το είδος επιλογής έχει καλύτερη απόδοση περίπτωση του n στο τετράγωνο,
την οποία εμείς εκπροσωπούμε με ωμέγα n τετράγωνο.
Και αυτό είναι το είδος για την επιλογή.
Μόνο ένα από τα πολλά αλγορίθμων μπορούμε
χρησιμοποιήσετε για να ταξινομήσετε μια λίστα.
Το όνομά μου είναι ο Tommy, και αυτό είναι CS50.