1
00:00:00,000 --> 00:00:05,726
>> [За възпроизвеждане на музика]

2
00:00:05,726 --> 00:00:08,600
Дъг LLOYD: Избор на сортиране е
алгоритъм, който, както може да се очаква,

3
00:00:08,600 --> 00:00:10,470
сортира набор от елементи.

4
00:00:10,470 --> 00:00:12,470
И алгоритъм изземване
е набор стъпка по стъпка

5
00:00:12,470 --> 00:00:15,260
на инструкции за попълването на дадена задача.

6
00:00:15,260 --> 00:00:17,580
>> В подбора сортирате
основната идея е тази,

7
00:00:17,580 --> 00:00:22,080
намерят най-малкия елемент и е сортиран
да го добавите в края на сортиран списък.

8
00:00:22,080 --> 00:00:26,970
Ефективно какво прави това е натрупването
а сортирани списък, един елемент в даден момент.

9
00:00:26,970 --> 00:00:29,800
Тя Премахване на Псевдокод
бихме могли да се посочи този алгоритъм

10
00:00:29,800 --> 00:00:34,490
както следва, повтарям това, докато
не несортиран елементи остават.

11
00:00:34,490 --> 00:00:38,660
Търсене чрез несортирани
данни, за да намерят най-малката стойност,

12
00:00:38,660 --> 00:00:44,130
След това сменяте най-малката стойност с
Първият елемент от сортиран част.

13
00:00:44,130 --> 00:00:47,130
>> Тя може да помогне да се визуализира това,
така че нека да погледнем на това.

14
00:00:47,130 --> 00:00:49,710
Така че това, Аз твърдя, е
сортиран масив и съм

15
00:00:49,710 --> 00:00:53,040
той посочи, като посочи, че всички
на елементите са оцветени в червено,

16
00:00:53,040 --> 00:00:54,420
те все още не са подредени.

17
00:00:54,420 --> 00:00:57,670
Това е цялото
несортиран част на масива.

18
00:00:57,670 --> 00:01:02,020
>> Така че нека да мине през етапите на
Избор на вид, за да сортирате този масив.

19
00:01:02,020 --> 00:01:05,296
Така че отново, ние ще се повтаря
докато не останат несортиран елементи.

20
00:01:05,296 --> 00:01:07,920
Ние ще търсим в по
данни, за да намерят най-малката стойност,

21
00:01:07,920 --> 00:01:11,990
и след това да сменяте тази стойност с
Първият елемент от сортиран част.

22
00:01:11,990 --> 00:01:14,380
>> Точно сега, отново, цялата
масив е сортиран част.

23
00:01:14,380 --> 00:01:16,534
Всички червени елементи са неразделени.

24
00:01:16,534 --> 00:01:18,700
Така че ние търсим в и
ние намираме най-малката стойност.

25
00:01:18,700 --> 00:01:20,533
Започваме в началото,
отидем до края,

26
00:01:20,533 --> 00:01:23,630
ние намираме най-малката стойност е един.

27
00:01:23,630 --> 00:01:24,860
Така че това е първа част.

28
00:01:24,860 --> 00:01:29,440
И тогава част втора, сменяте тази стойност с
първият елемент на несортиран част,

29
00:01:29,440 --> 00:01:31,340
или първата червен елемент.

30
00:01:31,340 --> 00:01:34,980
>> В този случай това би било
пет, така че можем да сменяте една и пет.

31
00:01:34,980 --> 00:01:37,320
Когато правим това, което можем
визуално се види, че ние сме

32
00:01:37,320 --> 00:01:41,260
премества най-малката ценен елемент
на масива, за самото начало.

33
00:01:41,260 --> 00:01:43,920
Ефективно сортиране този елемент.

34
00:01:43,920 --> 00:01:47,520
>> И така, ние наистина може да се потвърди
и посочва, че една, се сортира.

35
00:01:47,520 --> 00:01:52,080
И така, ние ще посочи сортирани част
на нашия масив, чрез оцветяване го синьо.

36
00:01:52,080 --> 00:01:53,860
>> Сега ние просто повторете процеса отново.

37
00:01:53,860 --> 00:01:57,430
Търсим през несортирани част на
масива, за да намерите най-малкия елемент.

38
00:01:57,430 --> 00:01:59,000
В този случай, това е две.

39
00:01:59,000 --> 00:02:02,100
>> Ние суап, че с първия
елемент от сортиран част.

