javascript常用經(jīng)典算法實(shí)例詳解

更新時(shí)間：2015年11月25日 14:51:10 作者：菩提樹下的楊過

這篇文章主要介紹了javascript常用算法,結(jié)合實(shí)例形式較為詳細(xì)的分析總結(jié)了JavaScript中常見的各種排序算法以及堆、棧、鏈表等數(shù)據(jù)結(jié)構(gòu)的相關(guān)實(shí)現(xiàn)與使用技巧,需要的朋友可以參考下

本文實(shí)例講述了javascript常用算法。分享給大家供大家參考，具體如下：

入門級(jí)算法-線性查找-時(shí)間復(fù)雜度O(n)--相當(dāng)于算法界中的HelloWorld

//線性搜索(入門HelloWorld)
//A為數(shù)組，x為要搜索的值
function linearSearch(A, x) {
  for (var i = 0; i < A.length; i++) {
    if (A[i] == x) {
      return i;
    }
  }
  return -1;
}

二分查找(又稱折半查找) - 適用于已排好序的線性結(jié)構(gòu) - 時(shí)間復(fù)雜度O(logN)

//二分搜索
//A為已按"升序排列"的數(shù)組，x為要查詢的元素
//返回目標(biāo)元素的下標(biāo)
function binarySearch(A, x) {
  var low = 0, high = A.length - 1;
  while (low <= high) {
    var mid = Math.floor((low + high) / 2); //下取整   
    if (x == A[mid]) {
      return mid;
    }
    if (x < A[mid]) {
      high = mid - 1;
    }
    else {
      low = mid + 1;
    }
  }
  return -1;
}

冒泡排序 -- 時(shí)間復(fù)雜度O(n^2)

//冒泡排序
function bubbleSort(A) {
  for (var i = 0; i < A.length; i++) {
    var sorted = true;
  //注意：內(nèi)循環(huán)是倒著來的
    for (var j = A.length - 1; j > i; j--) {
      if (A[j] < A[j - 1]) {
        swap(A, j, j - 1);
        sorted = false;
      }
    }
    if (sorted) {
      return;
    }
  }
}

選擇排序 -- 時(shí)間復(fù)雜度O(n^2)

//選擇排序
//思路：找到最小值的下標(biāo)記下來，再交換
function selectionSort(A) {
  for (var i = 0; i < A.length - 1; i++) {
    var k = i;
    for (var j = i + 1; j < A.length; j++) {
      if (A[j] < A[k]) {
        k = j;
      }
    }
    if (k != i) {
      var t = A[k];
      A[k] = A[i];
      A[i] = t;
      println(A);
    }
  }
  return A;
}

插入排序 -- 時(shí)間復(fù)雜度O(n^2)

//插入排序
//假定當(dāng)前元素之前的元素已經(jīng)排好序，先把自己的位置空出來，
//然后前面比自己大的元素依次向后移，直到空出一個(gè)"坑"，
//然后把目標(biāo)元素插入"坑"中
function insertSort(A) {
  for (var i = 1; i < A.length; i++) {
    var x = A[i];
    for (var j = i - 1; j >= 0 && A[j] > x; j--) {
      A[j + 1] = A[j];
    }
    if (A[j + 1] != x) {
      A[j + 1] = x;
      println(A);
    }
  }
  return A;
}

字符串反轉(zhuǎn) -- 時(shí)間復(fù)雜度O(logN)

//字符串反轉(zhuǎn)(比如：ABC -> CBA)
function inverse(s) {
  var arr = s.split('');
  var i = 0, j = arr.length - 1;
  while (i < j) {
    var t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
    i++;
    j--;
  }
  return arr.join('');
}

關(guān)于穩(wěn)定性排序的一個(gè)結(jié)論：

基于比較的簡單排序算法，即時(shí)間復(fù)雜度為O(N^2)的排序算法，通?？烧J(rèn)為均是穩(wěn)定排序
其它先進(jìn)的排序算法，比如歸并排序、堆排序、桶排序之類（通常這類算法的時(shí)間復(fù)雜度可優(yōu)化為n*LogN），通常可認(rèn)為均是不穩(wěn)定排序

單鏈表實(shí)現(xiàn)

