1
00:00:00,000 --> 00:00:02,826
>> [Zenelejátszási]

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

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: Szóval beillesztés sort egy másik
algoritmust tudjuk használni, hogy rendezni egy tömb.

4
00:00:09,370 --> 00:00:12,350
Az ötlet mögött ez az algoritmus
hogy létrejöjjön a rendezett tömbben

5
00:00:12,350 --> 00:00:19,670
a helyén, a változó elemek ki
az út, ahogy megy, hogy helyet csináljon.

6
00:00:19,670 --> 00:00:22,240
Ez kicsit más
a kijelölés ilyen vagy buborék

7
00:00:22,240 --> 00:00:25,460
rendezés, például, ahol
mi kiigazításáról helyeken,

8
00:00:25,460 --> 00:00:26,910
ahol tesszük swap.

9
00:00:26,910 --> 00:00:29,760
>> Ebben az esetben mi vagyunk valójában
Ennek a csúszó elemek

10
00:00:29,760 --> 00:00:31,390
vége, az útból.

11
00:00:31,390 --> 00:00:34,030
Hogyan működik ez az algoritmus
dolgozni pszeudokódja?

12
00:00:34,030 --> 00:00:37,646
Nos nézzük csak önkényesen mondani, hogy a
első eleme a tömb rendezve.

13
00:00:37,646 --> 00:00:38,770
Építünk a helyére.

14
00:00:38,770 --> 00:00:42,660
>> Mi fog menni egyik eleme egy időben, és
építeni, és így az első dolog, amit látni

15
00:00:42,660 --> 00:00:43,890
egy egyik eleme tömb.

16
00:00:43,890 --> 00:00:47,720
És a meghatározás szerint az egyik
elem tömb rendezve.

17
00:00:47,720 --> 00:00:50,850
>> Akkor ismételje meg ezt a folyamatot until--
fogjuk ismételni a következő eljárás

18
00:00:50,850 --> 00:00:52,900
amíg az összes elemet vannak rendezve.

19
00:00:52,900 --> 00:00:57,770
Nézd meg a következő osztályozás nélküli elem és
helyezze be a rendezett része,

20
00:00:57,770 --> 00:01:01,209
eltolásával a szükséges számú
elemek az útból.

21
00:01:01,209 --> 00:01:03,750
Remélhetőleg ez a vizualizáció
segít, hogy pontosan mi

22
00:01:03,750 --> 00:01:05,980
folyik a behelyezés sort.

23
00:01:05,980 --> 00:01:08,010
>> Szóval megint itt van a
teljes válogatás nélkül tömb,

24
00:01:08,010 --> 00:01:10,970
az összes elem pirossal jelzett.

25
00:01:10,970 --> 00:01:13,320
És kövessük a
lépéseit a pszeudokódja.

26
00:01:13,320 --> 00:01:16,970
Az első dolog, amit csinálunk, az hívjuk a
első eleme a tömb, válogatni.

27
00:01:16,970 --> 00:01:20,920
Szóval mi csak akarsz mondani
öt, te most válogatni.

28
00:01:20,920 --> 00:01:24,570
>> Akkor nézzük a következő
válogatás nélkül a tömb elemének

29
00:01:24,570 --> 00:01:27,610
és szeretnénk beszúrni, hogy
a rendezve része,

30
00:01:27,610 --> 00:01:29,750
eltolásával elemek fölött.

31
00:01:29,750 --> 00:01:33,470
Tehát két a következő szétválogatás nélkül
elem a tömb.

32
00:01:33,470 --> 00:01:36,250
Nyilvánvaló tartozik előtt
öt, akkor mi csinálunk

33
00:01:36,250 --> 00:01:41,580
A fajta tartsa két félre egy pillanatra,
váltás öt fölött, majd helyezze be a két

34
00:01:41,580 --> 00:01:43,210
öt előtt, hol kell menni.

35
00:01:43,210 --> 00:01:45,280
És most azt mondhatjuk, hogy a két rendezve.

36
00:01:45,280 --> 00:01:48,400
>> Tehát mint látható, most már csak eddig
nézett a két tömb elemei.

37
00:01:48,400 --> 00:01:50,600
Még nem nézett
pihenni egyáltalán, de mi már

38
00:01:50,600 --> 00:01:54,582
kapott e két elem sorolva
módja a változó mechanizmus.

39
00:01:54,582 --> 00:01:56,410
>> Tehát ismételjük meg a folyamatot újra.

40
00:01:56,410 --> 00:01:58,850
Nézd meg a következő szétválogatás nélkül
eleme, hogy az egyik.

41
00:01:58,850 --> 00:02:04,010
Nézzük meg, hogy félre egy pillanatra,
váltás mindent ért, és egyik

42
00:02:04,010 --> 00:02:05,570
hová kell mennie.

43
00:02:05,570 --> 00:02:08,110
>> Ismét mindig, most már mindig csak
nézett egy, kettő, öt.

