1
00:00:00,000 --> 00:00:04,419
>> [Παίζει μουσική]

2
00:00:04,419 --> 00:00:05,401

3
00:00:05,401 --> 00:00:08,460
>> DOUG LLOYD: Εντάξει, έτσι η συγχώνευση
sort είναι ένα ακόμη αλγόριθμο

4
00:00:08,460 --> 00:00:11,200
ότι μπορούμε να χρησιμοποιήσουμε για να λύσουμε
τα στοιχεία ενός πίνακα.

5
00:00:11,200 --> 00:00:14,480
Αλλά, όπως θα δούμε, ότι έχεις ένα
πολύ θεμελιώδης διαφορά

6
00:00:14,480 --> 00:00:17,850
από το είδος επιλογής, φούσκα
είδος, και ταξινόμηση με εισαγωγή

7
00:00:17,850 --> 00:00:20,280
που την καθιστούν πραγματικά πολύ έξυπνο.

8
00:00:20,280 --> 00:00:24,290
>> Η βασική ιδέα πίσω από τη συγχώνευση
sort είναι να ταξινομήσετε τα μικρότερα συστοιχίες

9
00:00:24,290 --> 00:00:27,430
και στη συνέχεια συνδυάζουν εκείνες τις συστοιχίες
μαζί, ή να συγχωνεύσει them--

10
00:00:27,430 --> 00:00:31,440
εξ ου και η name-- σε ταξινομημένη σειρά.

11
00:00:31,440 --> 00:00:34,230
Ο τρόπος που το κάνει ταξινόμηση με συγχώνευση
Αυτό είναι με τη μόχλευση ένα εργαλείο

12
00:00:34,230 --> 00:00:37,290
που ονομάζεται αναδρομή, η οποία είναι ό, τι
θα πάμε να μιλάμε για σύντομα,

13
00:00:37,290 --> 00:00:39,720
αλλά δεν έχουμε πραγματικά μίλησε ακόμα.

14
00:00:39,720 --> 00:00:43,010
>> Εδώ είναι η βασική ιδέα πίσω από τη συγχώνευση του είδους.

15
00:00:43,010 --> 00:00:46,320
Ταξινόμηση το αριστερό μισό του πίνακα,
υποθέτοντας το η είναι μεγαλύτερο από 1.

16
00:00:46,320 --> 00:00:49,980
Και τι εννοώ όταν λέω
υποθέτοντας η είναι μεγαλύτερο από 1 είναι,

17
00:00:49,980 --> 00:00:53,970
Νομίζω ότι μπορούμε να συμφωνήσουμε ότι αν μια σειρά
μόνο αποτελείται από ένα μόνο στοιχείο,

18
00:00:53,970 --> 00:00:54,680
αυτό είναι ταξινομημένο.

19
00:00:54,680 --> 00:00:56,560
Δεν πραγματικά ανάγκη
να κάνει τίποτα για αυτό.

20
00:00:56,560 --> 00:00:58,059
Εμείς απλά να κηρύξει πρέπει να διευθετηθεί.

21
00:00:58,059 --> 00:01:00,110
Είναι μόνο ένα στοιχείο.

22
00:01:00,110 --> 00:01:03,610
>> Έτσι, ο ψευδοκώδικας, πάλι, είναι
ταξινομήσετε το αριστερό μισό του πίνακα,

23
00:01:03,610 --> 00:01:08,590
τότε ταξινομήσετε το δεξί μισό του πίνακα,
Στη συνέχεια τη συγχώνευση των δύο μισά μαζί.

24
00:01:08,590 --> 00:01:11,040
Τώρα, ήδη θα μπορούσε να είναι
σκέψης, το είδος ακριβώς

25
00:01:11,040 --> 00:01:14,080
Ακούγεται σαν να είστε απωθώντας the--
δεν έχετε κάνει τίποτα στην πραγματικότητα.

26
00:01:14,080 --> 00:01:16,330
Λέτε ταξινομήσετε το αριστερό
ήμισυ, να ταξινομήσετε το δεξί μισό,

27
00:01:16,330 --> 00:01:19,335
αλλά εσείς δεν λέτε
μου πώς το κάνετε.

28
00:01:19,335 --> 00:01:22,220
>> Αλλά να θυμάστε ότι όσο
μια συστοιχία είναι ένα ενιαίο στοιχείο,

29
00:01:22,220 --> 00:01:23,705
μπορούμε να κηρύξει ταξινομημένο.

30
00:01:23,705 --> 00:01:25,330
Στη συνέχεια, μπορούμε να τα συνδυάσουμε απλά μαζί.

