寫(xiě)在前面

這是《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》的最后一篇博客，也是在面試中常常會(huì)被問(wèn)到的一部分內(nèi)容：排序和搜索。在這篇博客之前，我每每看到排序頭就是大的，心里想著類(lèi)似“冒泡排序，兩層遍歷啪啪啪“就完事了，然后再也無(wú)心去深入研究排序相關(guān)的問(wèn)題了。如果你也有類(lèi)似的經(jīng)歷，希望下面的內(nèi)容對(duì)你有一定幫助

一、準(zhǔn)備

在進(jìn)入正題之前，先準(zhǔn)備幾個(gè)基礎(chǔ)的函數(shù)

（1）交換數(shù)組兩個(gè)元素

function swap(arr, sourceIndex, targetIndex) {
  let temp = arr[sourceIndex];
  arr[sourceIndex] = arr[targetIndex];
  arr[targetIndex] = temp;
}

（2）快速生成0~N的數(shù)組

function createArr(length) {
  return Array.from({length}, (_, i) => i);
}

（3）洗牌函數(shù)
洗牌函數(shù)可快速打亂數(shù)組，常見(jiàn)的用法如切換音樂(lè)播放順序

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

二、排序

常見(jiàn)排序算法可以分為兩大類(lèi)：

• 比較類(lèi)排序：通過(guò)比較來(lái)決定元素間的相對(duì)次序，由于其時(shí)間復(fù)雜度不能突破O(nlogn)，因此也稱(chēng)為非線性時(shí)間比較類(lèi)排序
• 非比較類(lèi)排序：不通過(guò)比較來(lái)決定元素間的相對(duì)次序，它可以突破基于比較排序的時(shí)間下界，以線性時(shí)間運(yùn)行，因此也稱(chēng)為線性時(shí)間非比較類(lèi)排序

在本篇博客中，僅對(duì)比較類(lèi)排序的幾種排序方式進(jìn)行學(xué)習(xí)介紹

2.1 冒泡排序

冒泡排序是所有排序算法中最簡(jiǎn)單的，通常也是我們學(xué)習(xí)排序的入門(mén)方法。但是，從運(yùn)行時(shí)間的角度來(lái)看，冒泡排序是最差的一種排序方式。

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

動(dòng)圖：

image

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

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 選擇排序

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

核心：首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小元素，然后放到已排序序列的末尾。以此類(lèi)推，直到所有元素均排序完畢

image

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

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; // 尋找最小值對(duì)應(yīng)的索引
      }
    }
    if (minIndex === i) continue;
    swap(arr, minIndex, i);
  }
  return arr;
}

2.3 插入排序

插入排序的比較順序不同于冒泡排序和選擇排序，插入排序的比較順序是當(dāng)前項(xiàng)向前比較。

核心：通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入

image

注意：從第二項(xiàng)開(kāi)始，依次向前比較，保證當(dāng)前項(xiàng)以前的序列是順序排列

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]; // 前一項(xiàng)大于指針項(xiàng)，則向前移動(dòng)一項(xiàng)
      pointer -= 1;
    }
    arr[pointer] = current; // 指針項(xiàng)還原成當(dāng)前項(xiàng)
  }
  return arr;
}

2.4 歸并排序

歸并排序和快速排序相較于上面三種排序算法在實(shí)際中更具有可行性（在第四小節(jié)我們會(huì)通過(guò)實(shí)踐復(fù)雜度來(lái)比較這幾種排序算法）

JavaScript 的 Array 類(lèi)定義了一個(gè) sort 函數(shù)(Array.prototype.sort)用以排序 JavaScript 數(shù)組。ECMAScript 沒(méi)有定義用哪個(gè)排序算法，所以瀏覽器廠商可以自行去實(shí)現(xiàn)算法。例如，Mozilla Firefox使用歸并排序作為 Array.prototype.sort 的實(shí)現(xiàn)，而 Chrome 使用了一個(gè)快速排序的變體

歸并排序是一種分治算法。其思想是將原始數(shù)組切分成較小的數(shù)組，直到每個(gè)小數(shù)組只有一 個(gè)位置，接著將小數(shù)組歸并成較大的數(shù)組，直到最后只有一個(gè)排序完畢的大數(shù)組。因此需要用到遞歸

