[Powered by Google Translate] [Συγχώνευση Ταξινόμηση] [Rob Bowden - Πανεπιστήμιο του Χάρβαρντ] [Αυτό είναι CS50. - CS50.TV] Ας μιλήσουμε για το είδος συγχώνευσης. Μέχρι στιγμής έχετε δει bubble sort, ταξινόμηση με εισαγωγή, ταξινόμηση και επιλογή. Αν και εγώ θα το είδος του κύματος το χέρι μου σε ό, τι εννοώ με την καλύτερη, συγχώνευση είδος εκτελεί γενικά καλύτερα από ό, τι οποιοδήποτε από αυτά τα 3 είδη. 

Αλλά πριν να μιλάμε για τέτοια συγχώνευση, ας μιλήσουμε για συγχώνευση 2 Ταξινόμηση λίστες. Θα καλέσετε τη διαδικασία λαμβάνοντας 2 ταξινομημένο καταλόγους, όπως αυτοί, και κάνοντας μια ενιαία ταξινομημένη λίστα από αυτούς - συγχώνευση των καταλόγων. Πώς μπορούμε να το κάνουμε αυτό; Λοιπόν, μια ιδέα είναι να κολλήσει μόνο μια λίστα στο τέλος του άλλου λίστα ταξινομήσετε και στη συνέχεια το αποτέλεσμα λίστα. 

Ενώ αυτή η εργασία, είναι μια πολλά περιττά δουλειά. Μπορούμε να το κάνουμε πιο γρήγορα από ό, τι ακριβώς διαλογή. Παρατηρήστε ότι ένα λάθος ιδέα είναι να πάρει μόνο εναλλασσόμενο φλιτζάνια από κάθε λίστα. Ενώ αυτό μπορεί να φαίνεται σαν αυτό λειτουργεί σε πρώτη φάση, κάνει ότι καταλήγουμε με 4, 8, 15, 23, 16 - ειδοποίηση ότι 16 και 23 είναι εκτός τόπου. Αυτό οφείλεται στο γεγονός ότι 2 στοιχεία που θα πρέπει να εμφανίζονται διαδοχικά στην νέα λίστα βρίσκονται στην ίδια αρχικό κατάλογο. Και οι δύο 15 και 16 βρίσκονται στη λίστα στα αριστερά. Το κόλπο είναι να επωφεληθούν από το γεγονός ότι και οι δύο λίστες έχουν ήδη ταξινομημένο. Αυτό σημαίνει ότι αν εξετάσουμε μόνο τα πρώτα στοιχεία των δύο λιστών - εδώ, 4 και 8 - ένας από αυτούς πρέπει να είναι το πρώτο στοιχείο της νέας λίστας. Λοιπόν, γιατί συμβαίνει αυτό; Και οι δύο από αυτές τις λίστες είναι ήδη ταξινομημένο, και έτσι είτε 4 ή 8 πρέπει να είναι το μικρότερο στοιχείο όταν συνδυάζουμε τις 2 λίστες. Σε αυτή την περίπτωση, το μικρότερο είναι 4, έτσι μπορούμε να πάρουμε από 4 και να είναι το πρώτο στοιχείο της νέας λίστας μας. Τώρα συνεχίζουμε τη συγχώνευση τα υπόλοιπα 3 στοιχεία του πρώτου καταλόγου και 4 στοιχεία της δεύτερης λίστας. 

Για άλλη μια φορά, το μόνο που χρειάζεται να δούμε το πρώτο στοιχείο και των δύο καταλόγων. Το μικρότερο από τα 2 πρέπει να είναι το δεύτερο στοιχείο της νέας λίστας μας. Αυτή τη φορά, μεταξύ 8 και 15 το μικρότερο είναι 8, και έτσι ώστε εισάγουμε ως το δεύτερο στοιχείο της ταξινομημένη λίστα μας. Μπορούμε να συνεχίσουμε συγκρίνοντας τα πρώτα στοιχεία των δύο λιστών και αφαιρώντας το μικρότερο του 2. Συγκρίνοντας 15 και 23, 15 και είναι μικρότερη έτσι ώστε το τρίτο στοιχείο μας. Τώρα συγκρίνοντας 16 και 23, 16 είναι μικρότερη. Έτσι, αυτό είναι το τέταρτο στοιχείο. 

Σημειώστε ότι 2 στοιχεία προέρχονται από την ίδια λίστα σε μια σειρά. Για το λόγο αυτό η νέα λίστα δεν μπορεί απλώς εναλλακτική στοιχεία από τις 2 λίστες. Συγκρίνοντας 50 και 23, 23 είναι μικρότερη, οπότε η επιλογή του. Μεταξύ 50 και 42, 42 είναι μικρότερο. Μεταξύ 50 και 108, 50 είναι μικρότερο. Και, τέλος, έχουμε μόνο 108, γι 'αυτό πρέπει να πάει στο τέλος της λίστας μας. Παρατηρήστε ότι έχουμε μια ωραία, ταξινομημένη λίστα. Κάθε φορά που συγκρίναμε τα πρώτα 2 στοιχεία των πινάκων 2 ήμασταν σε θέση να καθορίσει το επόμενο στοιχείο της νέας λίστας. Αυτό σημαίνει ότι εάν ο τελικός κατάλογος περιέχει n αριθμούς, όπου η είναι εδώ 8, τότε χρειαζόμαστε το πολύ n συγκρίσεις για να πάρετε όλα αυτά τα νούμερα στο σωστό μέρος. Ένας τέτοιος αλγόριθμος λέγεται να τρέχει σε γραμμικό χρόνο, αλλά μην ανησυχείτε γι 'αυτό εδώ. 