31
00:01:25,330 --> 00:01:27,788
Και αυτό είναι στην πραγματικότητα η
βασική ιδέα πίσω από τη συγχώνευση του είδους,

32
00:01:27,788 --> 00:01:31,150
είναι να το σπάσει, έτσι ώστε
συστοιχίες σας είναι ένα μέγεθος.

33
00:01:31,150 --> 00:01:33,430
Και τότε θα ξαναχτίσουν από εκεί.

34
00:01:33,430 --> 00:01:35,910
>> Συγχώνευση είδος είναι σίγουρα
ένα πολύπλοκο αλγόριθμο.

35
00:01:35,910 --> 00:01:38,210
Και είναι, επίσης, ένα μικρό
περίπλοκο να απεικονίσει.

36
00:01:38,210 --> 00:01:41,870
Έτσι, ελπίζουμε, η οπτικοποίηση ότι εγώ,
έχουμε εδώ θα σας βοηθήσει να ακολουθήσετε μαζί.

37
00:01:41,870 --> 00:01:45,640
Και εγώ θα προσπαθήσω το καλύτερό μου για να αφηγηθεί τα πράγματα
και να προχωρήσει μέσα από αυτό το λίγο περισσότερο

38
00:01:45,640 --> 00:01:49,180
αργά από τις άλλες
απλά για να πάρει ελπίζουμε το κεφάλι σας

39
00:01:49,180 --> 00:01:51,800
γύρω από τις ιδέες πίσω από το είδος συγχώνευσης.

40
00:01:51,800 --> 00:01:54,680
>> Έτσι έχουμε την ίδια σειρά, όπως η
άλλα βίντεο διαλογή αλγόριθμο

41
00:01:54,680 --> 00:01:57,120
αν έχετε δει them--
μια σειρά έξι στοιχείο.

42
00:01:57,120 --> 00:02:02,110
Και κώδικας pseudocode μας εδώ είναι το είδος
το αριστερό μισό, να ταξινομήσετε το δεξί μισό,

43
00:02:02,110 --> 00:02:03,890
συγχώνευση των δύο μισά μαζί.

44
00:02:03,890 --> 00:02:09,770
Ας πάρουμε λοιπόν αυτό το πολύ σκούρο κόκκινο τούβλο
σειρά και να ταξινομήσετε το αριστερό μισό.

45
00:02:09,770 --> 00:02:13,380
>> Έτσι, προς το παρόν, θα πάμε
να αγνοήσει τα πράγματα σχετικά με το δικαίωμα.

46
00:02:13,380 --> 00:02:15,740
Είναι εκεί, αλλά είμαστε
όχι σε αυτό το στάδιο ακόμα.

47
00:02:15,740 --> 00:02:18,220
Δεν είμαστε στο είδος του
δεξιό μισό του πίνακα.

48
00:02:18,220 --> 00:02:21,037
Είμαστε σε είδος το αριστερό
μισο της συστοιχίας.

49
00:02:21,037 --> 00:02:22,870
Και μόνο για χάρη
να είναι λίγο πιο

50
00:02:22,870 --> 00:02:26,480
σαφείς, ώστε να μπορώ να αναφερθώ
σε ποιο στάδιο είμαστε σε,

51
00:02:26,480 --> 00:02:29,800
Πάω να αλλάξουν το
χρώμα αυτού του συνόλου σε πορτοκαλί.

52
00:02:29,800 --> 00:02:33,190
Τώρα, είμαστε ακόμα να μιλάμε για το
ίδιο αριστερό μισό του αρχικού πίνακα.

53
00:02:33,190 --> 00:02:38,520
Αλλά ελπίζω ότι με το να είναι σε θέση να
αναφέρονται στα χρώματα των διαφόρων ειδών,

54
00:02:38,520 --> 00:02:40,900
αυτό θα κάνει λίγο πιο
σαφές τι συμβαίνει εδώ.

55
00:02:40,900 --> 00:02:43,270
>> Εντάξει, έτσι τώρα έχουμε μια
τρία σειράς στοιχείων.

56
00:02:43,270 --> 00:02:46,420
Πώς μπορούμε να λύσουμε το αριστερό ήμισυ του εν λόγω
συστοιχία, η οποία εξακολουθεί να είναι αυτό το βήμα;

57
00:02:46,420 --> 00:02:49,400
Προσπαθούμε να λύσουμε το αριστερό
το ήμισυ του κεραμιδί array--

58
00:02:49,400 --> 00:02:52,410
το αριστερό ήμισυ του οποίου
Έχω τώρα χρωματισμένα πορτοκαλί.

