# 排序算法
* 冒泡排序 (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
![[常用算法整理]javascript algorithm](https://image.hyzed.cn/blog/484bcf1ca4d77859e911dc5c6e3a78c7.jpg)
[常用算法整理]javascript algorithm