1
00:00:00,000 --> 00:00:05,760

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD：所以在CS50，我們了解了
多種排序和搜索的

3
00:00:08,900 --> 00:00:09,442
算法。

4
00:00:09,442 --> 00:00:11,400
有時也可以是
一個小技巧，以保持

5
00:00:11,400 --> 00:00:14,161
跟踪什麼算法做什麼。

6
00:00:14,161 --> 00:00:15,910
我們真的只
撇去表面上也是如此，

7
00:00:15,910 --> 00:00:18,740
還有很多其他的搜索
和排序算法。

8
00:00:18,740 --> 00:00:21,780
所以在這部影片讓我們
只需要幾分鐘的時間

9
00:00:21,780 --> 00:00:24,980
嘗試和提煉每個算法
到其核心要素

10
00:00:24,980 --> 00:00:27,810
這樣你就可以記住的最
有關的重要信息

11
00:00:27,810 --> 00:00:31,970
並能夠闡明
差異，如果有必要的。

12
00:00:31,970 --> 00:00:34,220
>> 首先是選擇排序。

13
00:00:34,220 --> 00:00:38,210
後面的選擇排序的基本思想
被發現的最小的未分類的元素

14
00:00:38,210 --> 00:00:42,890
在一個陣列，並交換它與
該數組的第一個未排序的元素。

15
00:00:42,890 --> 00:00:46,620
我們說，在最壞情況下
的運行時間為：N的平方。

16
00:00:46,620 --> 00:00:50,060
如果你想召回原因，採取
來看看選擇排序視頻。

17
00:00:50,060 --> 00:00:54,560
最好的情況下運行時間
是也可為N的平方。

18
00:00:54,560 --> 00:00:58,910
>> 冒泡排序，背後的想法
一個是交換相鄰對。

19
00:00:58,910 --> 00:01:01,730
所以，這可以幫助你的關鍵
記住這裡的區別。

20
00:01:01,730 --> 00:01:04,920
選擇排序是，到目前為止，
找到smallest--泡沫

21
00:01:04,920 --> 00:01:06,790
排序是交換相鄰的一對。

22
00:01:06,790 --> 00:01:08,710
我們交換相鄰的一對
元件的，如果他們

23
00:01:08,710 --> 00:01:12,530
都失靈，從而有效地
泡到右側較大的因素，

24
00:01:12,530 --> 00:01:17,060
並在同一時間它也開始
移動到左側較小的元素。

25
00:01:17,060 --> 00:01:20,180
最壞情況下的情況下運行時間
冒泡排序為n的平方。

26
00:01:20,180 --> 00:01:23,476
最好的情況下運行時間
冒泡排序為n。

27
00:01:23,476 --> 00:01:25,350
因為在這種情況
我們不actually--

28
00:01:25,350 --> 00:01:27,141
我們可能不需要
做任何掉期的。

29
00:01:27,141 --> 00:01:31,026
我們只需要進行一次
通過在所有n個元素。

30
00:01:31,026 --> 00:01:34,600
>> 在插入排序中，
這裡基本思路正在發生變化。

31
00:01:34,600 --> 00:01:36,630
這就是關鍵字插入排序。

32
00:01:36,630 --> 00:01:39,630
我們正在經歷步驟一次
從陣列從左到右。

33
00:01:39,630 --> 00:01:41,670
當我們這樣做，我們
要轉變要素

34
00:01:41,670 --> 00:01:46,260
我們已經看到，以騰出空間
較小的需要適應的地方

35
00:01:46,260 --> 00:01:48,080
早在那個排序的部分。

36
00:01:48,080 --> 00:01:51,600
因此，我們所建立的有序陣列中的一個
元件在一個時間，從左到右，

37
00:01:51,600 --> 00:01:54,740
我們的東西轉移，以騰出空間。

38
00:01:54,740 --> 00:01:58,650
最糟糕的情況下的運行時間
插入排序為n的平方。

39
00:01:58,650 --> 00:02:02,380
最好的情況下的運行時間為n。

40
00:02:02,380 --> 00:02:05,380
>> 合併類別 - 關鍵字
這裡被分割和合併。

41
00:02:05,380 --> 00:02:08,949
我們分裂了全陣列，無論是
這六個要素，八大要素，

42
00:02:08,949 --> 00:02:13,790
萬elements--將其切
降了一半，一半，一半，

43
00:02:13,790 --> 00:02:17,720
直到我們有下陣
正一個元素的數組。

44
00:02:17,720 --> 00:02:19,470
一組N個一個元素的數組。

