iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 6
5
Modern Web

前端三十 - 成為更好的前端工程師系列 第 6

06. [JS] 請你在旁邊的白板寫個快速排序演算法。

https://ithelp.ithome.com.tw/upload/images/20190922/20111380uYRlZy0uJ3.jpg

今天是本系列進入 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),接著將其他元素與樞紐輪流比較,在由小到大的情況中,比它小的往前放,比它大的往後放,放完的同時也就把樞紐的位置固定好了;接著再對「比他大的部分」及「比他小的部分」個別做一次一樣的事,周而復始,直到陣列為空或只有一個元素就直接回傳;這樣就完成排序囉~

不夠清楚嗎?這裡有 匈牙利傳統舞蹈版本的說明

Yes

以上,就是今天的快速排序法,大家是不是學會了呢?我們明天見~

...
...
...

欸等等,快速排序是寫出來了啦,但你有沒有想過,為什麼要練習演算法?

演算法

先思考一下,演算法的本質是什麼?其實就只是前人經驗與智慧的累積,是一些優秀的解決事情的方法。

大推這部 TedEd 的影片,淺顯易懂的說明了好的演算法效果有多驚人!

Yes

如果能理解各個演算法的思考過程,遇到合適的情境便能套用,甚至觸類旁通,思考出更好的解決方案;例如 Tim PetersMerge sortInsertion sort 的優點結合,利用原始資料中連續升序或降序的片段,進一步優化了排序,發明了 Timsort

換言之,學習演算法,就如同是在學習高手們的思考方式,讓你在面對問題時,能找出更「聰明」的解決方法。

面試

那為什麼許多公司行號的面試都喜歡考演算法呢?我認為有兩種可能:

  1. 把演算法當成一種門檻,認為熟知這些是這個職位的基本條件
  2. 藉由一個已知最佳解的問題,想鑑定求職者的邏輯是否正確、思路是否靈活清晰

第 1 種情況的公司其實還不少,可能一些熱門的職位求職者眾多,徵才方希望透過設定好的門檻,快速篩選出合適的人選,而演算法也會是門檻之一。

第 2 種情況,通常就是讓許多求職者感到害怕的現場筆試甚至白板題;但從徵才方的角度思考一下,其實也不用太過害怕,畢竟就只是想看你的思考邏輯,而不是要你一口氣默寫出最佳解,通常面試官也會給予適當的引導,只要順順的照著自己思考問題的模式,與團隊思考方式契合的人也自然會得到青睞。

雖然有人開玩笑說「面試造火箭,工作擰螺絲」,但演算法仍然是熱門的面試題目來源 XD

刻意練習

當然,有公司會考就有人會準備,訪間也有許多練習演算法的解題網站,最紅的莫過於 LeetCode,除了網羅全球各大公司的面試考古題外,在解題後能看到解題時間等數據指標,付費版的甚至有模擬面試,可以說所有軟體工程相關領域的求職者,或多或少都會在這打滾一陣子。

除了 LeetCode 外,我個人比較喜歡的是另一個解題網站:CodeWars,多了經驗值、等級、戰隊、排行榜等許多遊戲化的要素,並開放讓所有使用者自創題目,上面除了基本的演算法題型外,還有各種產業可能遇到的真實問題,甚至是 Code Golf 等等,讓你刷題不無聊。各種生活化的題型解起來也是別有一番樂趣。之前筆者有寫過另一篇 CodeWars 刷題心得分享,有興趣的讀者也可以參考一下。

刻意練習是很重要的事情,畢竟只是讀過看過,並不能讓人真正學會一件新事物;但我認為 目的只是通過面試的刻意練習演算法,是毫無意義的。透過大量的刷題,也許可以熟記這些演算法考古題的題型,但如果不能真正的認識、理解、掌握,進而內化成自己的功力,即使刷題刷好刷滿,最終也只是淪為背誦答案的考試機器。

結語

演算法與資料結構一直是軟體工程中重要的基礎學科,熟練掌握其中的知識也是發展職涯過程的必經之路;為了求職刷好刷滿,比不上為了讓自己更好更強的刻意練習。

這次真的是本篇文章的結尾了,我們大家明天見~

參考資料

筆者

Gary

半路出家網站工程師;半生熟的前端加上一點點的後端。
喜歡音樂,喜歡學習、分享,也喜歡當個遊戲宅。

相信一切安排都是最好的路。


上一篇
05. [CSS] 元素選取器是如何運作的?
下一篇
07. [JS] 瀏覽器 DOM 元素的事件代理是指什麼?
系列文
前端三十 - 成為更好的前端工程師31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中
2
huli
iT邦新手 3 級 ‧ 2019-09-22 20:12:10

這個快速排序法是我看過最簡單易懂的版本,而且有抓到精髓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);
}
Gary iT邦新手 5 級 ‧ 2019-09-22 20:39:23 檢舉

謝謝大大幫補充~
/images/emoticon/emoticon41.gif

1
hannahpun
iT邦新手 4 級 ‧ 2019-09-22 23:48:13

你的版本真的好精簡,謝謝分享

看更多先前的回應...收起先前的回應...
hannahpun iT邦新手 4 級 ‧ 2019-09-22 23:55:17 檢舉

另外其實可以直接嵌入 youtube 影片,不知道作者用圖片在連結影片是有別的用意嗎?

Gary iT邦新手 5 級 ‧ 2019-09-23 00:07:33 檢舉

原來可以直接嵌入嗎!?
我用加入 Youtube 連結跑出來的也是圖片連結,我以為不行XD

hannahpun iT邦新手 4 級 ‧ 2019-09-23 10:43:57 檢舉

可以 好像只差在影片有 ![Yes]

Gary iT邦新手 5 級 ‧ 2019-09-23 11:16:25 檢舉

我以為 Yes 只是圖片描述,就改掉了XD

感謝!
/images/emoticon/emoticon41.gif

Yenting iT邦新手 5 級 ‧ 2019-09-23 23:18:55 檢舉

下次真的不現場示範刷題嗎 :D /images/emoticon/emoticon28.gif

0
ShawnGood
iT邦新手 5 級 ‧ 2022-03-08 00:25:47

我也來個跳舞版的 /images/emoticon/emoticon25.gif

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);
0
AndrewYEE
iT邦新手 3 級 ‧ 2023-07-04 13:50:03

不使用遞迴而使用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))

我要留言

立即登入留言