本文实例讲述了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 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 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），通常可认为均是不稳定排序
单链表实现

关于邻接矩阵、邻接表的选择：
邻接矩阵、邻接表都是图的基本存储方式，
稀松图情况下（即边远小于顶点情况下），用邻接表存储比较适合（相对矩阵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.length) { //叶子节点，就不用再向下移了 return; } for (var j = 2 * i; j h[j]) { j++; } var k = math.floor(j / 2); if (h[k] 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 h[j]) { j++; } var k = math.floor(j / 2); if (h[k] = 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 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] = 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 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 +
);}//全排列算法function perm(p, m) { var n = p.length - 1; if (m == n) { //完成一个新排列时，输出 println(p); return; } for (var j = m; j 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.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 = 0) { j--; } else if (a[i] < 0 && a[j] 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) { 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程序设计有所帮助。