JS資料結構與演算法_排序和搜尋演算法
寫在前面
這是《學習JavaScript資料結構與演算法》的最後一篇部落格，也是在面試中常常會被問到的一部分內容： 排序 和 搜尋 。在這篇部落格之前，我每每看到排序頭就是大的，心裡想著類似“氣泡排序，兩層遍歷啪啪啪“就完事了，然後再也無心去深入研究排序相關的問題了。如果你也有類似的經歷，希望下面的內容對你有一定幫助
一、準備
在進入正題之前，先準備幾個基礎的函式
（1）交換陣列兩個元素
function swap(arr, sourceIndex, targetIndex) {
let temp = arr[sourceIndex];
arr[sourceIndex] = arr[targetIndex];
arr[targetIndex] = temp;
}
（2）快速生成 0~N 的陣列 可點選檢視更多生成方法
function createArr(length) {
return Array.from({length}, (_, i) => i);
}
（3）洗牌函式
洗牌函式可快速打亂陣列，常見的用法如切換音樂播放順序
function shuffle(arr) {
for (let i = 0; i < arr.length; i += 1) {
const rand = Math.floor(Math.random() * (i + 1));
if (rand !== i) {
swap(arr, i, rand);
}
}
return arr;
}
二、排序
常見排序演算法可以分為兩大類：
- 比較類排序 ：通過比較來決定元素間的相對次序，由於其時間複雜度不能突破
O(nlogn)，因此也稱為非線性時間比較類排序 - 非比較類排序 ：不通過比較來決定元素間的相對次序，它可以突破基於比較排序的時間下界，以線性時間執行，因此也稱為線性時間非比較類排序
在本篇部落格中，僅對比較類排序的幾種排序方式進行學習介紹
2.1 氣泡排序
氣泡排序是所有排序演算法中最簡單的，通常也是我們學習排序的入門方法。但是，從執行時間的角度來看，氣泡排序是最差的一種排序方式。
核心：比較任何兩個相鄰的項，如果第一個比第二個大，則交換它們。元素項向上移動至正確的順序，就好像氣泡升至表面一樣，氣泡排序因而得名
動圖：
注意：第一層遍歷找出剩餘元素的最大值，至指定位置【依次冒泡出最大值】
程式碼：
function bubbleSort(arr) {
const len = arr.length;
for (let i = 0; i < len; i += 1) {
for (let j = 0; j < len - 1 - i; j += 1) {
if (arr[j] > arr[j + 1]) { // 比較相鄰元素
swap(arr, j, j + 1);
}
}
}
return arr;
}
2.2 選擇排序
選擇排序是一種原址比較排序演算法。
核心：首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢
動圖：
注意：第一層遍歷找出剩餘元素最小值的索引，然後交換當前位置和最小值索引值【依次找到最小值】
程式碼：
function selectionSort(arr) {
const len = arr.length;
let minIndex;
for (let i = 0; i < len - 1; i += 1) {
minIndex = i;
for (let j = i + 1; j < len; j += 1) {
if (arr[i] > arr[j]) {
minIndex = j; // 尋找最小值對應的索引
}
}
if (minIndex === i) continue;
swap(arr, minIndex, i);
}
return arr;
}
2.3 插入排序
插入排序的比較順序不同於氣泡排序和選擇排序，插入排序的比較順序是當前項向前比較。
核心：通過構建有序序列，對於未排序資料，在已排序序列中從後向前掃描，找到相應位置並插入
動圖：
注意：從第二項開始，依次向前比較，保證當前項以前的序列是順序排列
程式碼：
function insertionSort(arr) {
const len = arr.length;
let current, pointer;
for (let i = 1; i < len; i += 1) {
current = arr[i];
pointer = i;
while(pointer >= 0 && current < arr[pointer - 1]) { // 每次向前比較
arr[pointer] = arr[pointer - 1]; // 前一項大於指標項，則向前移動一項
pointer -= 1;
}
arr[pointer] = current; // 指標項還原成當前項
}
return arr;
}
2.4 歸併排序
歸併排序和快速排序相較於上面三種排序演算法在實際中更具有可行性（在第四小節我們會通過實踐複雜度來比較這幾種排序演算法）
JavaScript 的 Array 類定義了一個 sort 函式( Array.prototype.sort )用以排序 JavaScript 陣列。 ECMAScript 沒有定義用哪個排序演算法，所以瀏覽器廠商可以自行去實現演算法。例如， Mozilla Firefox 使用 歸併排序 作為 Array.prototype.sort 的實現，而 Chrome 使用了一個 快速排序 的變體
歸併排序是一種 分治演算法 。其思想是將原始陣列切分成較小的陣列，直到每個小陣列只有一 個位置，接著將小陣列歸併成較大的陣列，直到最後只有一個排序完畢的大陣列。因此需要用到 遞迴
核心：歸併排序，拆分成左右兩塊陣列，分別排序後合併
動圖：
注意：遞迴中最小的左右陣列比較為單個元素的陣列，因此在較上層多個元素對比時，左右兩個陣列一定是順序的
程式碼：
function mergeSort(arr) {
const len = arr.length;
if (len < 2) return arr; // 遞迴的終止條件
const middle = Math.floor(len / 2); // 拆分左右陣列
const left = arr.slice(0, middle);
const right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) { // 將左右兩側比較後進行合併
const ret = [];
while (left.length && right.length) {
if (left[0] > right[0]) {
ret.push(right.shift());
} else {
ret.push(left.shift());
}
}
while (left.length) {
ret.push(left.shift());
}
while (right.length) {
ret.push(right.shift());
}
return ret;
}
2.5 快速排序
快速排序也許是最常用的排序演算法了。它的複雜度為 O(nlogn) ，且它的效能通常比其他的復 雜度為 O(nlogn) 的排序演算法要好。和歸併排序一樣， 快速排序也使用分治的方法，將原始陣列分為較小的陣列
核心：分治演算法，以參考值為界限，將比它小的和大的值拆開
動圖：
注意：每一次遍歷篩選出比基準點小的值
程式碼：
function quickSort(arr, left = 0, right = arr.length - 1) {
// left和right預設為陣列首尾
if (left < right) {
let partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
return arr;
}
function partition(arr, left, right) {
let pivot = left;
let index = left + 1; // 滿足比較條件的依次放在分割點後
for (let i = index; i <= right; i += 1) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index += 1;
}
}
swap(arr, index - 1, pivot); // 交換順序時，以最後一位替換分隔項
return index - 1;
}
三、搜尋演算法
3.1 順序搜尋
順序或線性搜尋是最基本的搜尋演算法。它的機制是，將每一個數據結構中的元素和我們要找的元素做比較。 順序搜尋是最低效的一種搜尋演算法。
function findItem(item, arr) {
for (let i = 0; i < arr.length; i += 1) {
if (item === arr[i]) {
return i;
}
}
return -1;
}
3.2 二分搜尋
二分搜尋要求被搜尋的資料結構已排序。以下是該演算法遵循的步驟：
- 選擇陣列的中間值
- 如果選中值是待搜尋值，那麼演算法執行完畢
- 如果待搜尋值比選中值要小，則返回步驟1在選中值左邊的子陣列中尋找
- 如果待搜尋值比選中值要大，則返回步驟1在選中值右邊的子陣列中尋找
function binarySearch(item, arr) {
arr = quickSort(arr); // 排序
let low = 0;
let high = arr.length - 1;
let mid;
while (low <= high) {
min = Math.floor((low + high) / 2);
if (arr[mid] < item) {
low = mid + 1;
} else if (arr[mid] > item) {
high = mid - 1;
} else {
return mid;
}
}
return -1;
}
四、演算法複雜度
4.1 理解大O表示法
大O表示法用於描述演算法的效能和複雜程度。分析演算法時，時常遇到一下幾類函式
（1） O(1)
function increment(num){
return ++num;
}
執行時間和引數無關。因此說，上述函式的複雜度是 O(1) (常數)
（2） O(n)
以 順序搜尋函式 為例，查詢元素需要遍歷整個陣列，直到找到該元素停止。 函式執行的總開銷取決於陣列元素的個數(陣列大小)，而且也和搜尋的值有關 。但是函式複雜度取決於最壞的情況：如果陣列大小是10，開銷就是10；如果陣列大小是1000，開銷就是1000。這種函式的時間複雜度是 O(n) ，n是(輸入)陣列的大小
（3） O(n2)
以 氣泡排序 為例，在未優化的情況下，每次排序均需進行 n*n 次執行。時間複雜度為 O(n2)
時間複雜度 O(n) 的程式碼只有一層迴圈，而 O(n2) 的程式碼有雙層巢狀迴圈。如 果演算法有三層遍歷陣列的巢狀迴圈，它的時間複雜度很可能就是 O(n3)
4.2 時間複雜度比較
（1）常用資料結構時間複雜度
（2）排序演算法時間複雜度