<script type="text/javascript">
  function print(msg) {
    document.write(msg);
  }
  function println(msg) {
    print(msg + "<br/>");
  }
  //節(jié)點(diǎn)類
  var Node = function (v) {
    this.data = v; //節(jié)點(diǎn)值
    this.next = null; //后繼節(jié)點(diǎn)
  }
  //單鏈表
  var SingleLink = function () {
    this.head = new Node(null); //約定頭節(jié)點(diǎn)僅占位，不存值
    //插入節(jié)點(diǎn)
    this.insert = function (v) {
      var p = this.head;
      while (p.next != null) {
        p = p.next;
      }
      p.next = new Node(v);
    }
    //刪除指定位置的節(jié)點(diǎn)
    this.removeAt = function (n) {
      if (n <= 0) {
        return;
      }
      var preNode = this.getNodeByIndex(n - 1);
      preNode.next = preNode.next.next;
    }
    //取第N個(gè)位置的節(jié)點(diǎn)(約定頭節(jié)點(diǎn)為第0個(gè)位置)
    //N大于鏈表元素個(gè)數(shù)時(shí)，返回最后一個(gè)元素
    this.getNodeByIndex = function (n) {
      var p = this.head;
      var i = 0;
      while (p.next != null && i < n) {
        p = p.next;
        i++;
      }
      return p;
    }
    //查詢值為V的節(jié)點(diǎn)，
    //如果鏈表中有多個(gè)相同值的節(jié)點(diǎn)，
    //返回第一個(gè)找到的
    this.getNodeByValue = function (v) {
      var p = this.head;
      while (p.next != null) {
        p = p.next;
        if (p.data == v) {
          return p;
        }
      }
      return null;
    }
    //打印輸出所有節(jié)點(diǎn)
    this.print = function () {
      var p = this.head;
      while (p.next != null) {
        p = p.next;
        print(p.data + " ");
      }
      println("");
    }
  }
  //測試單鏈表L中是否有重復(fù)元素
  function hasSameValueNode(singleLink) {
    var i = singleLink.head;
    while (i.next != null) {
      i = i.next;
      var j = i;
      while (j.next != null) {
        j = j.next;
        if (i.data == j.data) {
          return true;
        }
      }
    }
    return false;
  }
  //單鏈表元素反轉(zhuǎn)
  function reverseSingleLink(singleLink) {
    var arr = new Array();
    var p = singleLink.head;
    //先跑一遍，把所有節(jié)點(diǎn)放入數(shù)組
    while (p.next != null) {
      p = p.next;
      arr.push(p.data);
    }
    var newLink = new SingleLink();
    //再從后向前遍歷數(shù)組,加入新鏈表
    for (var i = arr.length - 1; i >= 0; i--) {
      newLink.insert(arr[i]);
    }
    return newLink;
  }
  var linkTest = new SingleLink();
  linkTest.insert('A');
  linkTest.insert('B');
  linkTest.insert('C');
  linkTest.insert('D');
  linkTest.print();//A B C D
  var newLink = reverseSingleLink(linkTest);
  newLink.print();//D C B A
</script>

關(guān)于鄰接矩陣、鄰接表的選擇：

鄰接矩陣、鄰接表都是圖的基本存儲(chǔ)方式，
稀松圖情況下（即邊遠(yuǎn)小于頂點(diǎn)情況下），用鄰接表存儲(chǔ)比較適合（相對(duì)矩陣N*N而言，鄰接表只存儲(chǔ)有值的邊、頂點(diǎn)，不存儲(chǔ)空值，存儲(chǔ)效率更高）
稠密圖情況下（即邊遠(yuǎn)大地頂點(diǎn)情況下），用鄰接矩陣存儲(chǔ)比較適合（數(shù)據(jù)較多的情況下，要對(duì)較做遍歷，如果用鏈表存儲(chǔ)，要經(jīng)常跳來跳去，效率較低）

堆：

幾乎完全的二叉樹：除了最右邊位置上的一個(gè)或幾個(gè)葉子可能缺少的二叉樹。在物理存儲(chǔ)上，可以用數(shù)組來存儲(chǔ)，如果A[j]的頂點(diǎn)有左、右子節(jié)點(diǎn)，則左節(jié)點(diǎn)為A[2j]、右節(jié)點(diǎn)為A[2j+1]，A[j]的父頂點(diǎn)存儲(chǔ)在A[j/2]中