59
00:02:52,410 --> 00:02:54,840
>> Λοιπόν, θα μπορούσαμε να προσπαθήσουμε και
επαναλάβετε αυτή τη διαδικασία.

60
00:02:54,840 --> 00:02:56,756
Έτσι, είμαστε ακόμα στο
μέση προσπαθώντας να ταξινομήσετε

61
00:02:56,756 --> 00:02:58,700
το αριστερό μισό του πλήρους πίνακα.

62
00:02:58,700 --> 00:03:00,450
Το αριστερό ήμισυ του
array, είμαι απλώς πρόκειται

63
00:03:00,450 --> 00:03:03,910
να αποφασίζει αυθαίρετα ότι το αριστερό μισό
θα είναι μικρότερο από το δεξιό ήμισυ,

64
00:03:03,910 --> 00:03:06,550
γιατί συμβαίνει αυτό
αποτελείται από τρία στοιχεία.

65
00:03:06,550 --> 00:03:11,260
>> Και έτσι Πάω να πω ότι η
αριστερό ήμισυ του αριστερού μισο η συστοιχία

66
00:03:11,260 --> 00:03:14,050
είναι ακριβώς το στοιχείο πέντε.

67
00:03:14,050 --> 00:03:18,360
Πέντε, είναι ένα μόνο στοιχείο
σειρά, ξέρουμε πώς να το ξεκαθαρίσουμε.

68
00:03:18,360 --> 00:03:21,615
Και έτσι πέντε είναι ταξινομημένο.

69
00:03:21,615 --> 00:03:22,990
Είμαστε ακριβώς πρόκειται να δηλώσει ότι.

70
00:03:22,990 --> 00:03:24,890
Είναι μια απλή συστοιχία στοιχείο.

71
00:03:24,890 --> 00:03:29,015
>> Έτσι, έχουμε τώρα την ταξινόμηση
αριστερό μισό του αριστερού half--

72
00:03:29,015 --> 00:03:33,190
ή μάλλον, έχουμε την ταξινόμηση
αριστερό μισό του πορτοκαλιού.

73
00:03:33,190 --> 00:03:37,970
Έτσι τώρα, προκειμένου να ολοκληρωθεί ακόμα
το αριστερό μισό της συνολικής συστοιχίας,

74
00:03:37,970 --> 00:03:43,481
θα πρέπει να ταξινομήσετε το δεξί μισό
του πορτοκαλί, ή αυτά τα πράγματα.

75
00:03:43,481 --> 00:03:44,230
Πώς θα το κάνουμε αυτό;

76
00:03:44,230 --> 00:03:45,930
Λοιπόν, έχουμε μια σειρά δύο στοιχείων.

77
00:03:45,930 --> 00:03:50,470
Έτσι μπορούμε να λύσουμε το αριστερό μισό
της συστοιχίας, το οποίο είναι δύο.

78
00:03:50,470 --> 00:03:52,090
Δύο είναι ένα ενιαίο στοιχείο.

79
00:03:52,090 --> 00:03:55,890
Έτσι είναι ταξινομημένο από προεπιλογή.
Στη συνέχεια, μπορούμε να λύσουμε το δεξί μισό

80
00:03:55,890 --> 00:03:58,530
του τμήματος της συστοιχίας, το ένα.

81
00:03:58,530 --> 00:04:00,210
Αυτό είναι το είδος του από προεπιλογή.

82
00:04:00,210 --> 00:04:03,610
>> Αυτή είναι τώρα η πρώτη φορά
έχουμε φτάσει σε ένα στάδιο συγχώνευσης.

83
00:04:03,610 --> 00:04:06,135
Έχουμε ολοκληρώσει, αν και
είμαστε τώρα το είδος των ένθετων down--

84
00:04:06,135 --> 00:04:08,420
και αυτό είναι το είδος του δύσκολη
πράγμα με αναδρομή είναι,

85
00:04:08,420 --> 00:04:10,930
θα πρέπει να κρατήσει σας
το κεφάλι για το πού βρισκόμαστε.

86
00:04:10,930 --> 00:04:15,560
Έτσι, έχουμε το είδος της αριστεράς
μισο του τμήματος πορτοκαλιού.

87
00:04:15,560 --> 00:04:21,280
>> Και τώρα, είμαστε στη μέση της διαλογής
το δεξί μισό του τμήματος πορτοκαλί.

88
00:04:21,280 --> 00:04:25,320
Και σε αυτή τη διαδικασία, είμαστε
τώρα για να είναι στο στάδιο,

