Javascript之常見算法整理（持續(xù)更新）

cc17 發(fā)布于2019-08-23 17:14 / 3474人閱讀

摘要：所以平均來說，插入排序的時間復(fù)雜度是。顯然，次方級別的時間復(fù)雜度代表著插入排序不適合數(shù)據(jù)特別多的情況，一般來說插入排序適合小數(shù)據(jù)量的排序。

更新了幾個知識點(diǎn)~歡迎一起交流呀~

一、排序

冒泡排序（復(fù)雜度O(n^2)）

//冒泡排序
function bubbleSort(arr) {
  for(var i = 0, len = arr.length; i < len - 1; ++i) {
    for(var j = 0; j < len - i - 1; ++j) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

插入排序（復(fù)雜度O(n^2)）

//插入排序 過程就像你拿到一副撲克牌然后對它排序一樣
function insertionSort(arr) {
  var n = arr.length;
  // 我們認(rèn)為arr[0]已經(jīng)被排序，所以i從1開始
  for (var i = 1; i < n; i++) {
    // 取出下一個新元素，在已排序的元素序列中從后向前掃描來與該新元素比較大小
    for (var j = i - 1; j >= 0; j--) {
      if (arr[i] >= arr[j]) { // 若要從大到小排序，則將該行改為if (arr[i] <= arr[j])即可
        // 如果新元素arr[i] 大于等于 已排序的元素序列的arr[j]，
        // 則將arr[i]插入到arr[j]的下一位置，保持序列從小到大的順序
        arr.splice(j + 1, 0, arr.splice(i, 1)[0]);
        // 由于序列是從小到大并從后向前掃描的，所以不必再比較下標(biāo)小于j的值比arr[j]小的值，退出循環(huán)
        break;  
      } else if (j === 0) {
        // arr[j]比已排序序列的元素都要小，將它插入到序列最前面
        arr.splice(j, 0, arr.splice(i, 1)[0]);
      }
    }
  }
  return arr;
}

當(dāng)目標(biāo)是升序排序，最好情況是序列本來已經(jīng)是升序排序，那么只需比較n-1次，時間復(fù)雜度O(n)。最壞情況是序列本來是降序排序，那么需比較n(n-1)/2次，時間復(fù)雜度O(n^2)。所以平均來說，插入排序的時間復(fù)雜度是O(n^2)。顯然，次方級別的時間復(fù)雜度代表著插入排序不適合數(shù)據(jù)特別多的情況，一般來說插入排序適合小數(shù)據(jù)量的排序。

選擇排序（復(fù)雜度O(n^2)）

function selectionSort(arr) {
  var len = arr.length;
  var mi, tmp;
  for (var i = 0; i < len - 1; i++) {
    mi = i;  //最小值的下標(biāo)
    for (var j = i + 1; j < len; j++) {
      if (arr[j] < arr[mi]) {
        mi = j;  //比較得到最小值的下標(biāo)
      }
    }
    tmp = arr[mi];
    arr[mi] = arr[i];
    arr[i] = tmp;
  }
  return arr;
}

快速排序（復(fù)雜度O(n^log(n))）

//快速排序
function qSort(arr) {
  //聲明并初始化左邊的數(shù)組和右邊的數(shù)組
  var left = [], right = [];
  //使用數(shù)組第一個元素作為基準(zhǔn)值
  var base = arr[0];
  //當(dāng)數(shù)組長度只有1或者為空時，直接返回?cái)?shù)組，不需要排序
  if(arr.length <= 1) return arr;
  //進(jìn)行遍歷
  for(var i = 1, len = arr.length; i < len; i++) {
    if(arr[i] < base) {
    //如果小于基準(zhǔn)值，push到左邊的數(shù)組（不能 <= ，否則不穩(wěn)定）
      left.push(arr[i]);
    } else {
    //如果大于等于基準(zhǔn)值，push到右邊的數(shù)組
      right.push(arr[i]);
    }
  }
  //遞歸并且合并數(shù)組元素
  return [...qSort(left), ...[base], ...qSort(right)];    //return qSort(left).concat([base], qSort(right));
}

二、字符串

回文字符串

//判斷回文字符串
function palindrome(str) {
  var reg = /[W\_]/g;
  var str0 = str.toLowerCase().replace(reg, "");
  var str1 = str0.split("").reverse().join("");
  return str0 === str1;
}

翻轉(zhuǎn)字符串

function reverseString(str) {
  return str.split("").reverse().join("");
}

字符串中出現(xiàn)最多次數(shù)的字符

function findMaxDuplicateChar(str) {
  var cnt = {}, //用來記錄所有的字符的出現(xiàn)頻次
      c = ""; //用來記錄最大頻次的字符
  for (var i = 0; i < str.length; i++) {
    var ci = str[i];
    if (!cnt[ci]) {
      cnt[ci] = 1;
    } else {
      cnt[ci]++;
    }
    if (c == "" || cnt[ci] > cnt[c]) {
      c = ci;
    }
  }
  return c;
}

字符串去重

function unique(s) {
  // 1.利用Set去重 2.變?yōu)閿?shù)組 3.變?yōu)樽址?
  // join里一定要有""，否則會自動插入","，就得[...new Set(s)].join().replace(/,/g, "")
  return [...new Set(s)].join("")
}

字符串去除空白字符

str.replace(/s/g, "")    //去除所有空白字符
str.replace(/^s*/g, "")    //去除最前的空白字符
str.replace(/s*$/g, "")    //去除最后的空白字符
str.replace(/(^s*)|(s*$)/g, "")    //去除最前和最后的空白字符

三、數(shù)組

數(shù)組去重

利用新數(shù)組

function uniqueArray(arr) {
 var temp = [];
 for (var i = 0; i < arr.length; i++) {
   if (temp.indexOf(arr[i]) === -1) {
   // if (arr.indexOf(arr[i]) === i) {
     temp.push(arr[i]);
   }
 }
 return temp;
}

對原數(shù)組splice

function uniqueArray(arr) {
  for (var i = 0; i < arr.length; i++) {
     if (arr.indexOf(arr[i]) != i) {
         arr.splice(i,1);    //刪除重復(fù)元素
         i--;    //數(shù)組下標(biāo)回退
     }
  }
  return arr;
}

對原數(shù)組filter

function uniqueArray(arr) {
  return arr.filter((item, index, thisArr) => {
    return thisArr.indexOf(item) === index;
  })
}

利用Set

function uniqueArray(arr) {
 return Array.from(new Set(arr));
 //return [...new Set(arr)];  使用擴(kuò)展運(yùn)算符效果一致
}

利用簡單對象映射（缺點(diǎn)：無法正確識別數(shù)組元素為"1"與1的區(qū)別）

function uniqueArray(arr) {
  var map = {},
    ret = [];
  for (var i = 0; i < arr.length; i++) {
    var item = arr[i];
    if (!map[item]) {
      map[item] = true;
      ret.push(item);
    }
  }
  return ret;
}

針對以上做法缺點(diǎn)，可以將普通對象改為Map對象

function uniqueArray(arr) {
  var map = new Map(),
      ret = [];
  for (var i = 0; i < arr.length; i++) {
    var item = arr[i];
    if (!map.get(item)) {
      map.set(item, true);
      ret.push(item);
    }
  }
  return ret;    
}

利用sort（缺點(diǎn)：數(shù)組順序被打亂）

function uniqueArray(arr) {
  arr.sort();
  var temp = arr[0];
  for (var i = 1; i < arr.length; i++) {
    if (arr[i] == temp) {
      arr.splice(i, 1); //刪除重復(fù)元素
    } else {
      temp = arr[i];
    }
  }
  return arr;
}

嗯。還是Array.from(new Set(arr))最好（lan）(￣▽￣)"

數(shù)組扁平化
arr = [1, [2, 3], [4, 5, [6]]];
flatten(arr) = [1, 2, 3, 4, 5, 6]

數(shù)組->字符串->數(shù)組（不合適數(shù)字+字符數(shù)組，因?yàn)閿?shù)字會被轉(zhuǎn)成字符串）