44
00:02:08,110 --> 00:02:12,480
Nem tudjuk, mi más jön,
de már válogatni a három elemet.

45
00:02:12,480 --> 00:02:16,030
>> Következő szétválogatott elem
három, úgyhogy majd tegye félre.

46
00:02:16,030 --> 00:02:18,200
Majd álljak át, amit mi
kell, hogy melyik, ezúttal

47
00:02:18,200 --> 00:02:21,820
nem minden, mint az előző
Két esetben ez csak öt.

48
00:02:21,820 --> 00:02:25,440
És akkor maradok három,
a kettő között, és az öt.

49
00:02:25,440 --> 00:02:27,849
>> Hat a következő szétválogatás nélkül
elem a tömbben.

50
00:02:27,849 --> 00:02:31,140
És valóban hat nagyobb, mint öt, így
mi nem is kell semmilyen csere.

51
00:02:31,140 --> 00:02:35,710
Mi is csak irányt hat közvetlenül a
a végén a rendezve rész.

52
00:02:35,710 --> 00:02:38,270
>> Végül négy a
Utolsó szétválogatott elem.

53
00:02:38,270 --> 00:02:42,060
Szóval majd tegye félre, álljak át
Az elemek meg kell álljak át,

54
00:02:42,060 --> 00:02:43,780
majd fel négy, ahova tartozik.

55
00:02:43,780 --> 00:02:46,400
És most nézd, mi már egyfajta
minden elemét.

56
00:02:46,400 --> 00:02:48,150
Figyeljük meg a beillesztés
sort, nem volt

57
00:02:48,150 --> 00:02:50,240
hogy menjen vissza oda az egész tömböt.

58
00:02:50,240 --> 00:02:54,720
Mi csak akkor ment át a tömböt
Egy időben, és toltuk a dolgokat

59
00:02:54,720 --> 00:02:59,870
hogy mi lenne a már felmerült, annak érdekében,
hogy helyet csináljon az új elemeket.

60
00:02:59,870 --> 00:03:02,820
>> Szóval mi a legrosszabb esetben
forgatókönyv a beillesztés sort?

61
00:03:02,820 --> 00:03:05,090
A legrosszabb esetben, a
tömb fordított sorrendben.

62
00:03:05,090 --> 00:03:11,180
Meg kell váltani az egyes elemek n
n-ig pozíciókat, minden egyes alkalommal, amikor

63
00:03:11,180 --> 00:03:12,880
a beszúrási.

64
00:03:12,880 --> 00:03:15,720
Ez nagyon sok a változó.

65
00:03:15,720 --> 00:03:18,014
>> A legjobb esetben, a
tömb tökéletesen rendezve.

66
00:03:18,014 --> 00:03:20,680
És valami, mint mi történt
öt és hat a példában,

67
00:03:20,680 --> 00:03:23,779
ahol tudnánk csapáson azt
anélkül, hogy ezt bármilyen változó,

68
00:03:23,779 --> 00:03:24,820
mi lenne alapvetően csinálni.

69
00:03:24,820 --> 00:03:27,560
>> Ha tudod képzelni, hogy mi
tömb egyike volt a hat,

70
00:03:27,560 --> 00:03:29,900
mi lenne elindul a
nyilvánító egy rendezve.

71
00:03:29,900 --> 00:03:33,300
Két után jön valaki így tudjuk csak
azt mondják, OK, jól egy-két helyre nem kerül.

72
00:03:33,300 --> 00:03:36,190
Három után jön két igen, OK,
egy és kettő és három sorrendje.

73
00:03:36,190 --> 00:03:39,590
>> Nem vagyunk bármilyen csereügyletek vagyunk
csak mozog ez az önkényes vonal

74
00:03:39,590 --> 00:03:42,460
között rendezett és rendezetlen, ahogy haladunk.

75
00:03:42,460 --> 00:03:46,646
Olyan hatékonyan, mint mi a példában,
fordult elemek kék, ahogy haladunk tovább.

76
00:03:46,646 --> 00:03:48,270
Szóval mi a legrosszabb esetben runtime, akkor?

77
00:03:48,270 --> 00:03:51,854
Ne feledd, ha meg kell váltani az egyes
Az n elem esetleg n pozíciók,

78
00:03:51,854 --> 00:03:54,020
remélhetőleg, hogy megadja neked
egy ötlet, hogy a legrosszabb esetben

79
00:03:54,020 --> 00:03:57,770
üzemidő Big O n négyzeten.

80
00:03:57,770 --> 00:04:00,220
>> Ha a tömb tökéletesen
válogatni, minden, amit meg kell csinálni

81
00:04:00,220 --> 00:04:04,480
A nézd meg minden egyes elem
egyszer, és akkor kész.

82
00:04:04,480 --> 00:04:08,440
Tehát a legjobb esetben, ez az omega n.

83
00:04:08,440 --> 00:04:09,490
>> Én Doug Lloyd.

84
00:04:09,490 --> 00:04:11,760
Ez CS50.

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