堆：本身是一顆幾乎完全的二叉樹，而且父節(jié)點(diǎn)的值不小于子節(jié)點(diǎn)的值。應(yīng)用場景：優(yōu)先隊(duì)列，尋找最大或次最大值；以及把一個(gè)新元素插入優(yōu)先隊(duì)列。

注：以下所有討論的堆，約定索引0處的元素僅占位，有效元素從下標(biāo)1開始

根據(jù)堆的定義，可以用以下代碼測試一個(gè)數(shù)組是否為堆：

//測試數(shù)組H是否為堆
//(約定有效元素從下標(biāo)1開始)
//時(shí)間復(fù)雜度O(n)
function isHeap(H) {
  if (H.length <= 1) { return false; }
  var half = Math.floor(H.length / 2); //根據(jù)堆的性質(zhì)，循環(huán)上限只取一半就夠了
  for (var i = 1; i <= half; i++) {
    //如果父節(jié)點(diǎn)，比任何一個(gè)子節(jié)點(diǎn) 小，即違反堆定義
    if (H[i] < H[2 * i] || H[i] < H[2 * i + 1]) {
      return false;
    }
  }
  return true;
}

節(jié)點(diǎn)向上調(diào)整siftUp

某些情況下，如果堆中的某個(gè)元素值改變后(比如 10,8,9,7 變成 10,8,9,20 后，20需要向上調(diào)整 )，不再滿足堆的定義，需要向上調(diào)整時(shí)，可以用以下代碼實(shí)現(xiàn)

//堆中的節(jié)點(diǎn)上移
//(約定有效元素從下標(biāo)1開始)
function siftUp(H, i) {
  if (i <= 1) {
    return;
  }
  for (var j = i; j > 1; j = Math.floor(j / 2)) {
    var k = Math.floor(j / 2);
    //發(fā)現(xiàn) 子節(jié)點(diǎn) 比 父節(jié)點(diǎn)大，則與父節(jié)點(diǎn)交換位置
    if (H[j] > H[k]) {
      var t = H[j];
      H[j] = H[k];
      H[k] = t;
    }
    else {
      //說明已經(jīng)符合堆定義，調(diào)整結(jié)束，退出
      return;
    }
  }
}

節(jié)點(diǎn)向下調(diào)整siftDown (既然有向上調(diào)整，自然也有向下調(diào)整)

//堆中的節(jié)點(diǎn)下移
//(約定有效元素從下標(biāo)1開始)
//時(shí)間復(fù)雜度O(logN)
function siftDown(H, i) {
  if (2 * i > H.length) { //葉子節(jié)點(diǎn)，就不用再向下移了
    return;
  }
  for (var j = 2 * i; j < H.length; j = 2 * j) {
    //將j定位到 二個(gè)子節(jié)點(diǎn)中較大的那個(gè)上(很巧妙的做法)
    if (H[j + 1] > H[j]) {
      j++;
    }
    var k = Math.floor(j / 2);
    if (H[k] < H[j]) {
      var t = H[k];
      H[k] = H[j];
      H[j] = t;
    }
    else {
      return;
    }
  }
}

向堆中添加新元素

//向堆H中添加元素x
//時(shí)間復(fù)雜度O(logN)
function insert(H, x) {
  //思路：先在數(shù)組最后加入目標(biāo)元素x
  H.push(x);
  //然后向上推
  siftUp(H, H.length - 1);
}

從堆中刪除元素