arr.join().split(",")
arr.toString().split(",")

Array自帶

arr.flat(Infinity)

遞歸實(shí)現(xiàn)

function flatten(arr) {
  var ret = [];
  for (var i = 0; i < arr.length; i++) {
    if (Array.isArray(arr[i])) {
      ret.push.apply(ret, flatten(arr[i]));
      // ret = ret.concat(flatten(arr[i]));
    } else {
      ret.push(arr[i]);
    }
  }
  return ret;
}

some實(shí)現(xiàn)

function flatten(arr) {
  while (arr.some(item => Array.isArray(item))) {
    arr = [].concat.apply([], arr); //一次降一維
    //arr = [].concat(...arr); //使用展開運(yùn)算符 效果一致
  }
  return arr;
}

reduce實(shí)現(xiàn)

function flatten(arr) {
  return arr.reduce((total, currentValue) => {
    return total.concat(Array.isArray(currentValue) ? flatten(currentValue) : currentValue);
  }, []);
}

四、查找

二分查找

//二分查找
function binary_search(arr, l, r, v) {
  if (l > r) {
    return -1;
  }
  var m = parseInt((l + r) / 2);
  if (arr[m] == v) {
    return m;
  } else if (arr[m] < v) {
    return binary_search(arr, m+1, r, v);
  } else {
    return binary_search(arr, l, m-1, v);
  }
}