Χρησιμοποιώντας τον αλγόριθμο μας για τη συγχώνευση, μπορούμε να κάνουμε ένα γρήγορο αλγόριθμο είδος συγχώνευσης. Έτσι, ας επαναφορά τους καταλόγους μας. Υπάρχουν 2 μεγάλα βήματα στη διαδικασία της συγχώνευσης είδος. Κατ 'αρχάς, χωρίζεται συνεχώς τον κατάλογο των κυπέλλων στη μέση μέχρι να έχουμε ένα σωρό λίστες με μόλις 1 φλιτζάνι σε αυτά. Μην ανησυχείτε εάν ένας κατάλογος περιέχει ένα μονό αριθμό και δεν μπορείτε να κάνετε μια απόλυτα καθαρή κοπή μεταξύ τους. Απλά επιλέξτε αυθαίρετα ποια λίστα να περιλαμβάνει το επιπλέον φλιτζάνι μέσα Έτσι, ας χωρίσει τους καταλόγους αυτούς. Τώρα έχουμε 2 λίστες. Τώρα έχουμε 4 λίστες. 

Και τώρα έχουμε 8 λίστες με ένα μόνο φλιτζάνι σε κάθε λίστα. Έτσι, αυτό είναι όλο για το βήμα 1. Για το βήμα 2, έχουμε επανειλημμένα ζεύγη συγχώνευση των καταλόγων χρησιμοποιώντας τον αλγόριθμο συγχώνευσης μάθαμε πριν. Συγχώνευση 108 και 15, καταλήγουμε με τον κατάλογο 15, 108. Συγχώνευση 50 και 4, καταλήγουμε με 4, 50. Συγχώνευση 8 και 42, καταλήγουμε με 8, 42. Και τη συγχώνευση 23 και 16, καταλήγουμε με 16, 23. Τώρα όλες τις λίστες μας είναι το μέγεθος 2. Παρατηρήστε ότι κάθε ένα από τα 4 καταλόγων είναι ταξινομημένος. 

Έτσι, μπορούμε να αρχίσουμε τη συγχώνευση ζεύγη των καταλόγων και πάλι. Συγχωνεύοντας 15 και 108 και 4 και 50 - πρώτα λάβει το 4, τότε το 15, τότε το 50, τότε το 108. Συγχωνευόμενες 8, 42 και 16, 23, πρέπει πρώτα να λάβει τα 8, τότε το 16, τότε το 23, τότε το 42. Έτσι τώρα έχουμε μόλις 2 καταλόγους μεγέθους 4, καθένα από τα οποία είναι ταξινομημένο. Έτσι τώρα έχουμε συγχωνεύσει αυτά τα 2 λίστες. Πρώτα παίρνουμε το 4. Στη συνέχεια παίρνουμε το 8. Τότε παίρνουμε το 15 και 16, στη συνέχεια 23, στη συνέχεια 42, 50, στη συνέχεια, στη συνέχεια 108. Και τελειώσαμε. Έχουμε τώρα μια ταξινομημένη λίστα. Έτσι, πόσο γρήγορα ήταν αυτό, ακριβώς; Σε τεχνικούς όρους, συγχώνευση sort είναι O (n log n), ενώ όλες του bubble sort, ταξινόμηση με εισαγωγή, ταξινόμηση και επιλογή είναι O (n ²). Στην πραγματικότητα, όπως θα μάθετε σύντομα, δεν θα είναι σε θέση να καταλήξει σε ένα είδος που εκτελεί καλύτερα από O (n log n) στη γενική περίπτωση. Και πάλι, μην ανησυχείτε για αυτό το μεγάλο συμβολισμό O αν δεν το έχετε δει ακόμα. 

Απλά ξέρω ότι αυτό σημαίνει ότι αν θέλαμε να ταξινομήσετε μια πραγματικά μεγάλη λίστα bubble sort, ταξινόμηση με εισαγωγή, και η επιλογή του είδους θα μπορούσαν δυνητικά να σημαντικά μεγαλύτερη από ό, τι είδος συγχώνευσης. Αυτό δεν σημαίνει ότι η συγχώνευση είδος θα είναι ταχύτερη για όλες τις λίστες ή ακόμα και για κάθε ενιαίο κατάλογο κάτω από ένα ορισμένο μέγεθος. Για παράδειγμα, η ταξινόμηση με εισαγωγή μπορεί να είναι η ταχύτερη ταξινόμησης για όλους τους καταλόγους μικρότερα από 5 στοιχεία. Στην πράξη, συγχώνευση είδος είναι συνήθως πιο γρήγορα για τους καταλόγους τόσο μικρό όσο 50 στοιχεία. 

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

Το όνομά μου είναι Rob Bowden, και αυτό είναι CS50. [CS50.TV] - Και η επιλογή του είδους. [Γέλια] Ω, έχεις να λάβει ότι από πάρα πολύ, επειδή άλλαξα τρόπο με τον οποίο είχα την παρουσίαση. Κατάλογος για την αριστερά. Αυτό ήταν ένα τυπογραφικό λάθος. [Έκανε λάθος] σκάτωσα - [Γέλια] Δεν ξέρω τι -