[輕鬆影片] 想學「快速排序法」？來跳個舞吧！
https://youtu.be/ywWBy6J5gz8
#QuickSort #Algorithms #FunnyVideo
誰想出這種方法學快速排序法的啦～～（稱讚意味）
(*≥▽≤)ツ┏━┓
這是前不久，我瀏覽 Reddit 這個國外鄉民聚集地的 Programming 版時，無意中發現的。看到一半我嘴角就不爭氣地往上勾，然後那句鄉民金句就從我腦海中浮起來了：「可惡！這種東西不能只有我看到...（拇指）」
原連結是用一種匈牙利舞蹈，來展現快速排序法的原理。先簡單說明一下快速排序法原理，各位朋友們去看這支影片體會應該會更多：
「快速排序法」簡單來說，就是先把資料切成一半，然後把前半與後半開始逐一比較。只要是數字比較小的，就放到前面。數字比較大的，就放到後面。這樣一來，前方集合存放的都是相對小的數字，後方集合存放的都是相對大的數字。雖說大小數字已經分成兩群，但前方那群相對小的數字，現階段還沒能按照「小-->大」排列，只是把一堆跟後方比起來較小的數字，雜亂無章地聚集在一起而已。後方那群相對大的數字原理相同。
此時把前方與後方集合再分別切對半（這時應該有四個集合了），用剛剛一樣的手法，「前一」vs.「前二」，「後一」 vs.「後二」，比較小的放在「前一」、「後一」，比較大的放在「前二」、「後二」。就這樣，一份切成兩份、四份、八份...然後兩兩集合比較，小的數字交換到前方、大的數字交換到後方。一直切到集合內的個數 = 1 時，所有數字就按照「小-->大」排列完畢了。
如果我這麼說您還是不很瞭解，那就看影片吧！看完搭配我的說明，應該會很清楚的！「快速排序法」是演算法中「分治法」的代表作（見下方「演算法心得」），資訊科學本科系的學生，一定得瞭解「快速排序法」原理。也不少公司面試，用「快速排序法」來做第一輪篩選，看看哪些是屬於「瞭解狀況」、哪些又是「得過且過」的面試者。非常鼓勵各位朋友弄懂它！
---- （以下是個人修習博士班高等演算法後的小心得） ----
天底下「演算法」成千上萬，但萬變不離其宗，躲在每個演算法背後的原理大抵有三大類：
(1)「貪進法（Greedy，又稱貪婪演算法）」
(2)「分治法（Divide & Conquer，又稱分而治之法）」
(3)「動態規劃法（Dynamic Programming）」
當你遇到一個問題不知道該如何解，只要問自己：「這個問題用『貪進』、『分治』、『動態規劃』，哪一種手法好？」大致就會有答案。
「貪進法」是在每一步選擇時，都選擇「當下最有利」的，然後假設「結合所有『當下最有利』的選擇，結果也會是『最有利』的」。當然，我們都知道上面這句話不是永遠適用。不過「貪進法」算是比較簡單的「演算法」入門原理。
「分治法」是先把整個問題對切、對切、再對切。切到小到不能再小，然後去解決那個小問題，並期待把所有小問題的解答拼起來，就會是大問題的解答。剛剛您看的「快速排序法」，就是「分治法」的代表作！
「動態規劃法」會先設計一套「給分系統」，也就是對每一步的選擇「有多好」，設計一套「評分標準」。然後每解一步，就用這個「給分標準」記下剛剛那樣解有多漂亮，能得幾分。然後在做下一步選擇時，會計算下一步所有可能步數的得分，然後結合到目前為止所取得的分數，最後取「總分可能最高」的一條路。動態規劃法最被人稱道的是它靠給分系統，擁有「記取教訓」的能力，能累計從計算開始至今結果「有多好」。不像「貪進法」跟「分治法」眼光短淺，只看當下一步。雖然運算結果可能比較好，但計算量也是三種中最高的。
如果您覺得這支影片，或是我底下寫的「演算法心得」值得參考，就麻煩轉發分享給您 Facebook 的朋友喔！
快速排序法 在 Comparison Sort: Quick Sort(快速排序法) 的推薦與評價
Quick Sort(快速排序法) · pivot可以任意挑選，在此是固定挑選數列(矩陣)的最後一個元素。 · 在「新的數列」上只是重複相同的步驟(選pivot、調整數列)，可以利用遞迴( ... ... <看更多>
相關內容