在 Javascript 中遇到排序問題,通常可直接使用原生 function — sort()
因此很少自己實作排序的功能,此次透過刷題,嘗試用各種排序演算法,期待能更深入地對個演算法有記憶,並瞭解使用情境;相關的時間、空間複雜度,將會另撰寫文章
搭配相關的視覺化工具:VisualGo, VISUALIZE CODE EXECUTION
我個人是圖像化學習較能吸收,尤其在針對演算法這種較抽象的概念,能夠直觀地看逐步的過程,可以有更深入的理解。
摘要
將會用到的排序:
插入排序 Insert Sort
快速排列 Quick Sort (use space and in place )
堆排序 Bucket Sort
尋找第 K 個元素問題
- LeetCode 215: Find Kth Elements
思路:排序後即可求得
實作:
1. 使用 native sort 去排序 (LeetCode 實測結果: 80 ms, 39.2 MB)
2. 實作 quick sort use space 去排序 (LeetCode 實測結果: 1432 ms, 182.5 MB)
3. 實作 insert sort (LeetCode 實測結果: 612 ms, 41.2 MB)
其中在理解插入排序時,對於要用兩個迴圈這件事,我卡了好一陣子,直到查到這部影片,很生動地呈現,才頓悟,推薦給大家。
原來雙迴圈是使用了「雙指標」的概念:一個指標往前遍尋,一個指標往後遍尋。
- LeetCode 75: Sort Colors
實作:
1. 使用 quick sort use space 實作 sort (僅實作,題目要求要 in place)
2. 使用 quick sort in place (原地實作,不另外佔空間)實作 sort (LeetCode 實測結果:68 ms, 39.8 MB)
3. 使用 native sort (LeetCode 實測結果:68 ms, 39.8 MB)
同樣的我們可以先來看一支舞 XD
- LeetCode 347: Top K Frequent Elements
思路:先排序再做堆
學到: 善用 JS Map 型別,可以讓 code 更漂亮,以及 Object 與 Map 的差異,論 iterator 特性
延伸閱讀:
2. 各個瀏覽器對於 sort 的實作方式不同探討
Chrome engine v8 對於 Javascript 的 sort 實作:
基礎是用 Quick Sort 實作, 若陣列長度小於 10 則改用 Insert Sort 實作The sorting algorithm itself is rather straightforward: The basis is a Quicksort with an Insertion Sort fall-back for shorter arrays (length < 10). The Insertion Sort fall-back was also used when Quicksort recursion reached a sub-array length of 10. Insertion Sort is more efficient for smaller arrays.
Reference from ChromeDoc
Reference: 淺談 JS sort() 到背後排序方法
Reference: 從 Array 的 sort 方法,聊到各瀏覽器的實作,沒想到 Chrome 和FireFox 的排序如此不同
謝謝你的閱讀,
以上是我的讀書筆記整理,歡迎各方大大討論交流校正~
喜歡的話, Medium 同步更新,歡迎前往拍手:)
我們下次見~