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

2
00:00:02,826 --> 00:00:05,660

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: Έτσι ταξινόμηση με εισαγωγή είναι ένα άλλο
αλγόριθμο μπορούμε να χρησιμοποιήσουμε για να ταξινομήσετε μια σειρά.

4
00:00:09,370 --> 00:00:12,350
Η ιδέα πίσω από αυτόν τον αλγόριθμο
είναι να οικοδομήσουμε ταξινομημένο πίνακα σας

5
00:00:12,350 --> 00:00:19,670
στη θέση του, μετατοπίζοντας τα στοιχεία από
ο τρόπος as you go, για να κάνει χώρο.

6
00:00:19,670 --> 00:00:22,240
Αυτό είναι ελαφρώς διαφορετική
από το είδος ή την επιλογή φούσκα

7
00:00:22,240 --> 00:00:25,460
είδος, για παράδειγμα, όπου
είμαστε προσαρμογή των θέσεις,

8
00:00:25,460 --> 00:00:26,910
όπου φτιάχνουμε swaps.

9
00:00:26,910 --> 00:00:29,760
>> Σε αυτή την περίπτωση αυτό που είμαστε στην πραγματικότητα
κάνει είναι συρόμενα στοιχεία

10
00:00:29,760 --> 00:00:31,390
πάνω, έξω από το δρόμο.

11
00:00:31,390 --> 00:00:34,030
Πώς αυτόν τον αλγόριθμο
εργάζονται σε ψευδοκώδικα;

12
00:00:34,030 --> 00:00:37,646
Λοιπόν ας αυθαίρετα λένε ότι η
πρώτο στοιχείο του πίνακα είναι ταξινομημένο.

13
00:00:37,646 --> 00:00:38,770
Είμαστε το κτίριο στη θέση του.

14
00:00:38,770 --> 00:00:42,660
>> Είμαστε θα πάμε ένα στοιχείο σε έναν χρόνο και
οικοδομήσουμε, και έτσι το πρώτο πράγμα που βλέπουμε

15
00:00:42,660 --> 00:00:43,890
είναι μια διάταξη ένα στοιχείο.

16
00:00:43,890 --> 00:00:47,720
Και εξ ορισμού, μία
σειρά στοιχείων είναι ταξινομημένο.

17
00:00:47,720 --> 00:00:50,850
>> Στη συνέχεια, θα επαναλάβετε αυτή τη διαδικασία until--
Εμείς θα επαναλάβουμε την ακόλουθη διαδικασία

18
00:00:50,850 --> 00:00:52,900
έως ότου όλα τα στοιχεία ταξινομούνται.

19
00:00:52,900 --> 00:00:57,770
Κοιτάξτε το επόμενο στοιχείο και αδιαχώριστα
τοποθετήστε το στο ταξινομημένο τμήμα,

20
00:00:57,770 --> 00:01:01,209
μετατοπίζοντας τον απαιτούμενο αριθμό
των στοιχείων έξω από το δρόμο.

21
00:01:01,209 --> 00:01:03,750
Ας ελπίσουμε ότι αυτή η οπτικοποίηση
θα σας βοηθήσει να δείτε ακριβώς τι είναι

22
00:01:03,750 --> 00:01:05,980
συμβαίνει με το είδος εισαγωγής.

23
00:01:05,980 --> 00:01:08,010
>> Έτσι και πάλι, εδώ είναι μας
ολόκληρο το φάσμα χωρίς διαλογή,

24
00:01:08,010 --> 00:01:10,970
όλα τα στοιχεία που αναφέρονται στο κόκκινο.

25
00:01:10,970 --> 00:01:13,320
Και ας ακολουθήσει η
στάδια της ψευδοκώδικα μας.

26
00:01:13,320 --> 00:01:16,970
Το πρώτο πράγμα που κάνουμε, είναι που ονομάζουμε
το πρώτο στοιχείο του πίνακα, ταξινομημένο.

27
00:01:16,970 --> 00:01:20,920
Έτσι, είμαστε απλά θα πω
πέντε, είστε τώρα ταξινομημένο.

28
00:01:20,920 --> 00:01:24,570
>> Στη συνέχεια, εξετάζουμε την επόμενη
αδιαχώριστα στοιχείο του πίνακα

29
00:01:24,570 --> 00:01:27,610
και θέλουμε να προστεθεί ότι
στο ταξινομημένο τμήμα,

