本文實例講述了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)的排序算法，通?？烧J為均是穩定排序
其它先進的排序算法，比如歸并排序、堆排序、桶排序之類（通常這類算法的時間復雜度可優化為n*LogN），通?？烧J為均是不穩定排序
單鏈表實現
<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，否則返回falsefunction 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的元素（該元素也稱為多數元素）。通?？捎糜谶x票系統，快速判定某個候選人的票數是否過半。最優算法如下：
//找出數組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搜索的起、止索引范圍//返回：如果找到，返回下標，否則返回-1function 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,7split算法的思想應用：
設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,0var b = [1, -2, 3, -4, 5, -6, 0];sort2(b);println(b);//-2,-4,-6,1,5,3,0希望本文所述對大家JavaScript程序設計有所幫助。
新聞熱點
疑難解答