//刪除堆H中指定位置i的元素
//時(shí)間復(fù)雜度O(logN)
function remove(H, i) {
  //思路：先把位置i的元素與最后位置的元素n交換
  //然后數(shù)據(jù)長度減1(這樣就把i位置的元素給干掉了，但是整個(gè)堆就被破壞了)
  //需要做一個(gè)決定：最后一個(gè)元素n需要向上調(diào)整，還是向下調(diào)整
  //依據(jù)：比如比原來該位置的元素大，則向上調(diào)整，反之向下調(diào)整
  var x = H[i]; //先把原來i位置的元素保護(hù)起來
  //把最后一個(gè)元素放到i位置
  //同時(shí)刪除最后一個(gè)元素(js語言的優(yōu)越性體現(xiàn)!)
  H[i] = H.pop();
  var n = H.length - 1;
  if (i == n + 1) {
    //如果去掉的正好是最后二個(gè)元素之一，
    //無需再調(diào)整
    return ;
  }
  if (H[i] > x) {
    siftUp(H, i);
  }
  else {
    siftDown(H, i);
  }
}
//從堆中刪除最大項(xiàng)
//返回最大值
//時(shí)間復(fù)雜度O(logN)
function deleteMax(H) {
  var x = H[1];
  remove(H, 1);
  return x;
}

堆排序：

這是一種思路非常巧妙的排序算法，精華在于充分利用了“堆”這種數(shù)據(jù)結(jié)構(gòu)本身的特點(diǎn)（首元素必然最大），而且每個(gè)元素的上移、下調(diào)，時(shí)間復(fù)試度又比較低，僅為O(logN)，空間上，也無需借助額外的存儲(chǔ)空間，僅在數(shù)組自身內(nèi)部交換元素即可。

思路：

1、先將首元素(即最大元素)與最末尾的元素對(duì)調(diào)---目的在于，把最大值沉底，下一輪重就不再管它了
2、經(jīng)過1后，剩下的元素通常已經(jīng)不再是一個(gè)堆了。這時(shí)，只要把新的首元素用siftDown下調(diào)，調(diào)整完以后，新的最大值元素自然又上升到了首元素的位置
3、反復(fù)1、2，大的元素逐一沉底，最后整個(gè)數(shù)組就有序了。
時(shí)間復(fù)雜度分析：創(chuàng)建堆需要O(n)的代價(jià)，每次siftDown代價(jià)為O(logN)，最多調(diào)整n-1個(gè)元素，所以總代價(jià)為 O(N) + (N-1)O(logN)，最終時(shí)間復(fù)雜度為O(NLogN)

//堆中的節(jié)點(diǎn)下移
//(約定有效元素從下標(biāo)1開始)
//i為要調(diào)整的元素索引
//n為待處理的有效元素下標(biāo)范圍上限值
//時(shí)間復(fù)雜度O(logN)
function siftDown(H, i, n) {
  if (n >= H.length) {
    n = H.length;
  }
  if (2 * i > n) { //葉子節(jié)點(diǎn)，就不用再向下移了
    return;
  }
  for (var j = 2 * i; j < n; j = 2 * j) {
    //將j定位到 二個(gè)子節(jié)點(diǎn)中較大的那個(gè)上(很巧妙的做法)
    if (H[j + 1] > H[j]) {
      j++;
    }
    var k = Math.floor(j / 2);
    if (H[k] < H[j]) {
      var t = H[k];
      H[k] = H[j];
      H[j] = t;
    }
    else {
      return;
    }
  }
}
//對(duì)數(shù)組的前n個(gè)元素進(jìn)行創(chuàng)建堆的操作
function makeHeap(A, n) {
  if (n >= A.length) {
    n = A.length;
  }
  for (var i = Math.floor(n / 2); i >= 1; i--) {
    siftDown(A, i, n);
  }
}
//堆排序(非降序排列)
//時(shí)間復(fù)雜度O(nlogN)
function heapSort(H) {
  //先建堆
  makeHeap(H, H.length);
  for (var j = H.length - 1; j >= 2; j--) {
    //首元素必然是最大的
    //將最大元素與最后一個(gè)元素互換，
    //即將最大元素沉底，下一輪不再考慮
    var x = H[1];
    H[1] = H[j];
    H[j] = x;
    //互換后，剩下的元素不再滿足堆定義，
    //把新的首元素下調(diào)(以便繼續(xù)維持堆的"形狀")
    //調(diào)整完后，剩下元素中的最大值必須又浮到了第一位
    //進(jìn)入下一輪循環(huán)
    siftDown(H, 1, j - 1);
  }
  return H;
}

關(guān)于建堆，如果明白其中的原理后，也可以逆向思路，反過來做

