1
00:00:00,000 --> 00:00:02,826
>> [Muzikos grojimo]

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

3
00:00:05,660 --> 00:00:09,370
>> Doug LLOYD: Taigi įterpimo Rūšiuoti kitas
algoritmas mes galime naudoti rūšiuoti masyvą.

4
00:00:09,370 --> 00:00:12,350
Už šio algoritmo idėja
yra sukurti savo rūšiuotą masyvo

5
00:00:12,350 --> 00:00:19,670
vietoje, perkeliant elementus iš
būdas, kaip jūs einate, kad paliktume vietos.

6
00:00:19,670 --> 00:00:22,240
Tai yra šiek tiek kitoks
nuo atrankos rūšiuoti ar burbulo

7
00:00:22,240 --> 00:00:25,460
rūšiuoti, pavyzdžiui, kur
mes koreguojant vietas,

8
00:00:25,460 --> 00:00:26,910
kur mes darome apsikeitimo sandoriais.

9
00:00:26,910 --> 00:00:29,760
>> Šiuo atveju tai, ką mes iš tikrųjų
darote, yra stumdomas elementai

10
00:00:29,760 --> 00:00:31,390
daugiau, iš kelio.

11
00:00:31,390 --> 00:00:34,030
Kaip veikia šį algoritmą
dirbti Pseudocode?

12
00:00:34,030 --> 00:00:37,646
Na tegul tiesiog pasakyti, kad savavališkai
Pirmasis elementas masyve yra rūšiuojami.

13
00:00:37,646 --> 00:00:38,770
Mes statome jį į vietą.

14
00:00:38,770 --> 00:00:42,660
>> Mes gonna go vieną elementą vienu metu ir
statyti, todėl pirmas dalykas, kurį mes matome

15
00:00:42,660 --> 00:00:43,890
yra vienas elementas, masyvo.

16
00:00:43,890 --> 00:00:47,720
Ir pagal apibrėžimą, vienas
elementas masyvas surūšiuotas.

17
00:00:47,720 --> 00:00:50,850
>> Tada mes šį procesą pakartoti until--
mes pakartoti šią procedūrą

18
00:00:50,850 --> 00:00:52,900
tol, kol visus elementus, yra rūšiuojami.

19
00:00:52,900 --> 00:00:57,770
Pažvelkite į kitą nerūšiuotų elemento ir
įdėkite ją į rūšiuotų dalį,

20
00:00:57,770 --> 00:01:01,209
perkeliant reikiamą skaičių
iš elementų, iš kelio.

21
00:01:01,209 --> 00:01:03,750
Tikimės, kad šis vizualizacija
padės jums pamatyti, ką tai

22
00:01:03,750 --> 00:01:05,980
vyksta su įterpimo rūšiuoti.

23
00:01:05,980 --> 00:01:08,010
>> Taigi dar kartą, čia mūsų
Visa nerūšiuotos masyvas,

24
00:01:08,010 --> 00:01:10,970
visus elementus, raudonai nurodyta.

25
00:01:10,970 --> 00:01:13,320
Ir tegul sekti
žingsniai mūsų Pseudocode.

26
00:01:13,320 --> 00:01:16,970
Pirmas dalykas, kurį mes darome, yra mes vadiname
pirmasis elementas masyvo, rūšiuojami.

27
00:01:16,970 --> 00:01:20,920
Taigi mes tiesiog sakys
penki, jūs dabar rūšiuojami.

28
00:01:20,920 --> 00:01:24,570
>> Tada mes pažvelgti į kitą
nerūšiuotų elementas masyve

29
00:01:24,570 --> 00:01:27,610
ir mes norime įrašyti, kad
į rūšiuojami dalį,

30
00:01:27,610 --> 00:01:29,750
perkeliant elementus virš.

31
00:01:29,750 --> 00:01:33,470
Taigi du yra šalia nerūšiuotų
elementas masyve.

32
00:01:33,470 --> 00:01:36,250
Akivaizdu, kad jis priklauso iki
penki, todėl tai, ką mes darysim

33
00:01:36,250 --> 00:01:41,580
yra tarsi surengti du skirta per sekundę,
pereiti penkis daugiau, ir tada įdėkite du

34
00:01:41,580 --> 00:01:43,210
prieš penkis, kur reikia eiti.

35
00:01:43,210 --> 00:01:45,280
Ir dabar mes galime pasakyti, kad du yra rūšiuojami.

36
00:01:45,280 --> 00:01:48,400
>> Taigi, kaip matote, mes tik tiek, kiek
pažvelgė dviejų elementų masyvą.

37
00:01:48,400 --> 00:01:50,600
Mes ne pažvelgė
poilsio ne visi, bet mes

38
00:01:50,600 --> 00:01:54,582
gavo šie du elementai surūšiuoti pagal
būdas perjungimo mechanizmą.

39
00:01:54,582 --> 00:01:56,410
>> Taigi, mes vėl pakartokite šį procesą.

40
00:01:56,410 --> 00:01:58,850
Pažvelkite į kitą nerūšiuotų
elementas, tai viena.

41
00:01:58,850 --> 00:02:04,010
Leiskite nuspręsti, kad skirta per sekundę,
pereiti viską daugiau, ir įdėti vieną

42
00:02:04,010 --> 00:02:05,570
kur jis turėtų eiti.

43
00:02:05,570 --> 00:02:08,110
>> Vėlgi, vis tiek, mes tik kada nors
pažvelgė į vieno, dviejų, ir penkių.

