今天是本系列進入 JavaScript 主題的第一天，那麼就先寫個 前陣子面試 時遇到的快速排序法吧！
本系列文已經重新編校彙整編輯成冊，並正式出版囉！
《前端三十：從 HTML 到瀏覽器渲染的前端開發者必備心法》好評販售中！
喜歡我文章內容的讀者們，歡迎您 前往購買 支持！
來寫個由小到大的版本吧，不囉嗦直接上 Code：
function quickSort(arr) {
if (arr.length < 2) return arr
const [p, ...ary] = arr
const left = [], right = []
ary.forEach(c => {
if (c < p) left.push(c)
else right.push(c)
})
return [...quickSort(left), p, ...quickSort(right)]
}
用的空間有點多，歡迎高手幫補充原地交換版本的 XD
快速排序的基本概念就是先挑出一個 樞紐（pivot），接著將其他元素與樞紐輪流比較，在由小到大的情況中，比它小的往前放，比它大的往後放，放完的同時也就把樞紐的位置固定好了；接著再對「比他大的部分」及「比他小的部分」個別做一次一樣的事，周而復始，直到陣列為空或只有一個元素就直接回傳；這樣就完成排序囉～
不夠清楚嗎？這裡有 匈牙利傳統舞蹈版本的說明。
以上，就是今天的快速排序法，大家是不是學會了呢？我們明天見～
...
...
...
欸等等，快速排序是寫出來了啦，但你有沒有想過，為什麼要練習演算法？
先思考一下，演算法的本質是什麼？其實就只是前人經驗與智慧的累積，是一些優秀的解決事情的方法。
大推這部 TedEd 的影片，淺顯易懂的說明了好的演算法效果有多驚人！
如果能理解各個演算法的思考過程，遇到合適的情境便能套用，甚至觸類旁通，思考出更好的解決方案；例如 Tim Peters 將 Merge sort 與 Insertion sort 的優點結合，利用原始資料中連續升序或降序的片段，進一步優化了排序，發明了 Timsort。
換言之，學習演算法，就如同是在學習高手們的思考方式，讓你在面對問題時，能找出更「聰明」的解決方法。
那為什麼許多公司行號的面試都喜歡考演算法呢？我認為有兩種可能：
第 1 種情況的公司其實還不少，可能一些熱門的職位求職者眾多，徵才方希望透過設定好的門檻，快速篩選出合適的人選，而演算法也會是門檻之一。
第 2 種情況，通常就是讓許多求職者感到害怕的現場筆試甚至白板題；但從徵才方的角度思考一下，其實也不用太過害怕，畢竟就只是想看你的思考邏輯，而不是要你一口氣默寫出最佳解，通常面試官也會給予適當的引導，只要順順的照著自己思考問題的模式，與團隊思考方式契合的人也自然會得到青睞。
雖然有人開玩笑說「面試造火箭，工作擰螺絲」，但演算法仍然是熱門的面試題目來源 XD
當然，有公司會考就有人會準備，訪間也有許多練習演算法的解題網站，最紅的莫過於 LeetCode，除了網羅全球各大公司的面試考古題外，在解題後能看到解題時間等數據指標，付費版的甚至有模擬面試，可以說所有軟體工程相關領域的求職者，或多或少都會在這打滾一陣子。
除了 LeetCode 外，我個人比較喜歡的是另一個解題網站：CodeWars，多了經驗值、等級、戰隊、排行榜等許多遊戲化的要素，並開放讓所有使用者自創題目，上面除了基本的演算法題型外，還有各種產業可能遇到的真實問題，甚至是 Code Golf 等等，讓你刷題不無聊。各種生活化的題型解起來也是別有一番樂趣。之前筆者有寫過另一篇 CodeWars 刷題心得分享，有興趣的讀者也可以參考一下。
刻意練習是很重要的事情，畢竟只是讀過看過，並不能讓人真正學會一件新事物；但我認為 目的只是通過面試的刻意練習演算法，是毫無意義的。透過大量的刷題，也許可以熟記這些演算法考古題的題型，但如果不能真正的認識、理解、掌握，進而內化成自己的功力，即使刷題刷好刷滿，最終也只是淪為背誦答案的考試機器。
演算法與資料結構一直是軟體工程中重要的基礎學科，熟練掌握其中的知識也是發展職涯過程的必經之路；為了求職刷好刷滿，比不上為了讓自己更好更強的刻意練習。
這次真的是本篇文章的結尾了，我們大家明天見～
筆者
Gary
半路出家網站工程師；半生熟的前端加上一點點的後端。
喜歡音樂，喜歡學習、分享，也喜歡當個遊戲宅。相信一切安排都是最好的路。
這個快速排序法是我看過最簡單易懂的版本，而且有抓到精髓XD
不過缺點就如文章裡面講的，花費太多空間了
如果要改成原地交換版本的話其實要花不少時間而且複雜滿多XD
這邊附上一個之前寫過的原地交換版本（出自一起用 JavaScript 來複習經典排序法吧！）
function quickSort = (arr) => {
const swap = (array, i , j) => {
[array[i], array[j]] = [array[j], array[i]];
}
const partition = (array, start, end) => {
let splitIndex = start + 1;
for (let i = start + 1; i <= end; i++) {
if (array[i] < array[start]) {
swap(array, i, splitIndex);
splitIndex++;
}
}
// 記得把 pivot 跟最後一個比它小的元素互換
swap(array, start, splitIndex - 1);
return splitIndex - 1;
}
const _quickSort = (array, start, end) => {
if (start >= end) return array;
// 在 partition 裡面調整數列，並且回傳 pivot 的 index
const middle = partition(array, start, end);
_quickSort(array, start, middle - 1);
_quickSort(array, middle + 1, end);
return array;
};
return _quickSort(arr, 0, arr.length - 1);
}
謝謝大大幫補充～
你的版本真的好精簡，謝謝分享
另外其實可以直接嵌入 youtube 影片，不知道作者用圖片在連結影片是有別的用意嗎?
原來可以直接嵌入嗎！?
我用加入 Youtube 連結跑出來的也是圖片連結，我以為不行XD
可以 好像只差在影片有 ![Yes]
我以為 Yes 只是圖片描述，就改掉了XD
感謝！
下次真的不現場示範刷題嗎 :D 
我也來個跳舞版的 
function quickSort_dance_version(array, left, right, compare_func) {
let print = (head) => {
let decorate = (i) => {
let value = array[i];
let msg = value;
if (i == focus)
msg = "(" + msg + ")";
if (i == cursor)
msg = "#" + msg;
if (i == left)
msg = "[" + msg;
if (i == right)
msg = msg + "]";
return msg;
};
let str = head;
for (let i = 0; i < array.length; ++i)
str += decorate(i) + ",";
console.log(str);
}
let swap = (array, x, y) => {
[array[x], array[y]] = [array[y], array[x]];
};
let swap_condition = (array, focus, cursor) => {
let cursor_value = array[cursor];
let focus_value = array[focus];
if (focus < cursor) // 主角在左邊
return compare_func(focus_value, cursor_value);
if (cursor < focus) // 主角在右邊
return compare_func(cursor_value, focus_value);
return false;
};
let focus = left; // 主角
let cursor_offset = -1; // 一開始往左移動
let cursor = right;
if (focus >= cursor)
return;
while (true) {
print("排序過程 array : ");
if (swap_condition(array, focus, cursor)) {
swap(array, focus, cursor); // 交換值
[focus, cursor] = [cursor, focus]; // 交換索引
cursor_offset *= -1; // 換方向
print("進行交換 array : ");
}
cursor += cursor_offset;
if (focus == cursor) { // 結束交叉
print("結束交叉 array : ");
quickSort_dance_version(array, left, focus - 1, compare_func);
quickSort_dance_version(array, focus + 1, right, compare_func);
return;
}
}
}
let source = [3, 0, 1, 8, 7, 2, 5, 4, 9, 6];
console.log(source);
quickSort_dance_version(source, 0, 9, (x, y) => x > y);
console.log(source);
不使用遞迴而使用stack版本:
function quickSort(array) {
const stack = [];
stack.push(0);
stack.push(array.length - 1);
while (stack.length > 0) {
const end = stack.pop();
const start = stack.pop();
if (end > start) { //如果仍然是一個範圍
const pivot = array[start];
let l = start + 1;
let r = end;
for (; ;) {
while (r > start && array[r] >= pivot) {
r -= 1;
}
while (l <= r && array[l] <= pivot) {
l += 1;
}
if (l < r) {
const temp = array[l];
array[l] = array[r];
array[r] = temp;
} else { //如果l已超出r的位置
if (r > start) {
const temp = array[start];
array[start] = array[r];
array[r] = temp;
}
break; //這裡才跳出去
}
}
if (r > start) {
stack.push(start);
stack.push(r - 1);
}
if (r < end) { //如果r有異動過
stack.push(r + 1);
stack.push(end);
}
}
}
}
let arr=[8,6,1,10,5,3,9,2,7,4];
console.log(quickSort(arr))
iThome鐵人賽
看影片追技術