將二分查找運(yùn)用到之前的插入排序中，形成二分插入排序，據(jù)說因?yàn)槎植檎姨岣吡嗽瓉眄樞虿檎业男?，所以可以提高效率?/p>

//二分插入排序（折半插入排序）
function binary_insertionSort(arr) {
  var len = arr.length,
      l, r, m;
  for (var i = 1; i < len; i++) {
    l = 0;
    r = i - 1;
    while(l <= r) {
        m = parseInt((l + r) / 2);
      if (arr[i] < arr[m]) {
          r = m - 1;
      } else {
        l = m + 1;
      }
    }
    arr.splice(r + 1, 0, arr.splice(i, 1)[0]);
  }
  return arr;
}

五、樹的搜索/遍歷

深度優(yōu)先搜索

//深搜 非遞歸實(shí)現(xiàn)
function dfs(node) {
  var nodeList = [];
  if (node) {
    var stack = [];
    stack.push(node);
    while(stack.length != 0) {
      var item = stack.pop();
      nodeList.push(item);
      var children = item.children;
      for (var i = children.length-1; i >= 0; i--) {
        stack.push(children[i]);
      }
    }
  }
  return nodeList;
}

//深搜 遞歸實(shí)現(xiàn)
function dfs(node, nodeList) {
  if (node) {
    nodeList.push(node);
    var children = node.children;
    for (var i = 0; i < children.length; i++) {
      dfs(children[i], nodeList);
    }
  }
  return nodeList;
}

廣度優(yōu)先搜索

//廣搜 非遞歸實(shí)現(xiàn)
function bfs(node) {
    var nodeList = [];
    if (node != null) {
        var queue = [];
        queue.unshift(node);
        while (queue.length != 0) {
            var item = queue.shift();
            nodeList.push(item);
            var children = item.children;
            for (var i = 0; i < children.length; i++)
                queue.push(children[i]);
        }
    }
    return nodeList;
}

