演算法筆記：Linear Search, Binary Search, Selection Sort, Bubble Sort, Insertion Sort, Merge Sort

Gary Huang

Published in

Dublin so code

7 min readSep 11, 2020

為什麼需要了解演算法？

必須注意語言內建的 api 如何實現我們運算，才能選擇最有效率的寫法。

以 Leetcode 977. Squares of a Sorted Array 為例：

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Example 2:

Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Note:

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A is sorted in non-decreasing order.

使用 Javascript 的解法如下，這時候陣列是從大到小，因此需要反轉。這時候必須查看必須要查看 .reverse() 的說明：方法會原地（in place）反轉（reverses）一個陣列。陣列中的第一個元素變為最後一個，而最後一個元素則變成第一個。可以知道時間複雜度會增加 O (n/2) 可以省略常數為 O (n)。

var sortedSquares = function(A) {
    let i = 0;
    let n = A.length -1;
    let answer = []
    while (i !== n) {
        if (Math.abs(A[i]) > A[n]) {
            answer.push(A[i]*A[i])
            i += 1;
        } else {
            answer.push(A[n]*A[n])
            n -= 1;
        }
    }
    answer.push(A[n]*A[n])
    answer.reverse()
    return answer
};

這時候還有另一種寫法，answer.push(A[n]*A[n]) 改成 answer.unshift(A[n]*A[n]) ，但unshift 每添加一個元素，都要把現有元素往下移一個位置，因此時間複雜度為 O (n(n+1)/2)，可以省略常數為 O (n²)，因此可以得知選擇 push 再 reverse 的做法會比較好。push 與 unshift 的效率比較可以參考此文章。

接下來介紹這次課程的演算法：

Linear Search

Linear Search 概念十分簡單，跑一個 for loop 走訪每一項元素，找到目標值，因此效率是 O(n)。

要怎麼加速搜尋呢？這時候就需要排序過的數列來執行 Binary Search

Selection Sort

概念是反覆從未排序的數列中取出最小的元素，加入到另一個的數列，結果即為已排序的數列。運算流程如下：

從未排序的數列中找到最小的元素。
將此元素取出並加入到已排序數列最後。
重複以上動作直到未排序數列全部處理完成。

然而實作上通常不使用額外的數列來儲存已排序的部分，而使用原地(In-place)的方式來完成，數列的左半部表示已排序部分，右半部表示未排序部分，不另外使用數列。從未排序部分找到最小的元素，利用交換的方式將元素放置已排序部分的尾端。運算流程如下：

從未排序的數列中找到最小的元素。
將此元素與已排序部分的尾端元素進行交換。
重複以上動作直到未排序數列全部處理完成。

時間複雜度：O(n²)，空間複雜度：O(1)

Bubble Sort

演算法過程會將最大的數值移動到陣列最後面，而較小的數值則逐漸的往陣列前端移動。

比較相鄰的兩個元素，若前面的元素較大就進行交換。
重複進行1的動作直到最後面，最後一個元素將會是最大值。
重複進行 1 , 2 的動作，每次比較到上一輪的最後一個元素。
重複進行以上動作直到沒有元素需要比較。

實作上直接使用迭代法迴圈就可以很容易的完成。另外可以使用額外的旗標(Flag)來判斷這一輪是否有發生交換情形，若都沒有發生交換表示數列已經是排序好的，即可跳出迴圈，因此最佳時間複雜度是有可能達到O(n)。

時間複雜度：O(n²)，空間複雜度：O(1)

Insertion Sort

概念是利用另一個數列來存放已排序部分，逐一取出未排序數列中元素，從已排序數列由後往前找到適當的位置插入。運算流程如下：

從未排序數列取出一元素。
由後往前和已排序數列元素比較，直到遇到不大於自己的元素並插入此元素之後；若都沒有則插入在最前面。
重複以上動作直到未排序數列全部處理完成。

然而實作上通常不使用額外的數列來儲存已排序的部分，而使用原地(In-place)的方式來完成，數列的左半部表示已排序部分，右半部表示未排序部分，不另外使用數列。在與已排序的部分比較時，利用指派(Assign)的方式將元素往右位移，來達到插入的效果，因為位移的關係需要有另一個變數來暫存最右邊的數值。運算流程如下：