89
00:04:25,320 --> 00:04:27,850
συγχώνευση των δύο μισά μαζί.

90
00:04:27,850 --> 00:04:31,700
Όταν κοιτάξουμε τα δύο ημίχρονα
της συστοιχίας, βλέπουμε δυο και ένα.

91
00:04:31,700 --> 00:04:33,880
Ποιο στοιχείο είναι μικρότερο;

92
00:04:33,880 --> 00:04:35,160
Ένα.

93
00:04:35,160 --> 00:04:36,760
>> Τότε ποιο στοιχείο είναι μικρότερο;

94
00:04:36,760 --> 00:04:38,300
Λοιπόν, αυτό είναι δύο ή τίποτα.

95
00:04:38,300 --> 00:04:39,910
Γι 'αυτό είναι δύο.

96
00:04:39,910 --> 00:04:43,690
Μέχρι τώρα, μόνο και μόνο για να πλαισιώσει και πάλι
πού βρισκόμαστε σε αυτό το πλαίσιο,

97
00:04:43,690 --> 00:04:48,230
έχουμε την ταξινόμηση
αριστερό μισό του πορτοκαλιού

98
00:04:48,230 --> 00:04:49,886
και το δεξί μισό της καταγωγής.

99
00:04:49,886 --> 00:04:52,510
Ξέρω ότι έχω αλλάξει τα χρώματα
και πάλι, αλλά αυτό είναι όπου ήμασταν.

100
00:04:52,510 --> 00:04:54,676
Και ο λόγος που το έκανα αυτό
είναι επειδή αυτή η διαδικασία είναι

101
00:04:54,676 --> 00:04:57,870
Θα συνεχίσουμε, επανάληψη προς τα κάτω.

102
00:04:57,870 --> 00:05:00,500
Έχουμε ταξινομημένο το αριστερό
το ήμισυ του πρώην πορτοκαλί

103
00:05:00,500 --> 00:05:02,590
και το δεξί μισό του πρώην πορτοκαλί.

104
00:05:02,590 --> 00:05:05,620
>> Τώρα, θα πρέπει να συγχωνευθούν εκείνους
δύο μισά μαζί πάρα πολύ.

105
00:05:05,620 --> 00:05:07,730
Αυτό είναι το βήμα που βρίσκεστε.

106
00:05:07,730 --> 00:05:11,440
Έτσι θεωρούμε ότι όλα τα
στοιχεία που είναι τώρα το πράσινο,

107
00:05:11,440 --> 00:05:12,972
το αριστερό μισό του αρχικού πίνακα.

108
00:05:12,972 --> 00:05:14,680
Και έχουμε συγχωνεύσει εκείνους
χρησιμοποιώντας την ίδια διαδικασία

109
00:05:14,680 --> 00:05:18,660
κάναμε για τη συγχώνευση δύο
και πριν από ένα μόλις μια στιγμή.

110
00:05:18,660 --> 00:05:23,080
>> Το αριστερό μισό, το μικρότερο
στοιχείο στο αριστερό μισό είναι πέντε.

111
00:05:23,080 --> 00:05:25,620
Το μικρότερο στοιχείο για
το δεξί μισό είναι ένα.

112
00:05:25,620 --> 00:05:27,370
Ποια από αυτά είναι μικρότερο;

113
00:05:27,370 --> 00:05:29,260
Ένα.

114
00:05:29,260 --> 00:05:32,250
>> Το μικρότερο στοιχείο για
το αριστερό μισό είναι πέντε.

115
00:05:32,250 --> 00:05:35,540
Το μικρότερο στοιχείο για
το δεξί μισό είναι δύο.

116
00:05:35,540 --> 00:05:36,970
Ποια είναι η μικρότερη;

117
00:05:36,970 --> 00:05:38,160
Δύο.

118
00:05:38,160 --> 00:05:41,540
Και στη συνέχεια, τέλος, πέντε
τίποτα, μπορούμε να πούμε πέντε.

119
00:05:41,540 --> 00:05:43,935
>> Εντάξει, έτσι μεγάλη εικόνα, ας
να κάνουν ένα διάλειμμα για ένα δεύτερο

120
00:05:43,935 --> 00:05:46,080
και να καταλάβω πού βρισκόμαστε.

121
00:05:46,080 --> 00:05:48,580
Αν ξεκινήσαμε από
η ίδια η αρχή,

122
00:05:48,580 --> 00:05:51,640
έχουν πλέον ολοκληρωθεί για
η συνολική διάταξη μόνο

