algorithm Archives - 快樂學程式

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

氣泡排序法 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++) {…