1
00:00:00,000 --> 00:00:07,270

2
00:00:07,270 --> 00:00:10,390
>> MARK GROZEN-史密斯：嗨，我是马克
Grozen史密斯，这是快速排序。

3
00:00:10,390 --> 00:00:13,520
就像插入排序和冒泡
排序，快速排序是一种算法

4
00:00:13,520 --> 00:00:15,720
排序的列表或一个事物的数组。

5
00:00:15,720 --> 00:00:19,080
为简单起见，我们假设这些
事情是整数，但

6
00:00:19,080 --> 00:00:22,060
知道快速排序的工作
不仅仅是数量多。

7
00:00:22,060 --> 00:00:24,720
快速入门是比较复杂一点
比插入或泡沫，但它的

8
00:00:24,720 --> 00:00:27,560
还更高效
在大多数情况下。

9
00:00:27,560 --> 00:00:28,150
等待第二个。

10
00:00:28,150 --> 00:00:30,760
难道他只是说“最
例“，而不是”所有“？

11
00:00:30,760 --> 00:00:31,710
有趣的是，没有。

12
00:00:31,710 --> 00:00:33,560
不是所有的情况下都是相同的。

13
00:00:33,560 --> 00:00:36,650
不要担心这个细节，如果你
没见过大O表示法还，但

14
00:00:36,650 --> 00:00:39,730
快速排序是一种O（n平方）算法
在最坏的情况，就像

15
00:00:39,730 --> 00:00:41,430
插入或冒泡排序。

16
00:00:41,430 --> 00:00:44,950
然而，它典型地充当多
像一个旧的模拟米的算法。

17
00:00:44,950 --> 00:00:45,750
为什么呢？

18
00:00:45,750 --> 00:00:46,810
我们会尽快给后来。

19
00:00:46,810 --> 00:00:49,610
但是现在，就让我们学习
快速排序是如何工作的。

20
00:00:49,610 --> 00:00:53,080
>> 因此，让我们走过Quicksorting这
从最小的整数数组

21
00:00:53,080 --> 00:00:54,260
到最大。

22
00:00:54,260 --> 00:01:00,110
在这里，我们有6个整数，
5，1，3，8,4，7,9，和2。

23
00:01:00,110 --> 00:01:03,480
首先，我们选择的最后一个元素
这个数组 - 在这种情况下，2  - 

24
00:01:03,480 --> 00:01:06,870
并调用了“支点”。接下来，我们
开始看两件事情 - 

25
00:01:06,870 --> 00:01:10,220
1，最低的指数，我将把
为留到右侧

26
00:01:10,220 --> 00:01:13,970
壁，并且，两个，最左边的
要素，我称之为“当前

27
00:01:13,970 --> 00:01:17,260
元素。“我们现在要做的是
看看所有其他元素，其他

28
00:01:17,260 --> 00:01:20,930
比支点，并把所有的元素
比枢轴到较小

29
00:01:20,930 --> 00:01:24,140
左墙和所有
比枢轴到较大

30
00:01:24,140 --> 00:01:25,570
右墙。

31
00:01:25,570 --> 00:01:29,560
然后，终于，我们将删除该支点
右边上墙把它之间

32
00:01:29,560 --> 00:01:32,970
所有比它更小的数字
和所有较大的数字。

33
00:01:32,970 --> 00:01:34,460
>> 因此，让我们做到这一点。

34
00:01:34,460 --> 00:01:38,540
拿起2，把墙上的
开始，并调用6“当前

35
00:01:38,540 --> 00:01:41,590
元素“，所以我们想看看
我们目前的元素时，6。

36
00:01:41,590 --> 00:01:44,200
而且，由于它比大
2，我们将它留在了

37
00:01:44,200 --> 00:01:45,610
右墙。

38
00:01:45,610 --> 00:01:48,980
然后，我们继续来看看5作为我们
当前元素，看到这

39
00:01:48,980 --> 00:01:51,840
是，再次，比枢轴较大，所以我们
离开它的地方是在右边

40
00:01:51,840 --> 00:01:53,190
壁的一侧。

41
00:01:53,190 --> 00:01:53,880
我们继续前进。

42
00:01:53,880 --> 00:01:56,750
我们目前的元素是
现在1和 - 哦。