123
00:05:51,640 --> 00:05:53,810
ένα βήμα του κώδικα ψευδοκώδικα εδώ.

124
00:05:53,810 --> 00:05:56,645
Έχουμε ταξινομημένο το
αριστερό ήμισυ της συστοιχίας.

125
00:05:56,645 --> 00:05:59,490
>> Υπενθυμίζεται ότι το αρχικό
διαταγή ήταν πέντε, δύο, ένα.

126
00:05:59,490 --> 00:06:02,570
Με τη μετάβαση μέσω αυτής της διαδικασίας
και φωλιάζουν κάτω και επανάληψη,

127
00:06:02,570 --> 00:06:05,990
συνεχίζοντας να σπάσει το πρόβλημα
κάτω σε όλο και μικρότερα τμήματα,

128
00:06:05,990 --> 00:06:09,670
Έχουμε ολοκληρώσει τώρα
Βήμα πρώτο του ψευδοκώδικα

129
00:06:09,670 --> 00:06:13,940
για ολόκληρης της συστοιχίας εκκίνησης.

130
00:06:13,940 --> 00:06:16,670
Έχουμε ταξινομημένο αριστερό ήμισυ της.

131
00:06:16,670 --> 00:06:18,670
>> Έτσι τώρα ας παγώσει εκεί.

132
00:06:18,670 --> 00:06:23,087
Και τώρα ας λύσουμε το δικαίωμα
το μισό του αρχικού πίνακα.

133
00:06:23,087 --> 00:06:25,670
Και θα πάμε να το κάνουμε αυτό από
διέρχεται από το ίδιο επαναληπτική

134
00:06:25,670 --> 00:06:30,630
διαδικασία της άρσης πράγματα κάτω
και στη συνέχεια συγχώνευσή τους μαζί.

135
00:06:30,630 --> 00:06:34,290
>> Έτσι, το αριστερό ήμισυ του
κόκκινο, ή το αριστερό ήμισυ

136
00:06:34,290 --> 00:06:38,830
του δικαιώματος μισό του αρχικού
σειρά, Πάω να πω είναι τρεις.

137
00:06:38,830 --> 00:06:40,312
Και πάλι, είμαι συνεπείς εδώ.

138
00:06:40,312 --> 00:06:42,020
Εάν έχετε μια περίεργη
αριθμός των στοιχείων του,

139
00:06:42,020 --> 00:06:44,478
Δεν έχει τόση σημασία αν
κάνετε το αριστερό μικρότερα

140
00:06:44,478 --> 00:06:45,620
ή το δικαίωμα ενός μικρότερου.

141
00:06:45,620 --> 00:06:49,230
>> Αυτό που έχει σημασία είναι ότι κάθε φορά που
αντιμετωπίσετε αυτό το πρόβλημα κατά τη διεξαγωγή των

142
00:06:49,230 --> 00:06:51,422
μια συγχώνευση, θα πρέπει να είναι συνεπής.

143
00:06:51,422 --> 00:06:53,505
Μπορείτε είτε πρέπει πάντα να
κάνει μια αριστερή πλευρά μικρότερη

144
00:06:53,505 --> 00:06:55,421
ή πρέπει πάντα να κάνετε
η δεξιά πλευρά μικρότερο.

145
00:06:55,421 --> 00:06:57,720
Εδώ, έχω επιλέξει να είναι πάντα
κάνουν την αριστερή πλευρά μικρότερη

146
00:06:57,720 --> 00:07:04,380
όταν σειρά μου, ή μου
υπο-πίνακα, είναι ένα περίεργο μέγεθος.

147
00:07:04,380 --> 00:07:07,420
>> Τρεις είναι ένα μόνο στοιχείο,
και γι 'αυτό είναι ταξινομημένο.

148
00:07:07,420 --> 00:07:10,860
Έχουμε μόχλευση αυτή την υπόθεση
καθ 'όλη τη διαδικασία μας μέχρι στιγμής.

149
00:07:10,860 --> 00:07:15,020
Έτσι τώρα ας λύσουμε το δικαίωμα
μισό του δεξιού μισού,

150
00:07:15,020 --> 00:07:18,210
ή το δεξί μισό του κόκκινου.

151
00:07:18,210 --> 00:07:20,390
>> Και πάλι, θα πρέπει να χωρίσει αυτό κάτω.

152
00:07:20,390 --> 00:07:21,910
Αυτό δεν είναι ένα ενιαίο στοιχείο συστοιχία.

153
00:07:21,910 --> 00:07:23,970
Δεν μπορούμε να την κηρύξει ταξινομημένο.

