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