常见代码整理

常见代码

1. 浅拷贝

1. function shallowClone(data) {
      if(typeof data !== 'object') return data
      // let obj = Object.prototype.toString.call(data) === '[object Array]' ? [] : {}
      let obj = data instanceof Array ? [] : {}
      for (let key in data) {
        if (data.hasOwnProperty(key)) {
          obj[key] = data[key]
        }
      }
      return obj
    }
2. Object.assign({}, data)

2. 深拷贝

1. function deepClone(data) {
      if(typeof data !== 'object') return data
      // let obj = Object.prototype.toString.call(data) === '[object Array]' ? [] : {}
      let obj = data instanceof Array ? [] : {}
      for (let key in data) {
        if (data.hasOwnProperty(key)) {
          obj[key] = deepClone(data[key])
        }
      }
      return obj
    }
2. JSON.parse(JSON.stringify(data))

3. 函数防抖

function debounce(fn, duration) {
   let timer = null
   return (...args) => {
      if(timer) clearTimeout(timer)
      timer = setTimeout(() => {
         fn.apply(this, args)
         clearTimeout(timer)
      }, duration)
   }
}

4. 函数节流

function throttle(fn ,duration) {
   let flag = true
   return (...args) => {
      if(!flag) return
      flag = false
      setTimeout(() => {
         fn.apply(this, args)
         flag = true
      }, duration)
   }
}

5. 常见算法

  1. 冒泡排序
function bubbleSort(array) {
  const length = array.length
  // 外层循环决定每次遍历到数组哪一位置
  for (let i = length - 1; i > 0; i--) {
    // 内层循环对单次遍历进行两两元素对比交换操作
    for (let j = 0; j < i; j++) {
      if (array[j] > array[j + 1]) {
        let temp = array[j]
        array[j] = array[j + 1]
        array[j + 1] = temp
      }
    }
  }
  return array
}
平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
O(n²) O(n) O(n²) O(1) 稳定
  1. 选择排序
function selectionSort(array) {
  const length = array.length
  // 外层循环决定每次遍历的最小元素放置位置
  for (let i = 0; i < length - 1; i++) {
    let min = i
    // 内层循环对该位置后面所有元素进行对比,查找最小元素下标并交换
    for (let j = min + 1; j < length; j++) {
      if (array[j] < array[min]) {
        min = j
      }
    }
    let temp = array[i]
    array[i] = array[min]
    array[min] = temp
  }
  return array
}
平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
O(n²) O(n²) O(n²) O(1) 不稳定
  1. 插入排序
function insertionSort(array) {
  const length = array.length
  // 外层循环从第二个元素开始遍历到最后元素
  for (let i = 1; i < length; i++) {
    let temp = array[i]
    let j = i
    // 内层循环查找该元素在前面的有序数列中的放置位置
    while (j > 0 && array[j - 1] > temp) {
      array[j] = array[j - 1]
      j -= 1
    }
    array[j] = temp
  }
  return array
}
平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
O(n²) O(n) O(n²) O(1) 稳定
  1. 希尔排序
function shellSort(array) {
  const length = array.length
  // 同插入排序,多了gap间隔值
  let gap = Math.floor(length / 2)
  while (gap > 0) {
    for (let i = gap; i < length; i++) {
      let temp = array[i]
      let j = i
      while (j > gap - 1 && array[j - gap] > temp) {
        array[j] = array[j - gap]
        j -= gap
      }
      array[j] = temp
    }
    gap = Math.floor(gap / 2)
  }
  return array
}
平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
O(nlog(n)) O(n) O(n²) O(1) 不稳定
  1. 快速排序
  • 指针法
function quickSort(array, left, right) {
  if (left >= right) {
    return array
  }
  let i = left
  let j = right
  const pivot = array[left]
  while (i < j) {
    while (i < j && array[j] >= pivot) {
      j--
    }
    while (i < j && array[i] <= pivot) {
      i++
    }
    if (i < j) {
      let temp = array[i]
      array[i] = array[j]
      array[j] = temp
    }
  }
  array[left] = array[i]
  array[i] = pivot
  quickSort(array, left, i - 1)
  quickSort(array, i + 1, right)
  return array
}
  • 数组法
function quickSort(array) {
  const length = array.length
  if (length <= 1) {
    return array
  }
  const smaller = []
  const bigger = []
  const pivot = array[0]
  for (let i = 1; i < length; i++) {
    if (array[i] <= pivot) {
       smaller.push(array[i])
    } else {
      bigger.push(array[i])
    }
  }
  return quickSort(smaller).concat(Array.of(pivot).concat(quickSort(bigger)))
}
平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
O(nlog(n)) O(nlog(n)) O(n²) O(log(n)) 不稳定
  1. 二分查找(折半查找)
  • 递归实现
function binarySearch(array, left, right, key) {
  if (left > right) {
      return -1
  }
  const center = Math.floor((left + right) / 2)
  if (array[center] === key) {
    return center
  } else if (array[center] > key) {
    right = center - 1
    return binarySearch(array, left, right, key)
  } else {
    left = center + 1
    return binarySearch(array, left, right, key)
  }
}
  • 非递归实现
function binarySearch(array, key) {
  let left = 0
  let right = array.length - 1
  if (left > right) {
      return -1
  }
  while (left <= right) {
    const center = Math.floor((left + right) / 2)
    if (array[center] === key) {
      return center
    } else if (array[center] > key) {
      right = center - 1
    } else {
      left = center + 1  
    }
  }
  return -1
}

6. 斐波那契数列

function fibonacci(n) {
  return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(5)) // 1 1 2 3 5
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
禁止转载,如需转载请通过简信或评论联系作者。
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,126评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,254评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,445评论 0 341
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,185评论 1 278
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,178评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,970评论 1 284
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,276评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,927评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,400评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,883评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,997评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,646评论 4 322
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,213评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,204评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,423评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,423评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,722评论 2 345

推荐阅读更多精彩内容

  • It is not worth the while to let our imperfections distur...
    文心武士阅读 210评论 0 0
  • 鲜松茸和干松茸的食用方法一样吗? 市场上的松茸在购买的时候一般是有几种选择,分别是新鲜松茸和干松茸以及冻干松茸等,...
    松茸鼎阅读 173评论 0 0
  • 阳光正好,窗外的一切似乎都在蠢蠢欲动,这是被压抑许久之后的躁动,花鸟鱼虫人,皆如此 不知是我的住处楼层较高的原因,...
    ilovepeace阅读 221评论 0 0
  • 我看见一朵花 开在春天里 开在烈日下 开在寒冬里 …… 最后 她开在我心里
    木子超然阅读 473评论 6 5
  • 五一放假,舍友都要回家,可是我没抢到票在学校也觉着无聊就来了一场说走就走的旅行。 正巧学校里有好多人也想一起去,也...
    蜗牛遇到盐阅读 367评论 1 11