function makeHeap2(A, n) {
  if (n >= A.length) {
    n = A.length;
  }
  for (var i = Math.floor(n / 2); i <= n; i++) {
    siftUp(A, i);
  }
}

不相交集合查找、合并

//定義節(jié)點(diǎn)Node類
var Node = function (v, p) {
    this.value = v; //節(jié)點(diǎn)的值
    this.parent = p; //節(jié)點(diǎn)的父節(jié)點(diǎn)
    this.rank = 0; //節(jié)點(diǎn)的秩(默認(rèn)為0)    
}
//查找包含節(jié)點(diǎn)x的樹根節(jié)點(diǎn) 
var find = function (x) {
    var y = x;
    while (y.parent != null) {
      y = y.parent;
    }
    var root = y;
    y = x;
    //沿x到根進(jìn)行“路徑壓縮”
    while (y.parent != null) {
      //先把父節(jié)點(diǎn)保存起來，否則下一行調(diào)整后，就弄丟了
      var w = y.parent;
      //將目標(biāo)節(jié)點(diǎn)掛到根下
      y.parent = root;
      //再將工作指針，還原到 目標(biāo)節(jié)點(diǎn)原來的父節(jié)點(diǎn)上，
      //繼續(xù)向上逐層壓縮
      y = w
    }
    return root;
}
//合并節(jié)點(diǎn)x，y對(duì)應(yīng)的兩個(gè)樹
//時(shí)間復(fù)雜度O(m) - m為待合并的子集合數(shù)量
var union = function (x, y) {
    //先找到x所屬集合的根
    var u = find(x);
    //再找到y(tǒng)所屬集合的根
    var v = find(y);
    //把rank小的集合掛到rank大的集合上
    if (u.rank <= v.rank) {
      u.parent = v;
      if (u.rank == v.rank) {
        //二個(gè)集合的rank不分伯仲時(shí)
        //給"勝"出方一點(diǎn)獎(jiǎng)勵(lì)，rank+1
        v.rank += 1;
      }
    }
    else {
      v.parent = u;
    }
}

歸納法：

先來看二個(gè)排序的遞歸實(shí)現(xiàn)

//選擇排序的遞歸實(shí)現(xiàn)
//調(diào)用示例: selectionSort([3,2,1],0)
function selectionSortRec(A, i) {
  var n = A.length - 1;
  if (i < n) {
    var k = i;
    for (var j = i + 1; j <= n; j++) {
      if (A[j] < A[k]) {
        k = j
      }
    }
    if (k != i) {
      var t = A[k];
      A[k] = A[i];
      A[i] = t;
    }
    selectionSortRec(A, i + 1);
  }
}
//插入排序遞歸實(shí)現(xiàn)
//調(diào)用示例:insertSortRec([4,3,2,1],3);
function insertSortRec(A, i) {
  if (i > 0) {
    var x = A[i];
    insertSortRec(A, i - 1);
    var j = i - 1;
    while (j >= 0 && A[j] > x) {
      A[j + 1] = A[j];
      j--;
    }
    A[j + 1] = x;
  }
}

遞歸的程序通常易于理解，代碼也容易實(shí)現(xiàn)，再來看二個(gè)小例子：

從數(shù)組中，找出最大值

//在數(shù)組中找最大值(遞歸實(shí)現(xiàn))
function findMax(A, i) {
  if (i == 0) {
    return A[0];
  }
  var y = findMax(A, i - 1);
  var x = A[i - 1];
  return y > x ? y : x;
}
var A = [1,2,3,4,5,6,7,8,9];
var test = findMax(A,A.length);
alert(test);//返回9

有一個(gè)已經(jīng)升序排序好的數(shù)組，檢查數(shù)組中是否存在二個(gè)數(shù)，它們的和正好為x ？

//5.33 遞歸實(shí)現(xiàn)
//A為[1..n]已經(jīng)排好序的數(shù)組
//x為要測試的和
//如果存在二個(gè)數(shù)的和為x，則返回true，否則返回false
function sumX(A, i, j, x) {
  if (i >= j) {
    return false;
  }
  if (A[i] + A[j] == x) {
    return true;
  }
  else if (A[i] + A[j] < x) {
    //i后移
    return sumX(A, i + 1, j, x);
  }
  else {
    //j前移
    return sumX(A, i, j - 1, x);
  }
}
var A = [1, 2, 3, 4, 5, 6, 7, 8];
var test1 = sumX(A,0,A.length-1,9);
alert(test1); //返回true

