軟體工程師職涯升級計畫啟動！立即預約職涯諮詢、履歷健檢或模擬面試👈，為您的加薪做好準備！
為什麼需要了解演算法？
在編寫程式時，深入理解不同演算法的效能至關重要。這不僅能幫助我們寫出更有效率的程式碼，也能在面對複雜問題時，做出最佳的解法選擇。許多語言內建的 API 雖然方便，但其背後的實現方式（如時間和空間複雜度）會直接影響程式的整體表現。因此，了解演算法能讓你跳脫單純調用 API 的思維，真正從底層優化你的程式。
以 LeetCode 977. Squares of a Sorted Array 為例，此題要求將一個已排序的整數陣列中的每個元素平方後，再按非遞減順序排序。
範例 1： Input:[-4,-1,0,3,10] Output: [0,1,9,16,100]範例 2： Input: [-7,-3,2,3,11] Output: [4,9,9,49,121]
備註：
- 陣列長度介於 1 到 10000。
- 元素值介於 -10000 到 10000。
- 陣列已經按非遞減順序排序。
許多人可能會直覺地寫出以下解法：先對陣列中的每個元素進行平方，然後再進行排序。
JavaScript
var sortedSquares = function(A) {
// 遍歷陣列並平方每個元素
for (let i = 0; i < A.length; i++) {
A[i] = A[i] * A[i];
}
// 對平方後的陣列進行排序
A.sort((a, b) => a - b);
return A;
};
這個解法簡潔易懂，但效能如何？
for迴圈的時間複雜度為 O(n)。- JavaScript 的
Array.prototype.sort()方法，其時間複雜度在 V8 引擎中通常是 O(nlogn)（使用 Timsort 或 Mergesort 變體）。
因此，總時間複雜度為 O(n)+O(nlogn)=O(nlogn)。
優化解法：雙指針 (Two Pointers)
既然輸入陣列已經排序，我們可以利用這個特性來優化。由於負數平方後會變成正數，且絕對值較大的負數平方後值也較大，因此原始陣列的兩端（即絕對值最大值）在平方後會成為新陣列的最大值。這時，我們可以使用雙指針技巧：
- 一個指針
i從陣列開頭往後遍歷。 - 一個指針
j從陣列結尾往前遍歷。 - 比較
A[i]和A[j]的絕對值，將絕對值較大的平方後，放入一個新陣列的尾部。 - 當指針相遇時，循環結束。
這個方法的好處是，我們不需要額外進行排序，因為我們在遍歷的過程中就已經將平方後的數字以遞減的方式放入新陣列。最後再對新陣列進行反轉即可。
以下是優化後的 JavaScript 實作：
JavaScript
/**
* @param {number[]} A
* @return {number[]}
*/
var sortedSquares = function(A) {
let i = 0; // 指向陣列頭部
let j = A.length - 1; // 指向陣列尾部
const result = new Array(A.length); // 創建結果陣列，避免動態擴展
let pos = A.length - 1; // 從結果陣列的尾部開始填充
while (i <= j) {
if (Math.abs(A[i]) > Math.abs(A[j])) {
result[pos] = A[i] * A[i];
i++;
} else {
result[pos] = A[j] * A[j];
j--;
}
pos--;
}
return result;
};
這個版本的時間複雜度為 O(n)，因為我們只進行了一次遍歷。空間複雜度為 O(n)，因為我們使用了額外的 result 陣列。這種雙指針技巧在處理有序陣列問題時非常有效，值得在你的演算法工具箱中佔有一席之地。
核心演算法解析
接下來，我們深入探討幾種常見的搜尋與排序演算法。
Linear Search
概念： 這是最簡單的搜尋演算法，透過一個迴圈依序檢查陣列中的每個元素，直到找到目標值。
時間複雜度： 在最壞情況下，需要檢查陣列中所有 n 個元素，因此時間複雜度為 O(n)。
JavaScript 實作：
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i; // 找到目標，返回索引
}
}
return -1; // 找不到目標，返回 -1
}
Binary Search (二分搜尋)
概念： 僅適用於已排序的資料。每次都檢查搜尋範圍的中間元素。如果中間元素小於目標，則將搜尋範圍縮小到右半部；如果大於目標，則縮小到左半部。這種方法每次都將搜尋空間減半，效率極高。
時間複雜度： 由於每次都將搜尋範圍減半，其時間複雜度為 O(logn)。
JavaScript 實作：
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2); // 避免整數溢位
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
排序演算法 (Sorting Algorithms)
Selection Sort (選擇排序)
概念： 每次從未排序的子陣列中找出最小（或最大）的元素，並將其與未排序子陣列的第一個元素交換位置。
時間複雜度： 無論輸入資料的狀況如何，都必須進行 O(n2) 次比較和交換，因此時間複雜度為 O(n2)。
空間複雜度： O(1)，因為它是在原地 (in-place) 進行排序。
JavaScript 實作：
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 將找到的最小元素與當前位置的元素交換
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
Bubble Sort (氣泡排序)
概念： 重複地遍歷陣列，比較相鄰的兩個元素，如果它們的順序不正確，就進行交換。每次遍歷都會將未排序部分的最大元素「浮」到最末端。
時間複雜度： 最差與平均時間複雜度為 O(n2)。但若加入一個旗標 (flag) 判斷一輪遍歷中是否發生交換，若無則表示陣列已排序完成，此時最佳時間複雜度可達 O(n)。
空間複雜度： O(1)，原地排序。
JavaScript 實作：
function bubbleSort(arr) {
const n = arr.length;
let swapped;
for (let i = 0; i < n - 1; i++) {
swapped = false;
for (let j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交換元素
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}
// 如果這一輪沒有任何交換發生，表示陣列已排序完成
if (!swapped) {
break;
}
}
return arr;
}
Insertion Sort (插入排序)
概念： 類似於玩撲克牌時，將牌插入到手中已排序的牌組中。它將陣列分為已排序和未排序兩部分，每次從未排序部分取出一個元素，並將其插入到已排序部分的正確位置。
時間複雜度： 最差與平均時間複雜度為 O(n2)。但在處理近乎已排序的資料時，其效率非常高，最佳時間複雜度可達 O(n)。
空間複雜度： O(1)，原地排序。
JavaScript 實作：
function insertionSort(arr) {
const n = arr.length;
for (let i = 1; i < n; i++) {
const current = arr[i];
let j = i - 1;
// 將已排序部分中大於當前元素的元素往右移動
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
// 找到正確位置，插入當前元素
arr[j + 1] = current;
}
return arr;
}
Merge Sort (合併排序)
概念： 這是一種分治 (Divide and Conquer) 演算法。它將陣列遞迴地分割成兩個子陣列，直到每個子陣列只剩一個元素。然後，它會將這些子陣列兩兩合併，並在合併過程中進行排序，直到所有子陣列都合併回一個完整的排序陣列。
時間複雜度： 由於其分治特性，合併排序在任何情況下都保證穩定的 O(nlogn) 效能，且是穩定的排序演算法。
空間複雜度： O(n)，因為需要一個額外的暫存空間來進行合併操作。
JavaScript 實作：
function mergeSort(arr) {
// 遞迴結束條件
if (arr.length <= 1) {
return arr;
}
// 分割階段
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
// 遞迴地對左右子陣列進行排序
const sortedLeft = mergeSort(left);
const sortedRight = mergeSort(right);
// 合併階段
return merge(sortedLeft, sortedRight);
}
function merge(left, right) {
const result = [];
let i = 0;
let j = 0;
// 比較並合併兩個已排序的子陣列
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
// 將剩餘元素加入結果陣列
while (i < left.length) {
result.push(left[i]);
i++;
}
while (j < right.length) {
result.push(right[j]);
j++;
}
return result;
}
希望這篇文章的優化和補充能幫助你對這些經典演算法有更深入的理解！你對哪一種演算法的應用場景最感興趣呢？