154
00:07:23,970 --> 00:07:27,060
Και έτσι το πρώτο, θα πάμε
για να ταξινομήσετε το αριστερό μισό.

155
00:07:27,060 --> 00:07:31,620
>> Το αριστερό μισό είναι ένα ενιαίο στοιχείο,
έτσι είναι είδος από προεπιλογή.

156
00:07:31,620 --> 00:07:34,840
Στη συνέχεια, θα πάμε για να ταξινομήσετε τη σωστή
ένα δεύτερο, το οποίο είναι ένα ενιαίο στοιχείο.

157
00:07:34,840 --> 00:07:41,250
Είναι ταξινομημένο ως προεπιλογή. Και τωρα,
μπορούμε να συγχωνευθούν τα δύο αυτά μαζί.

158
00:07:41,250 --> 00:07:45,820
Τέσσερις είναι μικρότερο, και
στη συνέχεια, έξι είναι μικρότερο.

159
00:07:45,820 --> 00:07:48,870
>> Και πάλι, τι έχουμε κάνει σε αυτό το σημείο;

160
00:07:48,870 --> 00:07:52,512
Έχουμε ταξινομημένο το αριστερό
μισό του δεξιού μισού.

161
00:07:52,512 --> 00:07:54,720
Ή για να επανέλθω στο αρχικό
χρώματα που υπήρχαν,

162
00:07:54,720 --> 00:07:57,875
έχουμε ταξινομημένο το αριστερό
μισο του μαλακότερο κόκκινο.

163
00:07:57,875 --> 00:08:00,416
Ήταν αρχικά ένα σκοτεινό τούβλο
κόκκινο και τώρα είναι μια πιο ήπια κόκκινο,

164
00:08:00,416 --> 00:08:02,350
ή ήταν ένα μαλακότερο κόκκινο.

165
00:08:02,350 --> 00:08:05,145
>> Και τότε έχουμε την ταξινόμηση
δεξιό μισό του μαλακότερο κόκκινο.

166
00:08:05,145 --> 00:08:08,270
Τώρα, επίσης, ότι είναι πράσινα και πάλι, απλά
επειδή είμαστε σε μια διαδικασία.

167
00:08:08,270 --> 00:08:10,720
Και πρέπει να επαναλάβουμε
αυτό ξανά και ξανά.

168
00:08:10,720 --> 00:08:14,695
>> Έτσι τώρα μπορούμε να συγχωνεύσει εκείνους
δύο μισά μαζί.

169
00:08:14,695 --> 00:08:15,820
Και αυτό είναι που κάνουμε εδώ.

170
00:08:15,820 --> 00:08:17,653
Έτσι, η μαύρη γραμμή μόνο
διαιρείται το αριστερό μισό

171
00:08:17,653 --> 00:08:19,690
και το δεξί μισό του μέρους αυτού του είδους.

172
00:08:19,690 --> 00:08:24,310
>> Συγκρίνουμε τη μικρότερη τιμή
στην αριστερή πλευρά της array--

173
00:08:24,310 --> 00:08:26,710
ή με συγχωρείτε, το μικρότερο
αξία του αριστερού μισο

174
00:08:26,710 --> 00:08:30,790
με την μικρότερη τιμή του δικαιώματος
το ήμισυ και να διαπιστώσει ότι τρεις είναι μικρότερο.

175
00:08:30,790 --> 00:08:32,530
Και τώρα ένα κομμάτι από μια βελτιστοποίηση, σωστά;

176
00:08:32,530 --> 00:08:35,175
Δεν υπάρχει πραγματικά τίποτα
αριστερά στην αριστερή πλευρά.

177
00:08:35,175 --> 00:08:37,440
>> Δεν υπάρχει τίποτα που απομένει
στην αριστερή πλευρά,

178
00:08:37,440 --> 00:08:40,877
ώστε να μπορούμε αποτελεσματικά
ακριβώς move-- μπορούμε να δηλώσουμε

179
00:08:40,877 --> 00:08:42,960
το υπόλοιπο είναι πραγματικά
ταξινομούνται και απλά να αναστρέψει

180
00:08:42,960 --> 00:08:45,126
σχετικά, γιατί δεν υπάρχει τίποτα
άλλο να συγκρίνετε με.

181
00:08:45,126 --> 00:08:49,140
Και γνωρίζουμε ότι η δεξιά πλευρά
της δεξιάς πλευράς είναι ταξινομημένο.

182
00:08:49,140 --> 00:08:52,770
>> Εντάξει, έτσι και τώρα ας παγώσει και πάλι
καταλάβουμε πού βρισκόμαστε στην ιστορία.