30
00:01:27,610 --> 00:01:29,750
μετατοπίζοντας τα στοιχεία πάνω.

31
00:01:29,750 --> 00:01:33,470
Έτσι, δύο είναι η επόμενη αδιαχώριστα
στοιχείο της συστοιχίας.

32
00:01:33,470 --> 00:01:36,250
Είναι σαφές ότι ανήκει πριν από την
πέντε, οπότε τι θα κάνουμε

33
00:01:36,250 --> 00:01:41,580
είναι είδος κατέχει δύο στην άκρη για μια δεύτερη,
στροφή πέντε πάνω, και στη συνέχεια τοποθετήστε τα δύο

34
00:01:41,580 --> 00:01:43,210
πριν από πέντε, πού να πρέπει να πάει.

35
00:01:43,210 --> 00:01:45,280
Και τώρα μπορούμε να πούμε ότι δύο είναι ταξινομημένο.

36
00:01:45,280 --> 00:01:48,400
>> Έτσι, όπως μπορείτε να δείτε, έχουμε μόνο μέχρι στιγμής
εξέτασαν δύο στοιχεία της συστοιχίας.

37
00:01:48,400 --> 00:01:50,600
Δεν έχουμε κοίταξε το
ξεκουραστεί καθόλου, αλλά έχουμε

38
00:01:50,600 --> 00:01:54,582
πήρε τα δύο αυτά στοιχεία με ταξινόμηση κατά
τρόπος του μηχανισμού αλλαγής ταχυτήτων.

39
00:01:54,582 --> 00:01:56,410
>> Γι 'αυτό και επαναλάβετε τη διαδικασία.

40
00:01:56,410 --> 00:01:58,850
Κοιτάξτε την επόμενη αδιαχώριστα
στοιχείο, αυτό είναι ένα.

41
00:01:58,850 --> 00:02:04,010
Ας κρατήσει κατά μέρος για ένα δευτερόλεπτο,
τα πάντα πάνω στροφή, και να θέσει ένα

42
00:02:04,010 --> 00:02:05,570
πού πρέπει να πάει.

43
00:02:05,570 --> 00:02:08,110
>> Και πάλι, ακόμα, έχουμε μόνο ποτέ
κοίταξε ένα, δύο και πέντε.

44
00:02:08,110 --> 00:02:12,480
Δεν ξέρω τι άλλο έρχεται,
αλλά έχουμε ταξινομούνται τα τρία αυτά στοιχεία.

45
00:02:12,480 --> 00:02:16,030
>> Επόμενο στοιχείο είναι αδιαχώριστα
τρία, οπότε θα το αναιρέσει.

46
00:02:16,030 --> 00:02:18,200
Θα στραφούν πάνω από ό, τι
Πρέπει να τα οποία, αυτή τη φορά

47
00:02:18,200 --> 00:02:21,820
δεν είναι πάντα όπως και στην προηγούμενη
δύο περιπτώσεις, αυτό είναι ακριβώς το πέντε.

48
00:02:21,820 --> 00:02:25,440
Και τότε θα μείνουμε τρεις,
μεταξύ των δύο και πέντε.

49
00:02:25,440 --> 00:02:27,849
>> Έξι είναι η επόμενη αδιαχώριστα
στοιχείο στη συστοιχία.

50
00:02:27,849 --> 00:02:31,140
Και στην πραγματικότητα έξι είναι μεγαλύτερη από πέντε, έτσι
Δεν χρειάζεται καν να κάνει οποιαδήποτε εναλλαγή.

51
00:02:31,140 --> 00:02:35,710
Μπορούμε να αναστρέψει μόλις έξι δεξιά για να
το άκρο του τμήματος ταξινομημένο.

52
00:02:35,710 --> 00:02:38,270
>> Τέλος, τέσσερις είναι η
τελευταία αδιαχώριστα στοιχείο.

53
00:02:38,270 --> 00:02:42,060
Γι 'αυτό και θα το αναιρέσει, μεταβάλλεται με την πάροδο
Τα στοιχεία που θα πρέπει να στραφούν πάνω,

54
00:02:42,060 --> 00:02:43,780
και στη συνέχεια θα τοποθετούνται τέσσερα όπου ανήκει.

55
00:02:43,780 --> 00:02:46,400
Και τώρα να δείτε, έχουμε το είδος
όλων των στοιχείων.

56
00:02:46,400 --> 00:02:48,150
Ανακοίνωση με την εισαγωγή
είδος, δεν είχαμε

