常见前端算法的JavaScript实现|网站前端开发_前端开发者

网站前端开发_前端开发者丨前端资源

https://www.rokub.com

排序算法

1. 冒泡排序
javascript 代码

function bubbleSort(arr){<br /><br /> var i = j = 0;<br /><br /> for(i=1;i<arr.length;i++){<br /><br /> for(j=0;j<arr.length-i;j++){<br /><br /> var temp = 0;<br /><br /> if(arr[j]>arr[j+1]){<br /><br /> temp = arr[j];<br /><br /> arr[j] = arr[j+1];<br /><br /> arr[j+1] = temp;<br /><br /> }<br /><br /> }<br /><br /> }<br /><br /> }

2. 快速排序
javascript 代码

function quickSort(arr,l,r){<br /><br /> if(l < r){<br /><br /> var i = l, j = r, x = arr[i];<br /><br /> while(i<j){<br /><br /> while(i<j && arr[j]>x)<br /><br /> j–;</p><br /> <p> if(i<j)<br /><br /> //这里用i++，被换过来的必然比x小，赋值后直接让i自加，不用再比较，可以提高效率<br /><br /> arr[i++] = arr[j];</p><br /> <p> while(i<j && arr[i]<x)<br /><br /> i++;</p><br /> <p> if(i<j)<br /><br /> //这里用j–，被换过来的必然比x大，赋值后直接让j自减，不用再比较，可以提高效率<br /><br /> arr[j–] = arr[i];<br /><br /> }<br /><br /> arr[i] = x;</p><br /> <p> quickSort(arr, l, i-1);<br /><br /> quickSort(arr, i+1, r);<br /><br /> }<br /><br /> }

3. 二路归并
PS：将两个按值有序序列合并成一个按值有序序列，则称之为二路归并排序。
javascript 代码

function merge(left, right) {<br /><br /> var result = [],<br /><br /> il = 0,<br /><br /> ir = 0;</p><br /> <p> while (il < left.length && ir < right.length) {<br /><br /> if (left[il] < right[ir]) {<br /><br /> result.push(left[il++]);<br /><br /> } else {<br /><br /> result.push(right[ir++]);<br /><br /> }<br /><br /> }<br /><br /> while(left[il]){<br /><br /> result.push(left[il++]);<br /><br /> }<br /><br /> while(right[ir]){<br /><br /> result.push(right[ir++]);<br /><br /> }<br /><br /> return result;<br /><br /> }

字符串操作

1. 判断回文字符串
javascript 代码

function palindrome(str){<br /><br /> // \W匹配任何非单词字符。等价于“[^A-Za-z0-9_]”。<br /><br /> var re = /[\W_]/g;<br /><br /> // 将字符串变成小写字符,并干掉除字母数字外的字符<br /><br /> var lowRegStr = str.toLowerCase().replace(re,”);<br /><br /> // 如果字符串lowRegStr的length长度为0时，字符串即是palindrome<br /><br /> if(lowRegStr.length===0)<br /><br /> return true;<br /><br /> // 如果字符串的第一个和最后一个字符不相同，那么字符串就不是palindrome<br /><br /> if(lowRegStr[0]!=lowRegStr[lowRegStr.length-1])<br /><br /> return false;<br /><br /> //递归<br /><br /> return palindrome(lowRegStr.slice(1,lowRegStr.length-1));<br /><br /> }

2. 翻转字符串
2.1 思路1：反向遍历字符串
javascript 代码

function reverseString(str){<br /><br /> var tmp = ”;<br /><br /> for(var i=str.length-1;i>=0;i–)<br /><br /> tmp += str[i];<br /><br /> return tmp<br /><br /> }

2.2 思路2：转化成array操作。
javascript 代码

function reverseString2(str){<br /><br /> var arr = str.split(“”);<br /><br /> var i = 0,j = arr.length-1;<br /><br /> while(i<j){<br /><br /> tmp = arr[i];<br /><br /> arr[i] = arr[j];<br /><br /> arr[j] = tmp;<br /><br /> i++;<br /><br /> j–;<br /><br /> }<br /><br /> return arr.join(“”);<br /><br /> }

PS：什么？你要问为啥不直接操作str？ 因为str[i]是只读的，不能str[0]=str[1]这样操作。
再PS：如果允许用reverse()，也可以用’str’.split(”).reverse().join(”)实现。

3. 生成指定长度随机字符串
PS：配合模糊等效果可以生成个验证码- –
javascript 代码

function randomString(n){<br /><br /> var str = ‘abcdefghijklmnopqrstuvwxyz0123456789’;<br /><br /> var tmp = ”;<br /><br /> for(var i=0;i<n;i++)<br /><br /> tmp += str.charAt(Math.round(Math.random()*str.length));<br /><br /> return tmp;<br /><br /> }

4. 统计字符串中次数最多字母
PS：利用Object中key的唯一性，利用key来进行筛选，然后计数。
javascript 代码

function findMaxDuplicateChar(str) {<br /><br /> if(str.length == 1) {<br /><br /> return str;<br /><br /> }<br /><br /> var charObj = {};<br /><br /> for(var i = 0; i < str.length; i++) {<br /><br /> if(!charObj[str.charAt(i)]) {<br /><br /> charObj[str.charAt(i)] = 1;<br /><br /> } else {<br /><br /> charObj[str.charAt(i)] += 1;<br /><br /> }<br /><br /> }<br /><br /> var maxChar = ”,<br /><br /> maxValue = 1;<br /><br /> for(var k in charObj) {<br /><br /> if(charObj[k] >= maxValue) {<br /><br /> maxChar = k;<br /><br /> maxValue = charObj[k];<br /><br /> }<br /><br /> }<br /><br /> return maxChar + ‘：’ + maxValue;<br /><br /> }

数组操作

1. 数组去重
PS: 还是利用Object中key的唯一性，利用key来进行筛选。
javascript 代码

function unique(arr){<br /><br /> var obj = {}<br /><br /> var data = []<br /><br /> for(var i in arr){<br /><br /> if(!obj[arr[i]]){<br /><br /> obj[arr[i]] = true;<br /><br /> data.push(arr[i]);<br /><br /> }<br /><br /> }<br /><br /> return data;<br /><br /> }

2. Number数组中最大差值
javascript 代码

function getMaxProfit(arr){<br /><br /> var min = arr[0], max = arr[0];<br /><br /> for(var i=0;i<arr.length;i++){<br /><br /> if(arr[i]<min)<br /><br /> min = arr[i];<br /><br /> if(arr[i]>max)<br /><br /> max = arr[i];<br /><br /> }<br /><br /> return max – min;<br /><br /> }

其他常见算法

1. 阶乘
1.1 非递归实现
javascript 代码

function factorialize(num) {<br /><br /> var result = 1;<br /><br /> if(num < 2) return 1;<br /><br /> while(num>1)<br /><br /> result *= num–;<br /><br /> return result;<br /><br /> }

1.2 递归实现
javascript 代码

function factorialize(num) {<br /><br /> var result = 1;<br /><br /> if(num < 2) return 1;<br /><br /> if(num > 1){<br /><br /> return num * factorialize(num – 1);<br /><br /> }<br /><br /> }

2. 生成菲波那切数列
PS：斐波那契数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列主要考察递归的调用。通过定义fibo[i] = fibo[i-1]+fibo[i-2];来生成斐波那契数组。

2.1 强行递归实现
javascript 代码

function getfib(n){<br /><br /> if (n < 2) {<br /><br /> return n;<br /><br /> } else {<br /><br /> return getfib(n-1) + getfib(n-2);<br /><br /> }<br /><br /> }<br /><br /> function fibo(len){<br /><br /> var fibo = [];<br /><br /> for(var i=0;i<len;i++)<br /><br /> fibo.push(getfib(i));<br /><br /> return fibo;<br /><br /> }

2.2 简约非递归版
javascript 代码

function getFibonacci(n) {<br /><br /> var fibarr = [];<br /><br /> var i = 0;<br /><br /> while(i < n) {<br /><br /> if(i <= 1) {<br /><br /> fibarr.push(i);<br /><br /> } else {<br /><br /> fibarr.push(fibarr[i – 1] + fibarr[i – 2])<br /><br /> }<br /><br /> i++;<br /><br /> }<br /><br /> return fibarr;<br /><br /> }

3. 二分查找
PS：二分查找又称折半查找，是在有序数组查找中用到的较为频繁的一种算法，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。

3.1 非递归实现
javascript 代码

function binary_search(arr, key) {<br /><br /> var low = 0,<br /><br /> high = arr.length – 1;<br /><br /> while(low <= high){<br /><br /> var mid = parseInt((high + low) / 2);<br /><br /> if(key == arr[mid]){<br /><br /> return mid;<br /><br /> }else if(key > arr[mid]){<br /><br /> low = mid + 1;<br /><br /> }else if(key < arr[mid]){<br /><br /> high = mid -1;<br /><br /> }<br /><br /> }<br /><br /> return -1;<br /><br /> };

3.2 递归实现
javascript 代码

function binary_search2(arr, low, high, key) {<br /><br /> if(low > high)<br /><br /> return -1;<br /><br /> var mid = parseInt((low + high)/2);<br /><br /> if(key == arr[mid])<br /><br /> return mid;<br /><br /> else if(key > arr[mid])<br /><br /> return binary_search2(arr, mid+1, high, key);<br /><br /> else if(key < arr[mid])<br /><br /> return binary_search2(arr, low, mid-1, key);<br /><br /> }

网站前端开发_前端开发者丨前端资源

https://www.rokub.com