//廣搜 遞歸實(shí)現(xiàn)
var i=0;  //自增標(biāo)識符
function bfs(node, nodeList) {
    if (node) {
      nodeList.push(node);
      if (nodeList.length > 1 && node.nextElementSibling) {
        bfs(node.nextElementSibling, nodeList);  //搜索當(dāng)前元素的下一個兄弟元素
      }
      node = nodeList[i++];
      bfs(node.firstElementChild, nodeList); //該層元素節(jié)點(diǎn)遍歷完了，去找下一層的節(jié)點(diǎn)遍歷
    }
    return nodeList;
}

廣搜的遞歸版本我需要使用到函數(shù)體外的變量i，不知道大家有沒有更好的方法，懇請賜教~

六、數(shù)字

隨機(jī)選取任意范圍的數(shù)字

function getRandomNumber(left, right) {
  var len = right - left + 1;
  return Math.floor(Math.random() * len + left);
}

求解斐波那契數(shù)列（0，1，1，2，3...）的某一項(xiàng)

function fb(n) {
  var a = 1,
      b = 1,
      ret;
  if(n == 0) ret = 0;
  else if(n == 1 || n == 2) ret = 1;
  for(var i=3; i<=n; ++i) {
      ret = a + b;
      a = b;
      b = ret;
  }
  return ret;
}

持續(xù)更新中~~~

云服務(wù)器 GPU云服務(wù)器字符串碎片整理算法常見機(jī)器學(xué)習(xí)算法機(jī)器學(xué)習(xí)常見算法 webrtc之vad算法

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/104017.html

發(fā)表評論

登陸后可評論

0條評論

cc17

男|高級講師

我要關(guān)注我要私信

TA的文章

java基礎(chǔ) 面試題

閱讀 993·2021-11-24 09:39
#黑五#云鼎互聯(lián)：美國VPS五折優(yōu)惠，三網(wǎng)聯(lián)通9929，最低9.9元/月起

閱讀 2214·2021-11-16 11:54
HMBCloud半月灣雙11活動：廣港移動IPLC 500Mbps流量轉(zhuǎn)發(fā)$49.99/年起，美國洛

閱讀 2096·2021-11-11 17:22
傲游主機(jī)(aoyoyun)：荷蘭/美國聯(lián)通CU2 VPS(AS10099+AS9929)，月付58元

閱讀 2382·2021-09-30 09:55
#七夕#RangCloud：香港BGP云主機(jī)CN2直連七夕節(jié)7折促銷，月付

閱讀 3611·2021-08-12 13:22
用小程序·云開發(fā)打造功能全面的博客小程序丨實(shí)戰(zhàn)

閱讀 1638·2019-08-30 15:44
前端實(shí)例練習(xí) - 提示按鈕

閱讀 1180·2019-08-29 12:12
依賴包的優(yōu)先級設(shè)置

閱讀 3275·2019-08-27 10:58

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

Javascript之常見算法整理（持續(xù)更新）

相關(guān)文章

**前端最實(shí)用書簽(持續(xù)更新)**

前端基礎(chǔ)入門

**php 面試題目整理（持續(xù)更新）**

**php 面試題目整理（持續(xù)更新）**

發(fā)表評論

0條評論

cc17

男|高級講師

TA的文章

java基礎(chǔ) 面試題

#黑五#云鼎互聯(lián)：美國VPS五折優(yōu)惠，三網(wǎng)聯(lián)通9929，最低9.9元/月起

HMBCloud半月灣雙11活動：廣港移動IPLC 500Mbps流量轉(zhuǎn)發(fā)$49.99/年起，美國洛

傲游主機(jī)(aoyoyun)：荷蘭/美國聯(lián)通CU2 VPS(AS10099+AS9929)，月付58元

#七夕#RangCloud：香港BGP云主機(jī)CN2直連七夕節(jié)7折促銷，月付

用小程序·云開發(fā)打造功能全面的博客小程序丨實(shí)戰(zhàn)

前端實(shí)例練習(xí) - 提示按鈕

依賴包的優(yōu)先級設(shè)置

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

Javascript之常見算法整理（持續(xù)更新）

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！