遞歸程序雖然思路清晰，但通常效率不高，一般來講，遞歸實(shí)現(xiàn)，都可以改寫成非遞歸實(shí)現(xiàn)，上面的代碼也可以寫成：

//5.33 非遞歸實(shí)現(xiàn)
function sumX2(A, x) {
  var i = 0, j = A.length - 1;
  while (i < j) {
    if (A[i] + A[j] == x) {
      return true;
    }
    else if (A[i] + A[j] < x) {
      //i后移
      i++;
    }
    else {
      //j前移
      j--;
    }
  }
  return false;
}
var A = [1, 2, 3, 4, 5, 6, 7, 8];
var test2 = sumX2(A,9);
alert(test2);//返回true

遞歸并不總代表低效率，有些場景中，遞歸的效率反而更高，比如計(jì)算x的m次冪，常規(guī)算法，需要m次乘法運(yùn)算，下面的算法，卻將時(shí)間復(fù)雜度降到了O(logn)

//計(jì)算x的m次冪（遞歸實(shí)現(xiàn)）
//時(shí)間復(fù)雜度O(logn)
function expRec(x, m) {
  if (m == 0) {
    return 1;
  }
  var y = expRec(x, Math.floor(m / 2));
  y = y * y;
  if (m % 2 != 0) {
    y = x * y
  }
  return y;
}

當(dāng)然，這其中并不光是遞歸的功勞，其效率的改進(jìn) 主要依賴于一個(gè)數(shù)學(xué)常識(shí)： x^m = [x^(m/2)]^2，關(guān)于這個(gè)問題，還有一個(gè)思路很獨(dú)特的非遞歸解法，巧妙的利用了二進(jìn)制的特點(diǎn)

//將10進(jìn)制數(shù)轉(zhuǎn)化成2進(jìn)制
function toBin(dec) {
  var bits = [];
  var dividend = dec;
  var remainder = 0;
  while (dividend >= 2) {
    remainder = dividend % 2;
    bits.push(remainder);
    dividend = (dividend - remainder) / 2;
  }
  bits.push(dividend);
  bits.reverse();
  return bits.join("");
}
//計(jì)算x的m次冪（非遞歸實(shí)現(xiàn)）
//很獨(dú)特的一種解法
function exp(x, m) {
  var y = 1;
  var bin = toBin(m).split('');
  //先將m轉(zhuǎn)化成2進(jìn)制形式
  for (var j = 0; j < bin.length; j++) {
    y = y * 2;
    //如果2進(jìn)制的第j位是1，則再*x
    if (bin[j] == "1") {
      y = x * y
    }
  }
  return y;
}
//println(expRec(2, 5));
//println(exp(2, 5));

再來看看經(jīng)典的多項(xiàng)式求值問題：

給定一串實(shí)數(shù)An，An-1，...，A1，A0 和一個(gè)實(shí)數(shù)X，計(jì)算多項(xiàng)式Pn(x)的值

著名的Horner公式：

已經(jīng)如何計(jì)算：

顯然有：

這樣只需要 N次乘法+N次加法

//多項(xiàng)式求值
//N次乘法+N次加法搞定，偉大的改進(jìn)！
function horner(A, x) {
  var n = A.length - 1
  var p = A[n];
  for (var j = 0; j < n; j++) {
    p = x * p + A[n - j - 1];
  }
  return p;
}
//計(jì)算: y(2) = 3x^3 + 2x^2 + x -1;
var A = [-1, 1, 2, 3];
var y = horner(A, 2);
alert(y);//33

多數(shù)問題：

一個(gè)元素個(gè)數(shù)為n的數(shù)組，希望快速找出其中大于出現(xiàn)次數(shù)>n/2的元素（該元素也稱為多數(shù)元素）。通常可用于選票系統(tǒng)，快速判定某個(gè)候選人的票數(shù)是否過半。最優(yōu)算法如下：