45
00:02:19,470 --> 00:02:22,640
因此，我們開始與一個
1000元陣，

46
00:02:22,640 --> 00:02:26,550
而我們得到的地步，我們
有1000個一單元陣列。

47
00:02:26,550 --> 00:02:30,990
然後，我們開始合併這些子陣列
回到一起以正確的順序。

48
00:02:30,990 --> 00:02:34,860
因此，我們採取兩個一元的陣列
並創建一個兩元素數組。

49
00:02:34,860 --> 00:02:38,180
我們需要兩兩元素數組
並創建一個四元數組

50
00:02:38,180 --> 00:02:43,900
等等等等，直到我們
再次重修一個n元素的數組。

51
00:02:43,900 --> 00:02:48,410
>> 最糟糕的情況下的運行時間
歸併排序是N次日誌N。

52
00:02:48,410 --> 00:02:52,390
我們有n個元素，但
這個重新組合的過程

53
00:02:52,390 --> 00:02:56,960
需要記錄n步獲得
回到一個完整的陣列。

54
00:02:56,960 --> 00:03:01,160
運行時，最好的情況下也的n log
5.2，由於這個過程中並沒有真正的

55
00:03:01,160 --> 00:03:04,090
關心陣列是否
排序或不下手。

56
00:03:04,090 --> 00:03:07,590
的過程是相同的，有
沒辦法短路的事情。

57
00:03:07,590 --> 00:03:11,610
因此n日誌N在最壞情況下，
N日誌N的最好的情況下。

58
00:03:11,610 --> 00:03:13,960
>> 我們談了大約兩個
搜索算法。

59
00:03:13,960 --> 00:03:16,230
所以線性搜索是關於迭代。

60
00:03:16,230 --> 00:03:19,500
我們繼續進行跨越陣列
一次，由左到右，

61
00:03:19,500 --> 00:03:21,950
努力尋找數
我們正在尋找。

62
00:03:21,950 --> 00:03:24,550
最壞情況下的運行時間是n的大澳。

63
00:03:24,550 --> 00:03:27,610
這可能需要我們遍歷
橫跨每一個元件

64
00:03:27,610 --> 00:03:30,660
找到我們正在尋找的元素
為，無論是在最後的位置，

65
00:03:30,660 --> 00:03:31,630
或根本沒有。

66
00:03:31,630 --> 00:03:34,720
但是，我們不能確認，直到
我們已經看過了一切。

67
00:03:34,720 --> 00:03:36,730
米最好的情況，我們馬上找到。

68
00:03:36,730 --> 00:03:41,060
最好的情況下的運行時間
線性搜索是1歐米茄。

69
00:03:41,060 --> 00:03:43,689
>> 最後，出現了二分搜索，
這就需要配套陣列。

70
00:03:43,689 --> 00:03:45,605
請記住，這是一個非常
重要的考慮因素

71
00:03:45,605 --> 00:03:47,155
與二進制搜索工作時。

72
00:03:47,155 --> 00:03:50,180
這是一個先決條件使用它 - 
你正在尋找通過數組

73
00:03:50,180 --> 00:03:52,160
必須進行排序。

74
00:03:52,160 --> 00:03:54,500
否則，關鍵字
是分而治之。

75
00:03:54,500 --> 00:03:58,310
拆分數組半
消除一半的元素

76
00:03:58,310 --> 00:04:00,780
每一次當你繼續完成。

77
00:04:00,780 --> 00:04:04,330
由於這種分而治之的
和分裂的事情了一半的方法，

78
00:04:04,330 --> 00:04:07,450
最壞情況下的運行時間
的二進制搜索是

79
00:04:07,450 --> 00:04:11,730
日誌N，其基本上
不是線性搜索n值更好。

80
00:04:11,730 --> 00:04:13,570
在最好的情況運行時間仍為之一。

81
00:04:13,570 --> 00:04:17,010
>> 我們可能會立即發現
我們第一次做一個劃分，但是，

82
00:04:17,010 --> 00:04:19,339
再次，請記住，
雖然二進制搜索

83
00:04:19,339 --> 00:04:24,030
大大高於線性搜索更好
由於是日誌N對N，

84
00:04:24,030 --> 00:04:27,110
你可能要經過工作
先整理你的陣列中，這

85
00:04:27,110 --> 00:04:32,010
可能會使它不那麼有效視
在迭代排序的大小。

86
00:04:32,010 --> 00:04:35,250
>> 我是道格·勞埃德，這是CS50。

87
00:04:35,250 --> 00:04:36,757