核心：歸并排序，拆分成左右兩塊數(shù)組，分別排序后合并

image

注意：遞歸中最小的左右數(shù)組比較為單個(gè)元素的數(shù)組，因此在較上層多個(gè)元素對(duì)比時(shí)，左右兩個(gè)數(shù)組一定是順序的

function mergeSort(arr) {
  const len = arr.length;

  if (len < 2) return arr; // 遞歸的終止條件
  const middle = Math.floor(len / 2); // 拆分左右數(shù)組
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);
  
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) { // 將左右兩側(cè)比較后進(jìn)行合并
  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 快速排序

快速排序也許是最常用的排序算法了。它的復(fù)雜度為 O(nlogn)，且它的性能通常比其他的復(fù) 雜度為 O(nlogn) 的排序算法要好。和歸并排序一樣，快速排序也使用分治的方法，將原始數(shù)組分為較小的數(shù)組。

核心：分治算法，以參考值為界限，將比它小的和大的值拆開(kāi)

image

注意：每一次遍歷篩選出比基準(zhǔn)點(diǎn)小的值

function quickSort(arr, left = 0, right = arr.length - 1) {
  // left和right默認(rèn)為數(shù)組首尾
  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; // 滿足比較條件的依次放在分割點(diǎn)后

  for (let i = index; i <= right; i += 1) {
    if (arr[i] < arr[pivot]) {
      swap(arr, i, index);
      index += 1;
    }
  }
  swap(arr, index - 1, pivot); // 交換順序時(shí)，以最后一位替換分隔項(xiàng)
  return index - 1;
}

三、搜索算法

3.1 順序搜索

順序或線性搜索是最基本的搜索算法。它的機(jī)制是，將每一個(gè)數(shù)據(jù)結(jié)構(gòu)中的元素和我們要找的元素做比較。順序搜索是最低效的一種搜索算法。

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

3.2 二分搜索

二分搜索要求被搜索的數(shù)據(jù)結(jié)構(gòu)已排序。以下是該算法遵循的步驟：

1. 選擇數(shù)組的中間值
2. 如果選中值是待搜索值，那么算法執(zhí)行完畢
3. 如果待搜索值比選中值要小，則返回步驟1在選中值左邊的子數(shù)組中尋找
4. 如果待搜索值比選中值要大，則返回步驟1在選中值右邊的子數(shù)組中尋找

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

四、算法復(fù)雜度

4.1 理解大O表示法

大O表示法用于描述算法的性能和復(fù)雜程度。分析算法時(shí)，時(shí)常遇到一下幾類(lèi)函數(shù)

（1）O(1)

function increment(num){
    return ++num;
}

執(zhí)行時(shí)間和參數(shù)無(wú)關(guān)。因此說(shuō)，上述函數(shù)的復(fù)雜度是O(1)(常數(shù))

（2）O(n)

以順序搜索函數(shù)為例，查找元素需要遍歷整個(gè)數(shù)組，直到找到該元素停止。函數(shù)執(zhí)行的總開(kāi)銷(xiāo)取決于數(shù)組元素的個(gè)數(shù)(數(shù)組大小)，而且也和搜索的值有關(guān)。但是函數(shù)復(fù)雜度取決于最壞的情況：如果數(shù)組大小是10，開(kāi)銷(xiāo)就是10；如果數(shù)組大小是1000，開(kāi)銷(xiāo)就是1000。這種函數(shù)的時(shí)間復(fù)雜度是O(n)，n是(輸入)數(shù)組的大小

（3）O(n2)

以冒泡排序?yàn)槔谖磧?yōu)化的情況下，每次排序均需進(jìn)行 n*n 次執(zhí)行。時(shí)間復(fù)雜度為O(n2)

時(shí)間復(fù)雜度 O(n) 的代碼只有一層循環(huán)，而 O(n2) 的代碼有雙層嵌套循環(huán)。如 果算法有三層遍歷數(shù)組的嵌套循環(huán)，它的時(shí)間復(fù)雜度很可能就是 O(n3)

4.2 時(shí)間復(fù)雜度比較

（1）常用數(shù)據(jù)結(jié)構(gòu)時(shí)間復(fù)雜度

（2）排序算法時(shí)間復(fù)雜度