[常用算法整理]javascript algorithm

264

排序算法

  • 冒泡排序 (bubbleSort)

    const bubbleSort = arr => {
        let swapped = false
        const a = [...arr]
        for(let i = 1; i < a.length; i ++) {
            swapped = false
            for(let j = 0; j < a.length - i; j ++) {
                if(a[j + 1] < a[j]) {
                    [a[j], a[j + 1]] = [a[j + 1], a[j]]
                    swapped = true
                }
            }
            if(!swapped) return a
        }
        return a
    }
    
  • 插入排序 (insertionSort)

    const insertionSort = arr => 
        arr.reduce((acc, x) => {
            if(!acc.length) return [x]
            acc.some((y, idx) => {
                if(x <= y) {
                    acc.splice(idx, 0, x)
                    return true
                }
                if(x > y && idx === acc.length - 1) {
                    acc.splice(idx + 1, 0, x)
                    return true
                }
                return false
            })
            return acc
        }, [])
    
  • 选择排序 (selectionSort)

    const selectionSort = arr => {
        const a = [...arr]
        for(let i = 0; i < a.length; i ++) {
            // acc为min值下标
            const minIdx = a
                .slice(i + 1)
                .reduce((acc, val, j) => val < a[acc] ? j + i + 1 : acc, i)
            if(minIdx !== i) [a[i], a[minIdx]] = [a[minIdx], a[i]]
        }
        return a
    }
    
  • 快速排序 (quickSort)

    const quickSort = arr => {
        const a = [...arr]
        if(a.length < 2) return a
        const pivotIdx = Math.floor(arr.length / 2)
        const pivot = a[pivotIdx]
        const [left, right] = a.reduce(
            (acc, val, i) => {
                if(val < pivot || (val === pivot && i !== pivotIdx)) {
                    acc[0].push(val)
                } else if(val > pivot) {
                    acc[1].push(val)    
                }
                return acc
            },
            [[], []]
        )
        return [...quickSort(left), pivot, ...quickSort(right)]
    }
    
  • 归并排序 (mergeSort)

    const mergeSort = arr => {
        if(arr.length < 2) return arr
        const mid = Math.floor(arr.length / 2)
        const left = mergeSort(arr.slice(0, mid))
        const right = mergeSort(arr.slice(mid, arr.length))
        return Array.from({  length: left.length + right.length }, () => {
            if(!left.length) return right.shift()
            if(!right.length) return left.shift()
            return left[0] < right[0] ? left.shift() : right.shift()
        })
    }
    
  • 桶排序 (bucketSort)

    const bucketSort = (arr, size = 5) => {
        const min = Math.min(...arr)
        const max = Math.max(...arr)
        const buckets = Array.from(
            { length: Math.floor((max - min) / size) + 1 },
            () => []
        )
        arr.forEach(val => {
            buckets[Math.floor((val - min) / size)].push(val)
        })
        return buckets.reduce((acc, bucket) => [...acc, ...bucket.sort((a, b) => a - b)], [])
    }
    
  • 堆排序 (heapSort)

    const heapSort = arr => {
        const a = [...arr]
        const len = a.length
        const heapify = (a, i) => {
            const left = 2 * i + 1
            const right = 2 * i + 2
            let max = i
            if(left < len && a[left] > a[max]) max = left
            if(right < len && a[right] > a[max]) max = right
            if(max !== i) {
                [a[max], a[i]] = [a[i], a[max]]
                headify(a, max)
            }
        }
    
        for(let i = Math.floor(len / 2); i >= 0; i -- ) heapify(a, i)
        for(i = a.length - 1; i > 0; i --) {
            [ a[0], a[i] ] = [ a[i], a[0] ]
            len --
            heapify(a, 0)
        }
        return a
    }
    

其他常用算法

洗牌算法 (shuffle)

const shuffle = arr => {
    let m = arr.length
    while(m) {
        const i = Math.floor(Math.random() * m--);
        [ arr[m], arr[i] ] = [ arr[i], arr[m] ]
    }
    return arr
}

最小公约数 (lcm)

const lcm = arr = {
    const gcd = (x, y) => (!y ? x : gcd(y, x % y))
    const _lcm = (x, y) => (x * y) / gcd(x, y)
    return [...arr].reduce((a, b) => _lcm(a, b))
}

最大公因数 (gcd)

const gcd = arr => {
    const _gcd = (x, y) => (!y ? x : _gcd(y, x % y))
    return [...arr].reduce((x, y) => _gcd(x, y))
}

indexOfSubStrings

const indexOfSubStrings = function* (str, searchVal) {
    let i = 0
    while(true) {
        const r = str.indexOf(searchVal, i)
        if(r !== -1) {
            yield r
            i = i + 1
        } else return
    }
}

参考来源: https://www.30secondsofcode.org/js/t/algorithm/p/1