DIV CSS 佈局教程網

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

入門級算法-線性查找-時間復雜度O(n)--相當於算法界中的HelloWorld

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

二分查找(又稱折半查找) - 適用於已排好序的線性結構 - 時間復雜度O(logN)

//二分搜索
//A為已按"升序排列"的數組，x為要查詢的元素
//返回目標元素的下標
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;
}

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

//冒泡排序
function bubbleSort(A) {
  for (var i = 0; i < A.length; i++) {
    var sorted = true;
  //注意：內循環是倒著來的
    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;
    }
  }
}

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

//選擇排序
//思路：找到最小值的下標記下來，再交換
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;
}

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

//插入排序
//假定當前元素之前的元素已經排好序，先把自己的位置空出來，
//然後前面比自己大的元素依次向後移，直到空出一個"坑"，
//然後把目標元素插入"坑"中
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;
}

字符串反轉 -- 時間復雜度O(logN)

//字符串反轉(比如：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('');
}

關於穩定性排序的一個結論：

基於比較的簡單排序算法，即時間復雜度為O(N^2)的排序算法，通常可認為均是穩定排序
其它先進的排序算法，比如歸並排序、堆排序、桶排序之類（通常這類算法的時間復雜度可優化為n*LogN），通常可認為均是不穩定排序

單鏈表實現

<script type="text/javascript">
  function print(msg) {
    document.write(msg);
  }
  function println(msg) {
    print(msg + "<br/>");
  }
  //節點類
  var Node = function (v) {
    this.data = v; //節點值
    this.next = null; //後繼節點
  }
  //單鏈表
  var SingleLink = function () {
    this.head = new Node(null); //約定頭節點僅占位，不存值
    //插入節點
    this.insert = function (v) {
      var p = this.head;
      while (p.next != null) {
        p = p.next;
      }
      p.next = new Node(v);
    }
    //刪除指定位置的節點
    this.removeAt = function (n) {
      if (n <= 0) {
        return;
      }
      var preNode = this.getNodeByIndex(n - 1);
      preNode.next = preNode.next.next;
    }
    //取第N個位置的節點(約定頭節點為第0個位置)
    //N大於鏈表元素個數時，返回最後一個元素
    this.getNodeByIndex = function (n) {
      var p = this.head;
      var i = 0;
      while (p.next != null && i < n) {
        p = p.next;
        i++;
      }
      return p;
    }
    //查詢值為V的節點，
    //如果鏈表中有多個相同值的節點，
    //返回第一個找到的
    this.getNodeByValue = function (v) {
      var p = this.head;
      while (p.next != null) {
        p = p.next;
        if (p.data == v) {
          return p;
        }
      }
      return null;
    }
    //打印輸出所有節點
    this.print = function () {
      var p = this.head;
      while (p.next != null) {
        p = p.next;
        print(p.data + " ");
      }
      println("");
    }
  }
  //測試單鏈表L中是否有重復元素
  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;
  }
  //單鏈表元素反轉
  function reverseSingleLink(singleLink) {
    var arr = new Array();
    var p = singleLink.head;
    //先跑一遍，把所有節點放入數組
    while (p.next != null) {
      p = p.next;
      arr.push(p.data);
    }
    var newLink = new SingleLink();
    //再從後向前遍歷數組,加入新鏈表
    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>

關於鄰接矩陣、鄰接表的選擇：

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

堆：

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

堆：本身是一顆幾乎完全的二叉樹，而且父節點的值不小於子節點的值。應用場景：優先隊列，尋找最大或次最大值；以及把一個新元素插入優先隊列。

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

根據堆的定義，可以用以下代碼測試一個數組是否為堆：

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

節點向上調整siftUp

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

//堆中的節點上移
//(約定有效元素從下標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);
    //發現 子節點 比 父節點大，則與父節點交換位置
    if (H[j] > H[k]) {
      var t = H[j];
      H[j] = H[k];
      H[k] = t;
    }
    else {
      //說明已經符合堆定義，調整結束，退出
      return;
    }
  }
}

節點向下調整siftDown (既然有向上調整，自然也有向下調整)

//堆中的節點下移
//(約定有效元素從下標1開始)
//時間復雜度O(logN)
function siftDown(H, i) {
  if (2 * i > H.length) { //葉子節點，就不用再向下移了
    return;
  }
  for (var j = 2 * i; j < H.length; j = 2 * j) {
    //將j定位到 二個子節點中較大的那個上(很巧妙的做法)
    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
//時間復雜度O(logN)
function insert(H, x) {
  //思路：先在數組最後加入目標元素x
  H.push(x);
  //然後向上推
  siftUp(H, H.length - 1);
}

從堆中刪除元素

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

堆排序：

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

思路：

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

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

關於建堆，如果明白其中的原理後，也可以逆向思路，反過來做

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

不相交集合查找、合並

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

歸納法：

先來看二個排序的遞歸實現

//選擇排序的遞歸實現
//調用示例: 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);
  }
}
//插入排序遞歸實現
//調用示例: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;
  }
}

