學習資料結構和演算法有助於撰寫性能更優的程式碼。
基礎決定你可能達到的高度，而業務決定了你的最低瓶頸
了解和學習 JavaScript 常用演算法可以幫助前端開發者撰寫性能更好的程式碼，本文介紹排序演算法中的兩種時間複雜度為 O (n^2) 的演算法，選擇排序和插入排序。
選擇排序#
選擇排序的原理是：對排序陣列進行遍歷，在遍歷的過程中，對當前索引之後的陣列進行遍歷，找到最小元素的索引，將當前索引和最小元素的索引對應元素進行交換。
function swap(arr, a, b) {
[arr[a], arr[b]] = [arr[b], arr[a]];
}
function selectionSort(arr) {
for (let i = 0, len = arr.length; i < len; i ++) {
let minIndex = i;
for(let j = i + 1; j < len; j++) {
if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr, i, minIndex);
}
}
選擇排序因為嵌套了兩層迴圈，所以其時間複雜度為 O (n^2)
插入排序#
插入排序的原理與打撲克牌時按牌的大小整理順序類似，從陣列的第一項開始遍歷，遍歷過程中對於當前索引的左邊陣列從右向左進行大小比較，如果左邊項大於右邊項，則進行交換。否則退出當前迴圈。程式碼實現如下：
function insertionSort(arr) {
// 從1開始
for (let i = 1, len = arr.length; i < len; i ++) {
// 尋找元素合適的插入位置
for (let j = i; j > 0; j --) {
if (arr[j] < arr[j - 1]) {
swap(arr, j, j - 1);
} else {
break; // 退出當前迴圈
}
}
}
}
在內層迴圈中，可以將比較兩項大小的操作放到 for 迴圈中，以此來簡化程式碼。
function insertionSort(arr) {
// 從1開始
for (let i = 1, len = arr.length; i < len; i ++) {
// 尋找元素合適的插入位置
for (let j = i; j > 0 && arr[j] < arr[j - 1]; j --) {
swap(arr, j, j - 1);
}
}
}
對比選擇排序和插入排序，兩者都是進行了兩層迴圈，時間複雜度為 O (n^2)，但是從程式碼中看，插入排序在內層迴圈中會提前終止迴圈，是否表示插入排序的速度要優於選擇排序呢？
測試排序時間#
現在我們對兩種排序演算法進行測試，驗證是否插入排序的速度優於選擇排序？
此處使用 console.time 和 console.timeEnd 來測試一段程式碼運行消耗的時間。console.time 方法是開始計算時間，console.timeEnd 是停止計時，輸出程式碼執行的時間。
使用方法如下：
// 計時開始
console.time('test');
// 測試時間的程式碼
// 計時結束，輸出時間
console.timeEnd('test');
// test:4522.303ms
這兩個方法接收一個參數，作為計時器的名稱。
編寫測試程式碼如下：
function testFuncTime(tag, fn, args) {
console.time(tag);
fn(args);
console.timeEnd(tag);
}
testFuncTime 接收三個參數，分別是計時器名稱，測試的方法，測試方法的參數。
為了使測試結果更加明顯，我們需要一個可以生成任意範圍隨機數的陣列的方法。
function getRandom(start, end, n) {
let arr = [];
for(let i=0; i<n; i++) {
let choice = end - start + 1;
let value = Math.floor(Math.random() * choice + start);
arr.push(value);
}
return arr;
}
編寫 getRandom 方法用於生成在 start 和 end 之前的 n 個數字的隨機數陣列。
下面是測試程式碼：
let array = getRandom(1, 10000, 1000);
let array2 = [...array];
testFuncTime('selectionSort', selectionSort, array);
testFuncTime('insertionSort', insertionSort, array2);
console.log(array);
console.log(array2);
在上述程式碼中，生成了一個範圍在 1-10000，長度為 1000 的隨機數陣列 array，並且複製一份賦值給 array2，然後運行 testFuncTime 進行測試，最終輸出排序結果。
結果如下：
可以看到插入排序的耗時大約是選擇排序的三倍，恰恰和預期相反，那究竟是為什麼呢？
原因就是：選擇排序內層遍歷一次取到最小值的索引，每次只需要一次交換（swap）操作。但是插入排序在內層遍歷的時候，會從右向左依次比較大小再交換，而
交換操作又是最耗時的。
下面我們對插入排序的實現進行優化。
優化插入排序#
function insertionSort(arr) {
// 從1開始
for (let i = 1, len = arr.length; i < len; i ++) {
// 尋找元素合適的插入位置
let e = arr[i];
let j; // j保存元素e應該插入的位置
for (j = i; j > 0 && arr[j - 1] > e; j --) {
arr[j] = arr[j - 1];
}
arr[j] = e;
}
}
在上述程式碼中，對插入排序進行優化，在外層迴圈中，首先，聲明一個變數 e 來保存當前元素，並且聲明變數 j 來保存元素 e 應該插入的位置，在內層迴圈中，如果左邊項大於當前項，則將左邊項賦值到當前項，變數 j 不斷向左移動，直到迴圈結束，將待排序元素 e 賦值給 arr [j]。
我們聲明了新的變數，使用賦值操作來代替交換操作，優化了性能。下面對優化後的程式碼進行測試。
從上述圖片可以看出，優化後的插入排序耗時為選擇排序的一半左右，性能有了相當大的提升。
總結#
本文使用 JavaScript 實現了時間複雜度為 O (n^2)
的兩種排序演算法，對於選擇排序來說，它的缺點是兩層迴圈都必須完整得執行完成所以它的效率在任何條件下都是非常慢的。相比之下，雖然插入排序在最差的情況下複雜度為 O (n^2)，但是在實際的應用中，O (n^2) 複雜度的排序演算法並非是一無是處的，它可以作為更加複雜排序演算法的子過程進行優化，並且，對於近乎有序的陣列來講（系統日誌按時間生成），性能比 O (nlogn) 級別的排序演算法還要快，在完全有序的陣列中，插入排序的複雜度可以達到 O (n)。