183
00:08:52,770 --> 00:08:56,120
Στη συνολική συστοιχία,
τι έχουμε καταφέρει;

184
00:08:56,120 --> 00:08:58,790
Έχουμε πράγματι επιτύχει
τώρα τα βήματα ένα και το δεύτερο βήμα.

185
00:08:58,790 --> 00:09:03,300
Εμείς ταξινομημένο το αριστερό μισό, και
θα διευθετηθεί το δεξί μισό.

186
00:09:03,300 --> 00:09:08,210
>> Μέχρι τώρα, το μόνο που μας απομένει είναι
για τη συγχώνευση αυτών των δύο μισά μαζί.

187
00:09:08,210 --> 00:09:11,670
Γι 'αυτό και το συγκρίνουμε με τη χαμηλότερη αξία
στοιχείο κάθε μισό του πίνακα

188
00:09:11,670 --> 00:09:13,510
με τη σειρά του και να προχωρήσει.

189
00:09:13,510 --> 00:09:16,535
Ένα είναι μικρότερος των τριών, έτσι πηγαίνει.

190
00:09:16,535 --> 00:09:19,770
>> Δύο είναι μικρότερος των τριών, έτσι πηγαίνει δύο.

191
00:09:19,770 --> 00:09:22,740
Τρεις είναι μικρότερη από 5, οπότε τρεις πηγαίνει.

192
00:09:22,740 --> 00:09:25,820
Τέσσερις είναι μικρότερη από 5, έτσι ώστε τέσσερεις πηγαίνει.

193
00:09:25,820 --> 00:09:30,210
Στη συνέχεια, πέντε είναι μικρότερη των έξι,
και έξι είναι το μόνο που απομένει.

194
00:09:30,210 --> 00:09:31,820
>> Τώρα, ξέρω, ότι ήταν πολλά βήματα.

195
00:09:31,820 --> 00:09:33,636
Και έχουμε άφησε πολλά
της μνήμης στο πέρασμά μας.

196
00:09:33,636 --> 00:09:35,260
Και αυτό είναι ό, τι είναι αυτά τα γκρι τετράγωνα.

197
00:09:35,260 --> 00:09:40,540
Και μάλλον ένιωσα ότι πήρε
πολύ περισσότερο από ό, τι είδος εισαγωγής, φούσκα

198
00:09:40,540 --> 00:09:42,660
είδος ή είδος επιλογής.

199
00:09:42,660 --> 00:09:45,330
>> Αλλά στην πραγματικότητα, επειδή ένας
πολλά από αυτές τις διαδικασίες

200
00:09:45,330 --> 00:09:48,260
συμβαίνουν στο ίδιο time--
το οποίο είναι κάτι που θα, και πάλι,

201
00:09:48,260 --> 00:09:51,100
μιλάμε για όταν μιλάμε για
αναδρομή σε μια μελλοντική video--

202
00:09:51,100 --> 00:09:53,799
Αυτός ο αλγόριθμος πραγματικά
σαφώς είναι θεμελιωδώς

203
00:09:53,799 --> 00:09:55,590
διαφορετική από οτιδήποτε άλλο
έχουμε ξαναδεί

204
00:09:55,590 --> 00:09:58,820
αλλά είναι επίσης σημαντικά
πιο αποτελεσματική.

205
00:09:58,820 --> 00:09:59,532
>> Γιατί αυτό?

206
00:09:59,532 --> 00:10:01,240
Λοιπόν, στη χειρότερη
σενάριο, έχουμε

207
00:10:01,240 --> 00:10:04,830
να χωρίσει n στοιχεία μέχρι
και στη συνέχεια ανασυνδυάζονται τους.

208
00:10:04,830 --> 00:10:06,680
Αλλά όταν εμείς ανασυνδυάζονται
τους, αυτό που κάνουμε

209
00:10:06,680 --> 00:10:11,110
είναι βασικά ο διπλασιασμός
μέγεθος των μικρότερων συστοιχιών.

210
00:10:11,110 --> 00:10:14,260
Έχουμε ένα σωρό ενός στοιχείου
πινάκων που μπορούμε αποτελεσματικά

211
00:10:14,260 --> 00:10:16,290
συνδυάζονται σε δύο σειρές στοιχείων.

212
00:10:16,290 --> 00:10:18,590
Και τότε παίρνουμε εκείνες
δυο σειρές στοιχείων

213
00:10:18,590 --> 00:10:21,890
και να τα συνδυάσετε σε
τέσσερεις σειρές στοιχείων, και ούτω καθεξής,