遞歸的程序通常易於理解，代碼也容易實現，再來看二個小例子：

從數組中，找出最大值

//在數組中找最大值(遞歸實現)
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

有一個已經升序排序好的數組，檢查數組中是否存在二個數，它們的和正好為x ？

//5.33 遞歸實現
//A為[1..n]已經排好序的數組
//x為要測試的和
//如果存在二個數的和為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

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

//5.33 非遞歸實現
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

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

//計算x的m次冪（遞歸實現）
//時間復雜度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;
}

當然，這其中並不光是遞歸的功勞，其效率的改進 主要依賴於一個數學常識： x^m = [x^(m/2)]^2，關於這個問題，還有一個思路很獨特的非遞歸解法，巧妙的利用了二進制的特點

//將10進制數轉化成2進制
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("");
}
//計算x的m次冪（非遞歸實現）
//很獨特的一種解法
function exp(x, m) {
  var y = 1;
  var bin = toBin(m).split('');
  //先將m轉化成2進制形式
  for (var j = 0; j < bin.length; j++) {
    y = y * 2;
    //如果2進制的第j位是1，則再*x
    if (bin[j] == "1") {
      y = x * y
    }
  }
  return y;
}
//println(expRec(2, 5));
//println(exp(2, 5));

再來看看經典的多項式求值問題：

給定一串實數An，An-1，...，A1，A0 和一個實數X，計算多項式Pn(x)的值

著名的Horner公式：

已經如何計算：

顯然有：

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

//多項式求值
//N次乘法+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;
}
//計算: y(2) = 3x^3 + 2x^2 + x -1;
var A = [-1, 1, 2, 3];
var y = horner(A, 2);
alert(y);//33

多數問題：

一個元素個數為n的數組，希望快速找出其中大於出現次數>n/2的元素（該元素也稱為多數元素）。通常可用於選票系統，快速判定某個候選人的票數是否過半。最優算法如下：

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

以上算法基於這樣一個結論：在原序列中去除兩個不同的元素後，那麼在原序列中的多數元素在新序列中還是多數元素

證明如下：

如果原序列的元素個數為n，多數元素出現的次數為x，則 x/n > 1/2
去掉二個不同的元素後，
a)如果去掉的元素中不包括多數元素，則新序列中 ，原先的多數元素個數/新序列元素總數 = x/(n-2) ，因為x/n > 1/2 ，所以 x/(n-2) 也必然>1/2
b)如果去掉的元素中包含多數元素，則新序列中 ，原先的多數元素個數/新序列元素總數 = (x-1)/(n-2) ，因為x/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

下一個問題：全排列

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) {
    //完成一個新排列時，輸出
    println(P);
    return;
  }
  for (var j = m; j <= n; j++) {
    //將起始元素與後面的每個元素交換
    swap(P, j, m);
    //在前m個元素已經排好的基礎上
    //再加一個元素進行新排列
    perm(P, m + 1);
    //把j與m換回來，恢復遞歸調用前的“現場"，
    //否則因為遞歸調用前，swap已經將原順序破壞了，
    //導致後面生成排序時，可能生成重復
    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

分治法：

要點：將問題劃分成二個子問題時，盡量讓子問題的規模大致相等。這樣才能最大程度的體現一分為二，將問題規模以對數折半縮小的優勢。

//打印輸出(調試用)
function println(msg) {
  document.write(msg + "<br/>");
}
//數組中i,j位置的元素交換(輔助函數)
function swap(A, i, j) {
  var t = A[i];
  A[i] = A[j];
  A[j] = t;
}
//尋找數組A中的最大、最小值(分治法實現)
function findMinMaxDiv(A, low, high) {
  //最小規模子問題的解
  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
//二分搜索(分治法實現)
//輸入：A為已按非降序排列的數組
//x 為要搜索的值
//low,high搜索的起、止索引范圍
//返回：如果找到，返回下標，否則返回-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
//將數組A，以low位置的元素為界，劃分為前後二半
//n為待處理的索引范圍上限
function split(A, low, n) {
  if (n >= A.length - 1) {
    n = A.length - 1;
  }
  var i = low;
  var x = A[low];
  //二個指針一前一後“跟隨”，
  //最前面的指針發現有元素比分界元素小時，換到前半部
  //後面的指針再緊跟上，“夫唱婦隨”一路到頭
  for (var j = low + 1; j <= n; j++) {
    if (A[j] <= x) {
      i++;
      if (i != j) {
        swap(A, i, j);
      }
    }
  }
  //經過上面的折騰後，除low元素外，其它的元素均以就位
  //最後需要把low與最後一個比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算法的思想應用：

設A[1..n]是一個整數集，給出一算法重排數組A中元素，使得所有的負整數放到所有非負整數的左邊，你的算法的運行時間應當為Θ(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

希望本文所述對大家JavaScript程序設計有所幫助。