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