DOUG LLOYD: Έτσι σε CS50 μάθαμε για μια ποικιλία από διαλογή και την αναζήτηση αλγορίθμων. Και μερικές φορές μπορεί να είναι λίγο δύσκολο να κρατήσει παρακολουθείτε τι αλγορίθμου κάνει τι. Έχουμε πραγματικά μόνο αποκορυφωμένο την επιφάνεια πάρα πολύ, υπάρχουν πολλά άλλα αναζήτηση και αλγορίθμων ταξινόμησης. Έτσι, σε αυτό το βίντεο ας μόλις πάρει μερικά λεπτά να προσπαθήσουμε και να μετατρέψει κάθε αλγόριθμο κάτω στα βασικά στοιχεία της ώστε να μπορείτε να θυμηθείτε το πιο Σημαντικές πληροφορίες σχετικά με τους και να είναι σε θέση να αρθρώσει η διαφορές, εάν είναι απαραίτητο. 

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

Bubble sort, η ιδέα πίσω από αυτό η μία είναι να ανταλλάξουν γειτονικά ζεύγη. Έτσι, αυτό είναι το κλειδί που σας βοηθά θυμηθείτε τη διαφορά εδώ. Επιλογή sort είναι, μέχρι στιγμής, βρείτε το smallest-- φούσκα sort είναι swap δίπλα ζεύγη. Έχουμε ανταλλάξει γειτονικών ζευγών των στοιχείων, εφόσον είναι εκτός λειτουργίας, η οποία αποτελεσματικά φυσαλίδες μεγαλύτερα στοιχεία προς τα δεξιά, και συγχρόνως αρχίζει επίσης να κινηθεί μικρότερα στοιχεία προς τα αριστερά. Η χειρότερη περίπτωση χρόνος τρέχει περίπτωση του bubble sort είναι n τετράγωνο. Ο χρόνος λειτουργίας καλύτερη περίπτωση του bubble sort είναι n. Επειδή σε αυτή την κατάσταση δεν actually-- ίσως να μην χρειάζεται να προβεί σε ανταλλαγές σε όλα. Έχουμε μόνο να κάνει ένα να περάσει σε όλους τους n στοιχεία. 

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

Συγχώνευση sort-- την λέξη-κλειδί εδώ είναι χωρισμένη και να συγχωνεύσετε. Έχουμε χωρίσει την πλήρη σειρά, αν είναι έξι στοιχεία, οκτώ στοιχεία, 10.000 elements-- θα το χωρίσει προς τα κάτω κατά το ήμισυ, κατά το ήμισυ, κατά το ήμισυ, μέχρι να έχουμε κάτω πίνακα ν μια συστοιχίες στοιχείο. Ένα σύνολο από n μία σειρές στοιχείων. Έτσι ξεκινήσαμε με ένα 1.000 στοιχείο του πίνακα, και θα φτάσουμε στο σημείο όπου θα έχει 1.000 συστοιχίες ένα στοιχείο. Στη συνέχεια αρχίζουμε να συγχωνεύσει αυτές τις συστοιχίες υπο πίσω μαζί με τη σωστή σειρά. Έτσι παίρνουμε δύο συστοιχίες ενός στοιχείου και να δημιουργήσει μια συστοιχία δύο στοιχείων. Παίρνουμε δύο συστοιχίες δύο-στοιχείων και να δημιουργήσει μια συστοιχία τεσσάρων στοιχείων και ούτω καθεξής και ούτω καθεξής μέχρι να έχουμε ξαναχτίστηκε και πάλι μια συστοιχία n στοιχείο. 

Ο χρόνος εκτέλεσης χειρότερης περίπτωσης της ταξινόμηση με συγχώνευση είναι Ν φορές log n. Έχουμε n στοιχεία, αλλά Αυτή η διαδικασία ανασυνδυασμο παίρνει log n βήματα για να πάρει πίσω σε μια πλήρη σειρά. Η καλύτερη περίπτωση τρέχει ο χρόνος είναι επίσης n log n επειδή η διαδικασία αυτή δεν έχει πραγματικά με ενδιαφέρει αν ο πίνακας ήταν ταξινομούνται ή όχι να αρχίσει με. Η διαδικασία είναι η ίδια, υπάρχει δεν υπάρχει τρόπος να τα πράγματα σύντομο κύκλωμα. Έτσι n log n στη χειρότερη περίπτωση, n log n στην καλύτερη περίπτωση. 

Μιλήσαμε για δύο αναζήτηση αλγορίθμων. Έτσι γραμμική αναζήτηση είναι για την επανάληψη. Προχωρούμε σε όλη τη σειρά μία φορά, από αριστερά προς τα δεξιά, προσπαθούν να βρουν τον αριθμό ότι ψάχνουμε για. Η χειρότερη περίπτωση να τρέξει ο χρόνος είναι μεγάλος O Ν. Θα μπορούσε να μας πάρει την επανάληψη σε όλη κάθε στοιχείου για να βρείτε το στοιχείο που ψάχνουμε για, είτε στην τελευταία θέση, ή καθόλου. Αλλά δεν μπορούμε να επιβεβαιώσουμε ότι μέχρι έχουμε κοίταξε τα πάντα. m η καλύτερη περίπτωση, θα βρούμε αμέσως. Ο χρόνος λειτουργίας καλύτερη περίπτωση γραμμική αναζήτηση είναι ωμέγα 1. 

Τέλος, υπήρχε δυαδική αναζήτηση, η οποία απαιτεί ανάμικτες σειρά. Να θυμάστε ότι είναι μια πολύ σημαντική παράμετρος όταν εργάζεστε με δυαδική αναζήτηση. Είναι μια προϋπόθεση για τη χρήση it-- ο πίνακας που ψάχνετε μέσα πρέπει να ταξινομηθούν. Διαφορετικά, η λέξη-κλειδί είναι διαίρει και βασίλευε. Χωρίστε τη σειρά σε μισό και εξαλειφθούν τα μισά από τα στοιχεία κάθε φορά καθώς προχωράτε μέσα. Εξαιτίας αυτού του διαίρει και βασίλευε και διαχωρισμό πράγματα στο μισό προσέγγιση, το χρόνο εκτέλεσης χειρότερης περίπτωσης της δυαδικής αναζήτησης είναι log n, η οποία είναι ουσιαστικά καλύτερα από ό, n γραμμικά αναζήτησης. Η καλύτερη περίπτωση τρέχει ο χρόνος είναι ακόμα ένα. 

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

Είμαι ο Νταγκ Lloyd, αυτό είναι CS50.