43
00:01:56,750 --> 00:01:58,030
现在，这是不同的。

44
00:01:58,030 --> 00:02:00,890
当前元素现在比小
枢轴，所以我们要把它

45
00:02:00,890 --> 00:02:02,570
向壁的左边。

46
00:02:02,570 --> 00:02:06,555
要做到这一点，让我们切换
当前元素具有最低索引

47
00:02:06,555 --> 00:02:07,970
坐在刚刚在墙上的权利。

48
00:02:07,970 --> 00:02:14,050

49
00:02:14,050 --> 00:02:17,570
现在，我们将墙上了一个索引
因此，图1是在左边

50
00:02:17,570 --> 00:02:19,750
现在壁的一侧。

51
00:02:19,750 --> 00:02:20,310
>> 等待。

52
00:02:20,310 --> 00:02:23,450
我只是混在的元素
右侧墙上的，不是吗？

53
00:02:23,450 --> 00:02:23,890
不要担心。

54
00:02:23,890 --> 00:02:24,930
这很好。

55
00:02:24,930 --> 00:02:27,570
我们关心现在唯一
是，所有这些元素的

56
00:02:27,570 --> 00:02:29,570
右墙的块头大
比支点。

57
00:02:29,570 --> 00:02:31,760
没有实际的顺序是假设呢。

58
00:02:31,760 --> 00:02:33,200
>> 现在，回到分拣。

59
00:02:33,200 --> 00:02:35,840
因此，我们继续看
元件的其余部分。

60
00:02:35,840 --> 00:02:39,075
在这种情况下，我们可以看到，有
不及的其他元素

61
00:02:39,075 --> 00:02:42,100
支点，所以我们把它们全部在
右侧壁。

62
00:02:42,100 --> 00:02:45,980
最后，我们得到当前元素
并认为它是支点。

63
00:02:45,980 --> 00:02:48,830
现在，这意味着，我们有两个
数组，第一个是各款

64
00:02:48,830 --> 00:02:51,820
小在枢轴和左侧
壁，所述第二感的

65
00:02:51,820 --> 00:02:54,500
比枢轴到较大
右侧的墙上。

66
00:02:54,500 --> 00:02:57,040
我们希望把之间的支点元素
二，然后我们就会知道

67
00:02:57,040 --> 00:03:01,000
该枢轴是在其右
最终排序的地方。

68
00:03:01,000 --> 00:03:04,980
所以我们打开了第一个元素
右侧壁与枢转的，

69
00:03:04,980 --> 00:03:06,410
我们知道枢轴的
在它的右侧位置。

70
00:03:06,410 --> 00:03:11,130

71
00:03:11,130 --> 00:03:15,650
>> 然后，我们重复这个过程为
子阵列左和枢轴的权利。

72
00:03:15,650 --> 00:03:18,700
自上次子阵列中只有一个
元长，我们知道这已经

73
00:03:18,700 --> 00:03:22,480
排序的，因为你怎么能出
命令，如果你只有一个元素？

74
00:03:22,480 --> 00:03:28,860
对于右侧的子阵列，我们
看，所述枢轴是5，和壁

75
00:03:28,860 --> 00:03:32,250
是刚刚离开的6。

76
00:03:32,250 --> 00:03:34,970
以及当前元素也
开始时为6。

77
00:03:34,970 --> 00:03:36,200
所以图6是大于5。

78
00:03:36,200 --> 00:03:38,590
我们离开它的地方是在
右侧的墙上。

79
00:03:38,590 --> 00:03:41,060
现在，移动上，3小于5。

80
00:03:41,060 --> 00:03:44,160
因此，我们的第一个元素打开它
恰到好处的墙。

81
00:03:44,160 --> 00:03:47,944

82
00:03:47,944 --> 00:03:50,750
现在，我感动了堵墙之一。

83
00:03:50,750 --> 00:03:53,010
现在，移动到8。

84
00:03:53,010 --> 00:03:56,480
图8是大于5时，
所以我们离开它。

85
00:03:56,480 --> 00:03:58,720
4小于5，因此，我们切换它。

86
00:03:58,720 --> 00:04:02,950

87
00:04:02,950 --> 00:04:03,570
而上。

88
00:04:03,570 --> 00:04:04,820
而上。