57
00:02:48,150 --> 00:02:50,240
για να πάει μπροστά και πίσω σε όλη τη σειρά.

58
00:02:50,240 --> 00:02:54,720
Το μόνο που πήγαν σε όλη τη σειρά
μία φορά, και θα μετατοπιστεί πράγματα

59
00:02:54,720 --> 00:02:59,870
ότι είχαμε ήδη συναντήσει, προκειμένου
για να κάνουν χώρο για τα νέα στοιχεία.

60
00:02:59,870 --> 00:03:02,820
>> Έτσι ποια είναι η χειρότερη περίπτωση
σενάριο με ταξινόμηση με εισαγωγή;

61
00:03:02,820 --> 00:03:05,090
Στη χειρότερη περίπτωση, η
πίνακας είναι σε αντίστροφη σειρά.

62
00:03:05,090 --> 00:03:11,180
Θα πρέπει να στρέψουμε κάθε ένα από τα n στοιχεία
των θέσεων του Ν, κάθε φορά που

63
00:03:11,180 --> 00:03:12,880
κάνει μια εισαγωγή.

64
00:03:12,880 --> 00:03:15,720
Αυτό είναι ένα πολύ μετατόπιση.

65
00:03:15,720 --> 00:03:18,014
>> Στην καλύτερη περίπτωση, η
συστοιχία τέλεια ταξινομημένο.

66
00:03:18,014 --> 00:03:20,680
Και κάπως σαν αυτό που συνέβη
με πέντε και έξι στο παράδειγμα,

67
00:03:20,680 --> 00:03:23,779
όπου θα μπορούσαμε απλά να το θέτει
χωρίς να χρειάζεται να κάνει οποιαδήποτε μετατόπιση,

68
00:03:23,779 --> 00:03:24,820
θα κάναμε ουσιαστικά αυτό.

69
00:03:24,820 --> 00:03:27,560
>> Αν φανταστείτε ότι μας
σειρά ήταν ένα έως έξι,

70
00:03:27,560 --> 00:03:29,900
είχαμε ξεκινήσει από
δηλώνοντας ότι ο ένας είναι ταξινομημένο.

71
00:03:29,900 --> 00:03:33,300
Δύο έρχεται μετά από μία τόσο μπορούμε μόνο
πούμε, εντάξει, καλά ένα και δύο είναι ταξινομημένο.

72
00:03:33,300 --> 00:03:36,190
Τρεις έρχεται μετά από δύο έτσι, εντάξει,
ένα και δύο και τρία είναι ταξινομημένο.

73
00:03:36,190 --> 00:03:39,590
>> Εμείς δεν κάνουμε καμία swaps, είμαστε
κινείται μόνο αυτό αυθαίρετη γραμμή

74
00:03:39,590 --> 00:03:42,460
μεταξύ διαλογή και χωρίς διαλογή όσο προχωράμε.

75
00:03:42,460 --> 00:03:46,646
Το ίδιο αποτελεσματικά όπως κάναμε και στο παράδειγμα,
μετατρέποντας στοιχεία μπλε, καθώς προχωράμε.

76
00:03:46,646 --> 00:03:48,270
Έτσι ποια είναι η χειρότερη περίπτωση χρόνου εκτέλεσης, τότε;

77
00:03:48,270 --> 00:03:51,854
Να θυμάστε, αν θα πρέπει να στρέψουμε το καθένα από
τα n στοιχεία ενδεχομένως θέσεις n,

78
00:03:51,854 --> 00:03:54,020
ελπίζω ότι σας δίνει
η ιδέα ότι η χειρότερη περίπτωση

79
00:03:54,020 --> 00:03:57,770
runtime είναι Big O Ν τετράγωνο.

80
00:03:57,770 --> 00:04:00,220
>> Εάν η συστοιχία είναι τέλεια
διαλογή, το μόνο που έχουμε να κάνουμε

81
00:04:00,220 --> 00:04:04,480
είναι να δούμε κάθε στοιχείου
μία φορά, και στη συνέχεια να τελειώσουμε.

82
00:04:04,480 --> 00:04:08,440
Έτσι, στην καλύτερη περίπτωση, είναι το ωμέγα της Ν.

83
00:04:08,440 --> 00:04:09,490
>> Είμαι ο Νταγκ Lloyd.

84
00:04:09,490 --> 00:04:11,760
Αυτό είναι CS50.

85
00:04:11,760 --> 00:04:13,119