44
00:02:08,110 --> 00:02:12,480
Mes nežinome, ką dar ateina,
bet mes surūšiuoti šių trijų elementų.

45
00:02:12,480 --> 00:02:16,030
>> Kitas nerūšiuotos elementas yra
trys, todėl mes jį panaikinti.

46
00:02:16,030 --> 00:02:18,200
Mes pereinama, ką mes
reikia, į kurią, šį kartą

47
00:02:18,200 --> 00:02:21,820
tai dar ne viskas, kaip ir ankstesnis
du atvejai, tai tik penki.

48
00:02:21,820 --> 00:02:25,440
Ir tada mes klijuoti trys,
tarp dviejų ir penkių.

49
00:02:25,440 --> 00:02:27,849
>> Šeši yra šalia nerūšiuotų
elementas masyve.

50
00:02:27,849 --> 00:02:31,140
Ir iš tikrųjų šešių yra daugiau kaip penki, todėl
mes net nereikia daryti jokio Swapping.

51
00:02:31,140 --> 00:02:35,710
Mes galime tik smeigtuko šeši dešinę į
iš išrūšiuotų porcija pabaiga.

52
00:02:35,710 --> 00:02:38,270
>> Galiausiai, keturi yra
paskutinis nerūšiuotos elementas.

53
00:02:38,270 --> 00:02:42,060
Taigi mes jį panaikinti, pereinama
elementai turime pereiti per,

54
00:02:42,060 --> 00:02:43,780
ir tada įdėti keturis, jei ji priklauso.

55
00:02:43,780 --> 00:02:46,400
Ir dabar atrodo, mes tarsi
iš visų elementų.

56
00:02:46,400 --> 00:02:48,150
Atkreipkite dėmesį, su įterpimo
Rūšiuoti, mes neturėjome

57
00:02:48,150 --> 00:02:50,240
eiti pirmyn ir atgal per masyvo.

58
00:02:50,240 --> 00:02:54,720
Mes tik perėjo iš masyvo
vieną kartą, ir mes persikėlė dalykus

59
00:02:54,720 --> 00:02:59,870
kad mes jau norime susidūrė, siekiant
padaryti kambarį už naujų elementų.

60
00:02:59,870 --> 00:03:02,820
>> Taigi, kas blogiausiu atveju
scenarijus su įterpimo rūšiuoti?

61
00:03:02,820 --> 00:03:05,090
Blogiausiu atveju,
masyvas yra atvirkštine tvarka.

62
00:03:05,090 --> 00:03:11,180
Turite pereiti kiekvieną iš N elementų
iki n pozicijų, kiekvieną kartą, kai mes

63
00:03:11,180 --> 00:03:12,880
padaryti įdėjimo.

64
00:03:12,880 --> 00:03:15,720
Štai iš perkeliant daug.

65
00:03:15,720 --> 00:03:18,014
>> Geriausiu atveju,
array puikiai rūšiuojami.

66
00:03:18,014 --> 00:03:20,680
Ir tarsi kas atsitiko
su penkių ir šešių pavyzdyje,

67
00:03:20,680 --> 00:03:23,779
kur mes galėtume tiesiog ant smeigtuko
be daryti bet kokį perjungimą,

68
00:03:23,779 --> 00:03:24,820
mes norime iš esmės padaryti.

69
00:03:24,820 --> 00:03:27,560
>> Jei jūs galite įsivaizduoti, kad mūsų
masyvas buvo vienas per šešių,

70
00:03:27,560 --> 00:03:29,900
mes norime pradėti nuo
deklaruojant viena yra rūšiuojami.

71
00:03:29,900 --> 00:03:33,300
Du ateina po vieną, kad mes galime tik
sako, gerai, gerai vieno ir dviejų rūšiuojami.

72
00:03:33,300 --> 00:03:36,190
Trys ateina po du taip, gerai,
vieno ir dviejų ir trijų rūšiuojami.

73
00:03:36,190 --> 00:03:39,590
>> Mes ne priimant bet kokius sandorius, mes
tiesiog perkeldami savavališkai linija

74
00:03:39,590 --> 00:03:42,460
tarp rūšiuotus ir nerūšiuotus, kaip mes einame.

75
00:03:42,460 --> 00:03:46,646
Taip efektyviai, kaip mes padarėme, pavyzdžiui,
tekinimo elementus mėlyna, kaip mes toliau.

76
00:03:46,646 --> 00:03:48,270
Taigi, kas blogiausiu atveju Runtime, tada?

77
00:03:48,270 --> 00:03:51,854
Atminkite, kad jei mes turime pereiti kiekvieną iš
kad n elementų galbūt n pozicijos,

78
00:03:51,854 --> 00:03:54,020
tikiuosi, kad tau duoda
idėja, kad blogiausiu atveju

79
00:03:54,020 --> 00:03:57,770
Runtime yra Big O n kvadratu.

80
00:03:57,770 --> 00:04:00,220
>> Jei masyvas yra puikiai
rūšiuojamos, visi mes turime daryti

81
00:04:00,220 --> 00:04:04,480
yra pažvelgti kiekvieną elementą
vieną kartą, ir tada mes baigsite.

82
00:04:04,480 --> 00:04:08,440
Taigi geriausiu atveju, tai omega n.

83
00:04:08,440 --> 00:04:09,490
>> Aš Doug Lloyd.

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

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