《Algorithms Unlocked》是 《算法導(dǎo)論》的合著者之一 Thomas H. Cormen 寫的一本算法基礎(chǔ)，算是啃CLRS前的開胃菜和輔助教材。如果CLRS的厚度讓人望而生畏，這本200多頁的小讀本剛好合適帶你入門。

書中沒有涉及編程語言，直接用文字描述算法，我用 JavaScript 對書中的算法進(jìn)行描述。

二分查找

在排好序的數(shù)組中查找目標(biāo)值x。在p到r區(qū)間中，總是取索引為q的中間值與x進(jìn)行比較，如果array[q]大于x，則比較p到q-1區(qū)間，否則比較q+1到r區(qū)間，直到array[q]等于x或p>r。

// 利用二分法在已經(jīng)排好序的數(shù)組中查找值xfunction binarySearch(array, x) {
  let p = 1;
  let r = array.length - 1;

  while (p <= r) {
    let q = Math.round((p + r) / 2);  //四舍五入取整

    if (array[q] === x) {
      return q;
    } else {
      if (array[q] > x) {
        // 如果q沒有減一，遇到找不到x的情況，
        // 就會(huì)陷入while循環(huán)中出不來，因?yàn)閜會(huì)一直等于r
        r = q - 1; 
      } else {
        p = q + 1;
      }
    }
  }

  return 'NOT-FOUND';}

也可以把二分查找寫成遞歸風(fēng)格。

// 二分法遞歸風(fēng)格function recursiveBinarySearch(array, p, r, x) {

  if (p > r) {  // 基礎(chǔ)情況
     console.log('NOT-FOUND');
     return;
  }

  let q = Math.round((p + r) / 2);

  if (array[q] === x) {  // 基礎(chǔ)情況
    console.log(q);
    return;
  } else {
    if (array[q] > x) {
      recursiveBinarySearch(array, p, q-1, x);
    } else {
      recursiveBinarySearch(array, q+1, r, x);
    }
  }}

排序

選擇排序

從第一個(gè)元素開始遍歷，把該元素跟在它之后的所有元素進(jìn)行比較，選出最小的元素放入該位置。

以書架上的書本排序?yàn)槔?。我們看一眼書架上的第一本書的書名，接著與第二本進(jìn)行比較，如果第二本書的書名第一個(gè)字母的順序小于第一本，那我們忘掉第一本書的書名，記下第二本書的書名，此時(shí)我們并沒有對書籍進(jìn)行移動(dòng)，只是比較了書名的順序，并把順序最小的書名記在腦子里。直到與最后一本進(jìn)行比較結(jié)束，我們把腦子里順序最小的書名對應(yīng)的書與第一本書對調(diào)了一下位置。

function selectionSort (array) {
  for (let i = 0; i < array.length - 1; i++) {
    let smallest = i;
    let key = array[i]; // 保存當(dāng)前值
    for (let j = i + 1; j < array.length; j++) {
      // 比較當(dāng)前值和最小值，如果當(dāng)前值小于最小值則把當(dāng)前值的索引賦給smallest
      if (array[j] < array[smallest]) {
        smallest = j;
      }
    }
    // 最小值和當(dāng)前值交換
    array[i] = array[smallest];
    array[smallest] = key;
  }

  return array;}

選擇排序效率很低，因?yàn)檫x擇排序進(jìn)行了較多的比較操作，但移動(dòng)元素的操作次數(shù)很少。所以當(dāng)遇到移動(dòng)元素相當(dāng)耗時(shí)——或者它們所占空間很大或者它們存儲(chǔ)在一個(gè)存儲(chǔ)較慢的設(shè)備中——那么選擇排序可能是一個(gè)合適的算法。

插入排序

以書架為例，假設(shè)前4個(gè)位置已經(jīng)排好序了，我們拿起第五本書與第四本進(jìn)行比較，如果第四本大于第五本，把第四本向右移動(dòng)一個(gè)位置，再把第三本與第五本進(jìn)行比較，如果第三本還大于第五本，把第三本向右移動(dòng)一個(gè)位置，剛好放入第四本空出來的位置。直到遇到一本小于第五本的書或者已經(jīng)沒有書可以比較了，把第五本書插入小于它的那本書的后面。

function insertionSort (array) {
  for (let i = 1; i < array.length; i++) {
    let key = array[i];  // 把當(dāng)前操作值保存到key中
    let j = i - 1;       // j 為當(dāng)前值的前一位

    // 在j大于等于0且前一位大于當(dāng)前值時(shí)，前一位向右移動(dòng)一個(gè)位置
    while (j >= 0 && array[j] > key) {
      array[j+1] = array[j];
      j -= 1;
    };
    // 直到遇到array[j]小于當(dāng)前操作值或者j小于0時(shí)，把當(dāng)前值插入所空出來的位置    
    array[j+1] = key;
  }

  return array;}

