fbpx
AlgorithmJavascript工程思維

JS 學資料結構與演算法 (排序篇) — 選擇排序法 & 插入排序法

前言這篇文章將為排序篇章做一個結尾,文章會介紹選擇排序 (Selection Sort) 與插入排序 (Insertion Sort) 兩種排序法,透過上圖的排序法複雜度一覽表可以發現他們的執行效能相比其他排序法來的差一點,因此比較不常被使用,但要強調的是他們仍然有適合使用的情境,本篇文章將會簡單紀錄這兩個演算法的定義與程式碼實作。選擇排序法 (Selection Sort) 選擇排序法示意圖簡單來說選擇排序法一直重複的做兩件事:從尚未經過排序的陣列中找到最小值將當前找到最小值擺到最左邊時間複雜度 O(n²)程式碼範例這邊先設陣列的第一個數字是目前的最小值,然後往後把陣列的數值一個一個讀取,如果讀取的下個數比最小值大,就不作處理。而如果讀取到的數比目前的最小值小,就把目前的最小值換成這個數。重複這個方法把所有陣列裡的數都讀過一遍,就能確保目前的最小值為整個數列的最小值,扣除掉已經確定的最小值,剩下未確定的元素再重複執行以上步驟,直到陣列完成排序。function selectionSort(array) { const length = array.length; for(let i = 0; i < length; i++){ //…
學程式助教
March 16, 2020
AlgorithmJavascript工程思維

JS 學資料結構與演算法 (排序篇) — 氣泡排序法 Bubble Sort

氣泡排序法 Bubble Sort其實氣泡排序法算是最容易理解的排序法,也常作為初學者入門學習的演算法,相信經過前兩篇較為複雜的快速排序法、合併排序法後,可以快速理解氣泡排序法的內容與實作方法。氣泡排序法定義氣泡排序法的過程會從陣列最左邊開始將元素兩兩比較,每一輪都會把最大的數值移動到陣列末端,這個行為就好像氣泡不斷從底部冒出一樣,因此被稱作氣泡排序法。氣泡排序法的實作步驟如下:比較相鄰的兩個元素,若前面的元素較大就進行交換。重複進行1的動作直到最後面,最後一個元素將會是最大值。重複進行1,2的動作,每次比較到上一輪的最後一個元素。重複進行以上動作直到沒有元素需要比較。 把文章一開始示意圖的第一部份拆過來看,一開始把陣列的第一個元素跟第二個元素比較,如果前面的元素比後者大,就將兩元素交換,如果前者元素比後者小,就不做調整。這邊因為 5 比 1 大,因此將兩元素交換,接著看第二個元素跟第三個元素,依此類推,最後會將陣列中最大的元素放到陣列最後頭,接著重複以上步驟,直到所有元素都經過排列,排序才結束。時間複雜度因為實作會使用到雙重迴圈,因此平均時間複雜度為 O(n²)平均: O(n^2)空間複雜度因為沒有額外建立其他資料結構,因此空間複雜度為:O(1)程式碼範例function bubbleSort(array) { const length = array.length; for (let i = 0; i < length; i++) {…
學程式助教
March 16, 2020
AlgorithmJavascript

JavaScript 的 Leetcode 演算之路(一)

演算法對一個工程師來說是一個非常重要的技能,先撇開在工作上面的實務影響不管,光在求職的過程中,就有許多面試需要考試,而考的內容八九不離十是演算法考題,所以對於一個厲害的工程師來說,演算法尤其的重要,偏偏我的數學跟資料結構沒有這麼厲害,所以我也需要花點苦工來好好的學習,接下來我就會透過leetcode這個演算法考題的網站,學習演算法,把我寫好的題目來分享給大家,可以一起討論。 (more…)
學程式助教
December 2, 2019
Uncategorized

什麼是 B+ Tree

上一篇學習 什麼是 B-Tree 這篇就來補 B+ Tree 囉 B+ Tree 特徵 每個葉子節點都帶有指向下一個節點的指針,形成有序鏈表,加速範圍查詢 只有葉子節點帶衛星數據,父節點只帶關鍵字與指針,單一節點更省空間,讓查詢 I/O 變小 所有查詢都會查到葉子節點,查詢性能穩定 B+ Tree 更加矮胖 B+ Tree 中的內部節點,只存放關鍵字與子節點的指針,不存其他的 Satellite Information,因此最大化了內部節點的分支因子,所以說以同樣大小的硬碟分頁可以容納更多的節點元素。 換句話說,以數據量相同的情況下, B+ Tree 會比…
學程式助教
November 21, 2019
Uncategorized

什麼是 B-tree (Balance tree)

一般像是 MySQL PostgreSQL 都是用 Btree 的方式建立索引。 注意:B-tree 不念 B減樹,而是直接念 Btree,所以如果看到 Btree vs B-tree 其實是在講同一個算法。 為什麼用 Btree 用二元樹進行查詢,最快的時間複雜度是 O(logN),以算法邏輯上面來說,二元樹搜尋的查找速度跟比較次數都是最小的,但是要注意的事,我們還需要考量一個現實的問題就是「硬碟 I/O」。 二元樹結構: 數據庫的索引都是儲存在硬碟上,當數據量龐大時,索引的大小可能會有幾 G 甚至更多。 我們不可能在透過索引查詢時,一次把幾 G…
學程式助教
November 21, 2019