# 排序算法 * 冒泡排序 (bubbleSort) ```js 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) ```js 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) ```js 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) ```js 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) ```javascript 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) ```js 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) ```js 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) ```js 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) ```js 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) ```js const gcd = arr => { const _gcd = (x, y) => (!y ? x : _gcd(y, x % y)) return [...arr].reduce((x, y) => _gcd(x, y)) } ``` indexOfSubStrings ```js 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