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：真的嗎？