常见代码
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. 常见算法
- 冒泡排序
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) |
稳定 |
- 选择排序
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) |
不稳定 |
- 插入排序
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) |
稳定 |
- 希尔排序
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) |
不稳定 |
- 快速排序
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)) |
不稳定 |
- 二分查找(折半查找)
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