89
00:04:04,820 --> 00:04:10,190

90
00:04:10,190 --> 00:04:13,670
>> 我们每次重复这个过程就
阵列的左侧和右侧。我们

91
00:04:13,670 --> 00:04:17,010
选择一个支点，做的比较
和创建的另一个水平向左和

92
00:04:17,010 --> 00:04:18,240
右子数组。

93
00:04:18,240 --> 00:04:21,500
这个递归调用将持续到
我们到达的时候，我们已经结束

94
00:04:21,500 --> 00:04:25,290
瓜分了整个阵列成
刚子数组长度为1的。

95
00:04:25,290 --> 00:04:28,060
从那里，我们知道数组进行排序
因为每一个元素都有，在

96
00:04:28,060 --> 00:04:29,330
某一点上，一直是一个枢轴。

97
00:04:29,330 --> 00:04:32,720
换句话说，对于每个元素，所有
该数字的左侧有一个更小

98
00:04:32,720 --> 00:04:36,420
价值观和所有的数字到
右有更大的价值。

99
00:04:36,420 --> 00:04:38,980
>> 此方法效果非常好，如果在
选择枢轴的值是

100
00:04:38,980 --> 00:04:41,930
约在中间
范围列表的值。

101
00:04:41,930 --> 00:04:45,630
这意味着，当我们移动
周围的元素，大约有尽可能多的

102
00:04:45,630 --> 00:04:48,390
元素，以枢轴的左
因为有在右边。

103
00:04:48,390 --> 00:04:52,380
和的分而治之的性质
快速排序算法，然后采取

104
00:04:52,380 --> 00:04:53,850
充分利用。

105
00:04:53,850 --> 00:04:57,500
这将创建为O运行时（n日志N，）
第n因为我们必须做N减1

106
00:04:57,500 --> 00:05:01,640
在每一代和日志比较
N，因为我们必须将列表

107
00:05:01,640 --> 00:05:03,210
记录n次。

108
00:05:03,210 --> 00:05:06,160
然而，在最坏的情况下，这
算法其实是可以为O（n

109
00:05:06,160 --> 00:05:09,850
平方。）假设在每一代中，
枢轴只是恰巧是

110
00:05:09,850 --> 00:05:12,520
最小或最大的
我们正在整理的数字。

111
00:05:12,520 --> 00:05:15,870
这将意味着打破列表
n次且用N减1

112
00:05:15,870 --> 00:05:17,690
比较每一次。

113
00:05:17,690 --> 00:05:20,490
因此，O n个平方。

114
00:05:20,490 --> 00:05:22,000
>> 我们如何能改善的方法？

115
00:05:22,000 --> 00:05:25,100
改善方法的一个好方法是
切下来的概率

116
00:05:25,100 --> 00:05:28,150
运行时是有史以来实际上
二六，O n的平方。

117
00:05:28,150 --> 00:05:31,860
记住这个最坏的情况，最坏的情况下
只能发生在

118
00:05:31,860 --> 00:05:35,320
支点选择始终是最高的
或阵列中的最低值。

119
00:05:35,320 --> 00:05:38,630
以确保这是不太可能发生，
我们可以通过找到支点

120
00:05:38,630 --> 00:05:42,610
选择多个元素和
取中间值。

121
00:05:42,610 --> 00:05:44,650
>> 我的名字叫马克Grozen-史密斯，
这是CS50。

122
00:05:44,650 --> 00:05:47,790

123
00:05:47,790 --> 00:05:50,930
>> 为简单起见，我们假设这些
事情是整数，但

124
00:05:50,930 --> 00:05:51,970
知道Quicksert  - 

125
00:05:51,970 --> 00:05:53,160
Quicksert？

126
00:05:53,160 --> 00:05:55,200
抱歉。

127
00:05:55,200 --> 00:06:02,000
>> 在这里，我们有整数
6，5,1，3,8，4,9。

128
00:06:02,000 --> 00:06:03,200
>> 扬声器1：真的吗？

129
00:06:03,200 --> 00:06:04,850
>> 扬声器2：不要停​​在那里。

130
00:06:04,850 --> 00:06:06,100
>> 扬声器1：真的吗？

131
00:06:06,100 --> 00:06:08,491