插入排序與選擇排序時(shí)間差不多，如果移動(dòng)操作太過耗時(shí)最好用選擇排序。插入排序適用于數(shù)組一開始就已經(jīng)“基本有序”的狀態(tài)。

歸并排序

歸并排序中使用一個(gè)被稱為分治法的通用模式。在分治法中，我們將原問題分解為類似原問題的子問題，并遞歸的求解這些子問題，然后再合并這些子問題的解來得出原問題的解。

  1. 分解：把一個(gè)問題分解為多個(gè)子問題，這些子問題是更小實(shí)例上的原問題。

  2. 解決：遞歸地求解子問題。當(dāng)子問題足夠小時(shí)，按照基礎(chǔ)情況來求解。

  3. 合并：把子問題的解合并成原問題的解。

在歸并排序中，我們把數(shù)組不斷用二分法分解成兩個(gè)小數(shù)組，直到每個(gè)數(shù)組只剩一個(gè)元素（基礎(chǔ)情況）。再把小數(shù)組排好序并進(jìn)行合并。

seo優(yōu)化培訓(xùn),網(wǎng)絡(luò)推廣培訓(xùn),網(wǎng)絡(luò)營銷培訓(xùn),SEM培訓(xùn),網(wǎng)絡(luò)優(yōu)化,在線營銷培訓(xùn)

// array: 數(shù)組// p: 開始索引// r: 末尾索引function mergeSort (array, p, r) {
  if (p >= r) {
    return;
  } else {
    // 不可以用四舍五入，找了一夜的bug竟然是因?yàn)樗纳嵛迦脒@個(gè)小蹄子
    let q = Math.floor((p + r) / 2);
    // 遞歸調(diào)用，把數(shù)組拆分成兩部分，直到每個(gè)數(shù)組只剩一個(gè)元素
    mergeSort(array, p, q);
    mergeSort(array, q + 1, r);

    // 把兩個(gè)子數(shù)組排序并合并
    merge(array, p, q, r);
  }

  return array;}

程序的真正工作發(fā)生在 merge 函數(shù)中。歸并排序不是原址的。

假設(shè)有兩堆已經(jīng)排好序的書，書堆A和書堆B。把A中的第一本與B中的第一本拿起來比較，小的那本放入書架中，再把A中的“第一本”和B中的“第一本”進(jìn)行比較，此時(shí)的“第一本”不一定是剛才的第一本了，因?yàn)橐呀?jīng)有一本書放入書架了，不過該書堆的“第一本”任然是該書堆中最小的一本。直到把兩堆書全部放入書架。

seo優(yōu)化培訓(xùn),網(wǎng)絡(luò)推廣培訓(xùn),網(wǎng)絡(luò)營銷培訓(xùn),SEM培訓(xùn),網(wǎng)絡(luò)優(yōu)化,在線營銷培訓(xùn)

function merge (array, p, q, r) {
  let n1 = q - p + 1;  // 子數(shù)組的長度
  let n2 = r - q;

  // 把兩個(gè)子數(shù)組拷貝到B、C數(shù)組中
  // slice不包含end參數(shù)，所以end參數(shù)要加一
  let arrB = array.slice(p, q + 1);
  let arrC = array.slice(q + 1, r + 1);

  // 兩個(gè)數(shù)組的最后一個(gè)元素設(shè)為無窮大值，確保了無需再檢查數(shù)組中是否有剩余元素
  arrB[n1] = Number.MAX_VALUE;
  arrC[n2] = Number.MAX_VALUE;

  // 因?yàn)榛靥钊朐瓟?shù)組的個(gè)數(shù)是固定的，所以無窮大值不會(huì)被填入，也無需判斷是否有剩余
  // 一旦B、C兩個(gè)數(shù)組中的所有元素拷貝完就自動(dòng)終止
  // 因?yàn)锽、C中的元素已經(jīng)按照非遞減順序排好了，所以最小索引值對應(yīng)的就是最小值
  // 兩個(gè)子數(shù)組的最小值比較，小的則為當(dāng)前最小值
  let i = j = 0;
  for (let k = p; k < r + 1; k++) {
    if (arrB[i] < arrC[j]) {
      array[k] = arrB[i];
      i++;
    } else {
      array[k] = arrC[j];
      j++;
    }
  }

  return;}

由于歸并排序不是在原址上工作，需要拷貝出子數(shù)組，如果你的儲(chǔ)存空間較小或空間非常寶貴，可能不適合使用歸并排序。

快速排序