214
00:10:21,890 --> 00:10:26,130
και ούτω καθεξής, και ούτω καθεξής, μέχρι να
έχουν ένα ενιαίο πίνακα n στοιχείων.

215
00:10:26,130 --> 00:10:29,910
>> Αλλά πόσοι διπλασιασμούς
χρειάζεται για να πάρει στο n;

216
00:10:29,910 --> 00:10:31,460
Σκεφτείτε πίσω στο παράδειγμα τηλεφωνικό κατάλογο.

217
00:10:31,460 --> 00:10:34,490
Πόσες φορές έχουμε να σχίσει
τον τηλεφωνικό κατάλογο στη μέση, πόσα περισσότερα

218
00:10:34,490 --> 00:10:38,370
φορές έχουμε να σχίσει τον τηλεφωνικό κατάλογο
στο μισό, αν το μέγεθος του τηλεφωνικού καταλόγου

219
00:10:38,370 --> 00:10:39,680
διπλασιαστεί;

220
00:10:39,680 --> 00:10:41,960
Υπάρχει μόνο ένα, έτσι δεν είναι;

221
00:10:41,960 --> 00:10:45,360
>> Έτσι, υπάρχει κάποιο είδος
λογαριθμική στοιχείο εδώ.

222
00:10:45,360 --> 00:10:48,590
Αλλά πρέπει επίσης να εξακολουθούν να έχουν τουλάχιστον
δείτε όλα τα n στοιχεία.

223
00:10:48,590 --> 00:10:53,860
Έτσι, στη χειρότερη περίπτωση,
ταξινόμηση με συγχώνευση τρέχει στο n log n.

224
00:10:53,860 --> 00:10:56,160
Πρέπει να κοιτάξουμε
όλα τα n στοιχεία,

225
00:10:56,160 --> 00:11:02,915
και πρέπει να τα συνδυάσουν
μαζί log n σύνολα βημάτων.

226
00:11:02,915 --> 00:11:05,290
Στην καλύτερη περίπτωση,
η σειρά είναι απόλυτα ταξινομημένο.

227
00:11:05,290 --> 00:11:06,300
Αυτό είναι υπέροχο.

228
00:11:06,300 --> 00:11:09,980
Όμως, με βάση τον αλγόριθμο που έχουμε εδώ,
έχουμε ακόμη να χωρίσετε και ανασύνθεσης.

229
00:11:09,980 --> 00:11:13,290
Αν και στην περίπτωση αυτή, η
ανασυνδυασμο είδους αναποτελεσματική.

230
00:11:13,290 --> 00:11:14,720
Δεν είναι απαραίτητη.

231
00:11:14,720 --> 00:11:17,580
Αλλά ακόμα περνάμε
η όλη διαδικασία ούτως ή άλλως.

232
00:11:17,580 --> 00:11:21,290
>> Έτσι, στην καλύτερη περίπτωση
και στη χειρότερη περίπτωση,

233
00:11:21,290 --> 00:11:24,970
Αυτός ο αλγόριθμος τρέχει σε n log n του χρόνου.

234
00:11:24,970 --> 00:11:29,130
Συγχώνευση είδος είναι σίγουρα λίγο πιο περίπλοκη
από τις άλλες κύριες αλγορίθμων ταξινόμησης

235
00:11:29,130 --> 00:11:33,470
έχουμε μιλήσει για CS50, αλλά είναι
αισθητά πιο ισχυρή.

236
00:11:33,470 --> 00:11:35,400
>> Και έτσι αν ποτέ βρείτε
την ευκαιρία να το χρειαστείτε

237
00:11:35,400 --> 00:11:38,480
ή να το χρησιμοποιήσετε για να ταξινομήσετε ένα
μεγάλο σύνολο δεδομένων, να πάρει

238
00:11:38,480 --> 00:11:41,940
το κεφάλι σας γύρω από την ιδέα της αναδρομής
πρόκειται να είναι πραγματικά ισχυρή.

239
00:11:41,940 --> 00:11:45,270
Και αυτό πρόκειται να κάνει σας
προγράμματα πραγματικά πολύ πιο αποδοτική

240
00:11:45,270 --> 00:11:48,700
χρησιμοποιώντας ταξινόμηση με συγχώνευση έναντι οτιδήποτε άλλο.

241
00:11:48,700 --> 00:11:49,640
Είμαι ο Νταγκ Lloyd.

242
00:11:49,640 --> 00:11:51,970
Αυτό είναι CS50.

243
00:11:51,970 --> 00:11:53,826