40
00:02:02,100 --> 00:02:05,540
В този случай две също се случва да бъде
първият елемент на несортиран част.

41
00:02:05,540 --> 00:02:08,650
Така че ние суап две сам със себе си,
които наистина просто оставя двама

42
00:02:08,650 --> 00:02:11,257
където и да е, и това е сортирани.

43
00:02:11,257 --> 00:02:13,840
Продължавайки нататък, ние търсим в
да се намери най-малкия елемент.

44
00:02:13,840 --> 00:02:15,030
Това е три.

45
00:02:15,030 --> 00:02:17,650
Ние го сменяте с първия
елемент, който е пет.

46
00:02:17,650 --> 00:02:19,450
И сега три се сортира.

47
00:02:19,450 --> 00:02:22,440
>> Ние търсим в отново, и ние
намерят най-малкият елемент е четири.

48
00:02:22,440 --> 00:02:28,070
Ние го сменяте с първия елемент от
несортиран част, а сега четири се сортира.

49
00:02:28,070 --> 00:02:29,910
>> Ние намираме, че пет е
най-малкия елемент.

50
00:02:29,910 --> 00:02:32,900
Ние го сменяте с първия
елемент от сортиран част.

51
00:02:32,900 --> 00:02:34,740
И сега пет се сортира.

52
00:02:34,740 --> 00:02:36,660
>> И след това накрая, нашата
несортиран част се състои

53
00:02:36,660 --> 00:02:38,576
на само един елемент,
така че ние търсим в

54
00:02:38,576 --> 00:02:41,740
и ние откриваме, че шест е
малката, а в действителност, само елемент.

55
00:02:41,740 --> 00:02:44,906
И тогава можем да заявим, че това се сортира.

56
00:02:44,906 --> 00:02:47,530
И сега ние сме включен нашия масив
да бъде напълно несортирани

57
00:02:47,530 --> 00:02:52,660
в червено, за да напълно сортирани
в синьо, като се използва за избор на сортиране.

58
00:02:52,660 --> 00:02:54,920
>> Така че това, което е най-лошият сценарий тук?

59
00:02:54,920 --> 00:02:57,830
Ами в абсолютния-лошото
случай, ние трябва да погледнем над

60
00:02:57,830 --> 00:03:02,170
Всички елементи на масива
намерят най-малката е сортиран елемент,

61
00:03:02,170 --> 00:03:04,750
и ние трябва да се повтаря
този процес п пъти.

62
00:03:04,750 --> 00:03:09,090
След като за всеки елемент на масива
защото само в този алгоритъм,

63
00:03:09,090 --> 00:03:12,180
подреди един елемент в момента.

64
00:03:12,180 --> 00:03:13,595
>> Какво е най-добрия случай?

65
00:03:13,595 --> 00:03:15,040
Ами това е точно същото, нали?

66
00:03:15,040 --> 00:03:18,440
Ние всъщност трябва да продължава да преминете през
всеки един елемент от масива

67
00:03:18,440 --> 00:03:22,040
за да се потвърди, че това е,
В действителност, най-малкия елемент.

68
00:03:22,040 --> 00:03:26,760
>> Така че най-лошия случай на работа, ние
трябва да се повтаря един процес п пъти,

69
00:03:26,760 --> 00:03:28,960
веднъж за всеки от п елементи.

70
00:03:28,960 --> 00:03:31,940
И в най-добрия случай,
ние трябва да направим същото.

71
00:03:31,940 --> 00:03:35,340
>> Така че мисля обратно към нашия
изчислителна сложност инструментариум,

72
00:03:35,340 --> 00:03:39,250
какво според вас е най-лошото
При изпълнение за избор подреди?

73
00:03:39,250 --> 00:03:41,840
Какво мислиш, че е най-добрият
При изпълнение за избор подреди?

74
00:03:41,840 --> 00:03:44,760

75
00:03:44,760 --> 00:03:49,325
>> Знаете ли, предполагам, Big O на п квадрат,
и Big Omega на п квадрат?

76
00:03:49,325 --> 00:03:49,950
Вие искате да бъде прав.

77
00:03:49,950 --> 00:03:52,490
Това са, в действителност,
най-лошия случай и най-добрият случай продължава

78
00:03:52,490 --> 00:03:55,100
пъти, за избор на сортиране.

79
00:03:55,100 --> 00:03:56,260
>> Аз съм Дъг Лойд.

80
00:03:56,260 --> 00:03:58,600
Това е CS50.

81
00:03:58,600 --> 00:04:00,279