>> MARK GROZEN-史密斯：嗨，我是馬克 Grozen史密斯，這是快速排序。
就像插入排序和冒泡 排序，快速排序是一種算法
排序的列表或一個事物的數組。
為簡單起見，我們假設這些 事情是整數，但
知道快速排序的工作 不僅僅是數量多。
快速入門是比較複雜一點 比插入或泡沫，但它的
還更高效 在大多數情況下。
等待第二個。
難道他只是說“最 例“，而不是”所有“？
有趣的是，沒有。
不是所有的情況下都是相同的。
不要擔心這個細節，如果你 沒見過大O表示法還，但
快速排序是一種O（n平方）算法 在最壞的情況，就像
插入或冒泡排序。
然而，它典型地充當多 像一個舊的模擬米的算法。
為什麼呢？
我們會盡快給後來。
但是現在，就讓我們學習 快速排序是如何工作的。
>> 因此，讓我們走過Quicksorting這 從最小的整數數組
到最大。
在這裡，我們有6個整數， 5，1，3，8,4，7,9，和2。
首先，我們選擇的最後一個元素 這個數組 - 在這種情況下，2 -
並調用了“支點”。接下來，我們 開始看兩件事情 -
1，最低的指數，我將把 為留到右側
壁，並且，兩個，最左邊的 要素，我稱之為“當前
元素。“我們現在要做的是 看看所有其他元素，其他
比支點，並把所有的元素 比樞軸到較小
左牆和所有 比樞軸到較大
右牆。
然後，終於，我們將刪除該支點 右邊上牆把它之間
所有比它更小的數字 和所有較大的數字。
>> 因此，讓我們做到這一點。
拿起2，把牆上的 開始，並調用6“當前
元素“，所以我們想看看 我們目前的元素時，6。
而且，由於它比大 2，我們將它留在了
右牆。
然後，我們繼續來看看5作為我們 當前元素，看到這
是，再次，比樞軸較大，所以我們 離開它的地方是在右邊
壁的一側。
我們繼續前進。
我們目前的元素是 現在1和 - 哦。
現在，這是不同的。
當前元素現在比小 樞軸，所以我們要把它
向壁的左邊。
要做到這一點，讓我們切換 當前元素具有最低索引
坐在剛剛在牆上的權利。
現在，我們將牆上了一個索引 因此，圖1是在左邊
現在壁的一側。
>> 等待。
我只是混在的元素 右側牆上的，不是嗎？
不要擔心。
這很好。
我們關心現在唯一 是，所有這些元素的
右牆的塊頭大 比支點。
沒有實際的順序是假設呢。
>> 現在，回到分揀。
因此，我們繼續看 元件的其餘部分。
在這種情況下，我們可以看到，有 不及的其他元素
支點，所以我們把它們全部在 右側壁。
最後，我們得到當前元素 並認為它是支點。
現在，這意味著，我們有兩個 數組，第一個是各款
小在樞軸和左側 壁，所述第二感的
比樞軸到較大 右側的牆上。
我們希望把之間的支點元素 二，然後我們就會知道
該樞軸是在其右 最終排序的地方。
所以我們打開了第一個元素 右側壁與樞轉的，
我們知道樞軸的 在它的右側位置。
>> 然後，我們重複這個過程為 子陣列左和樞軸的權利。
自上次子陣列中只有一個 元長，我們知道這已經
排序的，因為你怎麼能出 命令，如果你只有一個元素？
對於右側的子陣列，我們 看，所述樞軸是5，和壁
是剛剛離開的6。
以及當前元素也 開始時為6。
所以圖6是大於5。
我們離開它的地方是在 右側的牆上。
現在，移動上，3小於5。
因此，我們的第一個元素打開它 恰到好處的牆。
現在，我感動了堵牆之一。
現在，移動到8。
圖8是大於5時， 所以我們離開它。
4小於5，因此，我們切換它。
而上。
>> 我們每次重複這個過程就 陣列的左側和右側。我們
選擇一個支點，做的比較 和創建的另一個水平向左和
右子數組。
這個遞歸調用將持續到 我們到達的時候，我們已經結束
瓜分了整個陣列成 剛子數組長度為1的。
從那裡，我們知道數組進行排序 因為每一個元素都有​​，在
某一點上，一直是一個樞軸。
換句話說，對於每個元素，所有 該數字的左側有一個更小
價值觀和所有的數字到 右有更大的價值。
>> 此方法效果非常好，如果在 選擇樞軸的值是
約在中間 範圍列表的值。
這意味著，當我們移動 周圍的元素，大約有盡可能多的
元素，以樞軸的左 因為有在右邊。
和的分而治之的性質 快速排序算法，然後採取
充分利用。
這將創建為O運行時（n日誌N，） 第n因為我們必須做N減1
在每一代和日誌比較 N，因為我們必須將列表
記錄n次。
然而，在最壞的情況下，這 算法其實是可以為O（n
平方。）假設在每一代中， 樞軸只是恰巧是
最小或最大的 我們正在整理的數字。
這將意味著打破列表 n次且用N減1
比較每一次。
因此，O n個平方。
>> 我們如何能改善的方法？
改善方法的一個好方法是 切下來的概率
運行時是有史以來實際上 二六，O n的平方。
記住這個最壞的情況，最壞的情況下 只能發生在
支點選擇始終是最高的 或陣列中的最低值。
以確保這是不太可能發生， 我們可以通過找到支點
選擇多個元素和 取中間值。
>> 我的名字叫馬克Grozen-史密斯， 這是CS50。
>> 為簡單起見，我們假設這些 事情是整數，但
知道Quicksert -
Quicksert？
抱歉。
>> 在這裡，我們有整數 6，5,1，3,8，4,9。
>> 揚聲器1：真的嗎？
>> 揚聲器2：不要停​​在那裡。
>> 揚聲器1：真的嗎？