摘要：上一篇數據結構與算法樹寫在前面這是學習數據結構與算法的最后一篇博客，也是在面試中常常會被問到的一部分內容排序和搜索。

上一篇：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)，因此也稱為非線性時間比較類排序

非比較類排序：不通過比較來決定元素間的相對次序，它可以突破基于比較排序的時間下界，以線性時間運行，因此也稱為線性時間非比較類排序

在本篇博客中，僅對比較類排序的幾種排序方式進行學習介紹

冒泡排序是所有排序算法中最簡單的，通常也是我們學習排序的入門方法。但是，從運行時間的角度來看，冒泡排序是最差的一種排序方式。

核心：比較任何兩個相鄰的項，如果第一個比第二個大，則交換它們。元素項向上移動至正確的順序，就好像氣泡升至表面一樣，冒泡排序因而得名

動圖：

注意：第一層遍歷找出剩余元素的最大值，至指定位置【依次冒泡出最大值】

代碼：

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;
}

選擇排序是一種原址比較排序算法。

核心：首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢

動圖：

注意：第一層遍歷找出剩余元素最小值的索引，然后交換當前位置和最小值索引值【依次找到最小值】

代碼：

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[minIndex] > arr[j]) {
        minIndex = j; // 尋找最小值對應的索引
      }
    }
    if (minIndex === i) continue;
    swap(arr, minIndex, i);
  }
  return arr;
}

插入排序的比較順序不同于冒泡排序和選擇排序，插入排序的比較順序是當前項向前比較。

核心：通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入

動圖：

注意：從第二項開始，依次向前比較，保證當前項以前的序列是順序排列

代碼：

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;
}

歸并排序和快速排序相較于上面三種排序算法在實際中更具有可行性（在第四小節我們會通過實踐復雜度來比較這幾種排序算法）

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;
}

快速排序也許是最常用的排序算法了。它的復雜度為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;
}

順序或線性搜索是最基本的搜索算法。它的機制是，將每一個數據結構中的元素和我們要找的元素做比較。順序搜索是最低效的一種搜索算法。

function findItem(item, arr) {
  for (let i = 0; i < arr.length; i += 1) {
    if (item === arr[i]) {
      return i;
    }
  }
  return -1;
}

二分搜索要求被搜索的數據結構已排序。以下是該算法遵循的步驟：

選擇數組的中間值

如果選中值是待搜索值，那么算法執行完畢

如果待搜索值比選中值要小，則返回步驟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;
}

大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)

（1）常用數據結構時間復雜度

（2）排序算法時間復雜度

上一篇：JS數據結構與算法_樹
參考：十大經典排序算法（動圖演示）