常見(jiàn)代碼
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. 函數(shù)防抖
function debounce(fn, duration) {
let timer = null
return (...args) => {
if(timer) clearTimeout(timer)
timer = setTimeout(() => {
fn.apply(this, args)
clearTimeout(timer)
}, duration)
}
}
4. 函數(shù)節(jié)流
function throttle(fn ,duration) {
let flag = true
return (...args) => {
if(!flag) return
flag = false
setTimeout(() => {
fn.apply(this, args)
flag = true
}, duration)
}
}
5. 常見(jiàn)算法
- 冒泡排序
function bubbleSort(array) {
const length = array.length
// 外層循環(huán)決定每次遍歷到數(shù)組哪一位置
for (let i = length - 1; i > 0; i--) {
// 內(nèi)層循環(huán)對(duì)單次遍歷進(jìn)行兩兩元素對(duì)比交換操作
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
}
| 平均時(shí)間復(fù)雜度 |
最好情況 |
最壞情況 |
空間復(fù)雜度 |
穩(wěn)定性 |
| O(n2) |
O(n) |
O(n2) |
O(1) |
穩(wěn)定 |
- 選擇排序
function selectionSort(array) {
const length = array.length
// 外層循環(huán)決定每次遍歷的最小元素放置位置
for (let i = 0; i < length - 1; i++) {
let min = i
// 內(nèi)層循環(huán)對(duì)該位置后面所有元素進(jìn)行對(duì)比找蜜，查找最小元素下標(biāo)并交換
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
}
| 平均時(shí)間復(fù)雜度 |
最好情況 |
最壞情況 |
空間復(fù)雜度 |
穩(wěn)定性 |
| O(n2) |
O(n2) |
O(n2) |
O(1) |
不穩(wěn)定 |
- 插入排序
function insertionSort(array) {
const length = array.length
// 外層循環(huán)從第二個(gè)元素開(kāi)始遍歷到最后元素
for (let i = 1; i < length; i++) {
let temp = array[i]
let j = i
// 內(nèi)層循環(huán)查找該元素在前面的有序數(shù)列中的放置位置
while (j > 0 && array[j - 1] > temp) {
array[j] = array[j - 1]
j -= 1
}
array[j] = temp
}
return array
}
| 平均時(shí)間復(fù)雜度 |
最好情況 |
最壞情況 |
空間復(fù)雜度 |
穩(wěn)定性 |
| O(n2) |
O(n) |
O(n2) |
O(1) |
穩(wěn)定 |
- 希爾排序
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
}
| 平均時(shí)間復(fù)雜度 |
最好情況 |
最壞情況 |
空間復(fù)雜度 |
穩(wěn)定性 |
| O(nlog(n)) |
O(n) |
O(n2) |
O(1) |
不穩(wěn)定 |
- 快速排序
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)))
}
| 平均時(shí)間復(fù)雜度 |
最好情況 |
最壞情況 |
空間復(fù)雜度 |
穩(wěn)定性 |
| O(nlog(n)) |
O(nlog(n)) |
O(n2) |
O(log(n)) |
不穩(wě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. 斐波那契數(shù)列
function fibonacci(n) {
return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(5)) // 1 1 2 3 5