//找出數(shù)組A中“可能存在”的多數(shù)元素
function candidate(A, m) {
  var count = 1, c = A[m], n = A.length - 1;
  while (m < n && count > 0) {
    m++;
    if (A[m] == c) {
      count++;
    }
    else {
      count--;
    }
  }
  if (m == n) {
    return c;
  }
  else {
    return candidate(A, m + 1);
  }
}
//尋找多數(shù)元素
//時(shí)間復(fù)雜度O(n)
function majority(A) {
  var c = candidate(A, 0);
  var count = 0;
  //找出的c，可能是多數(shù)元素，也可能不是，
  //必須再數(shù)一遍，以確保結(jié)果正確
  for (var i = 0; i < A.length; i++) {
    if (A[i] == c) {
      count++;
    }
  }
  //如果過半，則確定為多數(shù)元素
  if (count > Math.floor(A.length / 2)) {
    return c;
  }
  return null;
}
var m = majority([3, 2, 3, 3, 4, 3]);
alert(m);

以上算法基于這樣一個(gè)結(jié)論：在原序列中去除兩個(gè)不同的元素后，那么在原序列中的多數(shù)元素在新序列中還是多數(shù)元素

證明如下：

如果原序列的元素個(gè)數(shù)為n，多數(shù)元素出現(xiàn)的次數(shù)為x，則 x/n > 1/2
去掉二個(gè)不同的元素后，
a)如果去掉的元素中不包括多數(shù)元素，則新序列中，原先的多數(shù)元素個(gè)數(shù)/新序列元素總數(shù) = x/(n-2) ，因?yàn)閤/n > 1/2 ，所以 x/(n-2) 也必然>1/2
b)如果去掉的元素中包含多數(shù)元素，則新序列中，原先的多數(shù)元素個(gè)數(shù)/新序列元素總數(shù) = (x-1)/(n-2) ，因?yàn)閤/n > 1/2 =》 x>n/2 代入 (x-1)/(n-2) 中，
有 (x-1)/(n-2) > (n/2 -1)/(n-2) = 2(n-2)/(n-2) = 1/2

下一個(gè)問題：全排列

function swap(A, i, j) {
  var t = A[i];
  A[i] = A[j];
  A[j] = t;
}
function println(msg) {
  document.write(msg + "<br/>");
}
//全排列算法
function perm(P, m) {
  var n = P.length - 1;
  if (m == n) {
    //完成一個(gè)新排列時(shí)，輸出
    println(P);
    return;
  }
  for (var j = m; j <= n; j++) {
    //將起始元素與后面的每個(gè)元素交換
    swap(P, j, m);
    //在前m個(gè)元素已經(jīng)排好的基礎(chǔ)上
    //再加一個(gè)元素進(jìn)行新排列
    perm(P, m + 1);
    //把j與m換回來，恢復(fù)遞歸調(diào)用前的“現(xiàn)場"，
    //否則因?yàn)檫f歸調(diào)用前，swap已經(jīng)將原順序破壞了，
    //導(dǎo)致后面生成排序時(shí)，可能生成重復(fù)
    swap(P, j, m);
  }
}
perm([1, 2, 3], 0);
//1,2,3
//1,3,2
//2,1,3
//2,3,1
//3,2,1
//3,1,2

分治法：

要點(diǎn)：將問題劃分成二個(gè)子問題時(shí)，盡量讓子問題的規(guī)模大致相等。這樣才能最大程度的體現(xiàn)一分為二，將問題規(guī)模以對(duì)數(shù)折半縮小的優(yōu)勢。