與歸并排序類似，快速排序也是使用分治模式。與歸并排序不同的是，快速排序是在原址上工作的，歸并排序是拷貝出兩個(gè)子數(shù)組進(jìn)行操作并不在原址上工作。

在書架中隨機(jī)挑選一本書作為主元（這里我們總是選擇位于書架最末尾的那本書），所有小于主元的書放在主元左側(cè)，所有大于或等于主元的書放在主元右側(cè)，這時(shí)就把書分為左右兩組（不包括主元），再分別對這兩組書進(jìn)行相同的操作（遞歸），直到子數(shù)組只剩一本書觸發(fā)基礎(chǔ)情況。

seo優(yōu)化培訓(xùn),網(wǎng)絡(luò)推廣培訓(xùn),網(wǎng)絡(luò)營銷培訓(xùn),SEM培訓(xùn),網(wǎng)絡(luò)優(yōu)化,在線營銷培訓(xùn)

function quickSort (array, p, r) {

  if (p >= r) {
    return;
  } else {
    let q = partition(array, p, r);

    // 遞歸中不再包含array[q]，因?yàn)樗呀?jīng)處在正確的位置（左邊所有元素都小于它，右邊所有元素都大于或等于它）
    // 如果遞歸調(diào)用還包含array[q]，就會(huì)陷入死循環(huán)
    quickSort(array, p, q - 1);
    quickSort(array, q + 1, r);
  }

  return array;}

重要的操作都在 partition 函數(shù)中。這個(gè)函數(shù)把數(shù)組按照大于或小于主元分為左右兩堆，并返回主元所在位置的索引q。注意，左右兩堆數(shù)組并不是有序的（見上圖），只是大于或小于主元。

在書架中隨機(jī)挑選一本書作為主元（這里我們總是選擇位于書架最末尾的那本書），此時(shí)主元位于最末尾。還未進(jìn)行比較的為未知組，稱為組U，位于主元左側(cè)。小于主元的稱為組L，位于書架最左側(cè)。大于或小于主元的稱為組R，位于組L左側(cè)組U右側(cè)。如下圖。

我們拿起組U中最左側(cè)的那本書，與主元進(jìn)行比較，如果小于主元?jiǎng)t放入組L，大于或等于主元?jiǎng)t放入組R。放入組R的操作比較簡單，只需要把組R和組U的分割線往右移一位，無需移動(dòng)書籍。

放入組L的操作則比較復(fù)雜。我們將它與組R中最左側(cè)的書籍進(jìn)行調(diào)換，并將組L和組R之間的分割線向右移一位，將組R和組U的分割線向右移一位。如下圖

seo優(yōu)化培訓(xùn),網(wǎng)絡(luò)推廣培訓(xùn),網(wǎng)絡(luò)營銷培訓(xùn),SEM培訓(xùn),網(wǎng)絡(luò)優(yōu)化,在線營銷培訓(xùn)

// 主元：數(shù)組中隨機(jī)挑選單獨(dú)的一個(gè)數(shù)（這里我們總是選數(shù)組中的最后一位）array[r]// 組L（左側(cè)組）：所有小于主元的數(shù)，array[p...q-1]// 組R（右側(cè)組）：所有大于或等于主元的數(shù)，array[q...u-1]// 組U（未知組）：還未進(jìn)行比較的數(shù)，array[u...r-1]function partition(array, p, r) {
  let q = p;
  // 遍歷array[p...r-1]
  for (let u = p; u < r; u++) {

    // 如果未知數(shù)小于主元，放入組L
    if (array[u] < array[r]) {

      // 把未知數(shù)和組R最左側(cè)值(array[q])進(jìn)行交換，并讓q和u往右移一位(加1)
      let key = array[q];
      array[q] = array[u];
      array[u] = key;
      q += 1;
    }

    // 如果未知數(shù)大于或等于主元，放入組R
    // 無需其他操作，只需要把u往右移一位
  }

  // 把主元和組R最左側(cè)值(array[q])進(jìn)行交換，讓主元位于組L合組R中間
  let key = array[q];
  array[q] = array[r];
  array[r] = key;

  return q;}

本例的快速排序總是選擇最末尾的元素作為主元，稱為確定的快速排序。如果每次選擇主元時(shí)都從數(shù)組中隨機(jī)選擇，則稱為隨機(jī)快速排序，隨機(jī)快速排序在測試中會(huì)快于確定的快速排序。

根據(jù)數(shù)據(jù)量的不同，儲(chǔ)存空間的大小，存儲(chǔ)速度的快慢，每個(gè)排序方法都有不同的表現(xiàn)，并不是說哪個(gè)方法一定是最快的，也不一定最快就是最好的，合適才是最好的。

http://www.cnblogs.com/chaohangz/p/6719874.html