//打印輸出(調(diào)試用)
function println(msg) {
  document.write(msg + "<br/>");
}
//數(shù)組中i,j位置的元素交換(輔助函數(shù))
function swap(A, i, j) {
  var t = A[i];
  A[i] = A[j];
  A[j] = t;
}
//尋找數(shù)組A中的最大、最小值(分治法實(shí)現(xiàn))
function findMinMaxDiv(A, low, high) {
  //最小規(guī)模子問題的解
  if (high - low == 1) {
    if (A[low] < A[high]) {
      return [A[low], A[high]];
    }
    else {
      return [A[high], A[low]];
    }
  }
  var mid = Math.floor((low + high) / 2);
  //在前一半元素中尋找子問題的解
  var r1 = findMinMaxDiv(A, low, mid);
  //在后一半元素中尋找子問題的解
  var r2 = findMinMaxDiv(A, mid + 1, high);
  //把二部分的解合并
  var x = r1[0] > r2[0] ? r2[0] : r1[0];
  var y = r1[1] > r2[1] ? r1[1] : r2[1];
  return [x, y];
}
var r = findMinMaxDiv([1, 2, 3, 4, 5, 6, 7, 8], 0, 7);
println(r); //1,8
//二分搜索(分治法實(shí)現(xiàn))
//輸入：A為已按非降序排列的數(shù)組
//x 為要搜索的值
//low,high搜索的起、止索引范圍
//返回：如果找到，返回下標(biāo)，否則返回-1
function binarySearchDiv(A, x, low, high) {
  if (low > high) {
    return -1;
  }
  var mid = Math.floor((low + high) / 2);
  if (x == A[mid]) {
    return mid;
  }
  else if (x < A[mid]) {
    return binarySearchDiv(A, x, low, mid - 1);
  }
  else {
    return binarySearchDiv(A, x, mid + 1, high);
  }
}
var f = binarySearchDiv([1, 2, 3, 4, 5, 6, 7], 4, 0, 6);
println(f); //3
//將數(shù)組A，以low位置的元素為界，劃分為前后二半
//n為待處理的索引范圍上限
function split(A, low, n) {
  if (n >= A.length - 1) {
    n = A.length - 1;
  }
  var i = low;
  var x = A[low];
  //二個(gè)指針一前一后“跟隨”，
  //最前面的指針發(fā)現(xiàn)有元素比分界元素小時(shí)，換到前半部
  //后面的指針再緊跟上，“夫唱婦隨”一路到頭
  for (var j = low + 1; j <= n; j++) {
    if (A[j] <= x) {
      i++;
      if (i != j) {
        swap(A, i, j);
      }
    }
  }
  //經(jīng)過上面的折騰后，除low元素外，其它的元素均以就位
  //最后需要把low與最后一個(gè)比low位置小的元素交換，
  //以便把low放在分水嶺位置上
  swap(A, low, i);
  return [A, i];
}
var A = [5, 1, 2, 6, 3];
var b = split(A, 0, A.length - 1);
println(b[0]); //3,1,2,5,6
//快速排序 
function quickSort(A, low, high) {
  var w = high;
  if (low < high) {
    var t = split(A, low, w); //分治思路，先分成二半
    w = t[1];
    //在前一半求解
    quickSort(A, low, w - 1);
    //在后一半求解
    quickSort(A, w + 1, high);
  }
}
var A = [5, 6, 4, 7, 3];
quickSort(A, 0, A.length - 1);
println(A); //3,4,5,6,7

split算法的思想應(yīng)用：

設(shè)A[1..n]是一個(gè)整數(shù)集，給出一算法重排數(shù)組A中元素，使得所有的負(fù)整數(shù)放到所有非負(fù)整數(shù)的左邊，你的算法的運(yùn)行時(shí)間應(yīng)當(dāng)為Θ(n)

function sort1(A) {
  var i = 0, j = A.length - 1;
  while (i < j) {
    if (A[i] >= 0 && A[j] >= 0) {
      j--;
    }
    else if (A[i] < 0 && A[j] < 0) {
      i++;
    }
    else if (A[i] > 0 && A[j] < 0) {
      swap(A, i, j);
      i++;
      j--;
    }
    else {
      i++;
      j--;
    }
  }
}
function sort2(A) {
  if (A.length <= 1) { return; }
  var i = 0;
  for (var j = i + 1; j < A.length; j++) {
    if (A[j] < 0 && A[i] >= 0) {
      swap(A, i, j);
      i++;
    }
  }
}
var a = [1, -2, 3, -4, 5, -6, 0];
sort1(a);
println(a);//-6,-2,-4,3,5,1,0
var b = [1, -2, 3, -4, 5, -6, 0];
sort2(b);
println(b);//-2,-4,-6,1,5,3,0

希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: