冒泡排序

1. 交换符合条件的相邻数组
2. 顺序对所有元素进行1，除了最后一组。
3. 重复1、2，直到结束。

const sort = a => {
    let len = a.length
    for (let i = 0; i < len - 1; i++) {
        for (let j = 0; j < len - i - 1; j++) {
            if (a[j] > a[j + 1]) [a[j], a[j + 1]] = [a[j + 1], a[j]]
        }
    }
    return a
}

选择排序

1. 在未排序元素中找到最小元素的位置
2. 交换最小元素和第一位未排序元素
3. 重复1、2，直到结束

const sort = a => {
    let len = a.length
        for (let i = 0; i < len; i++) {
            let min = i
            for (let j = i; j < len; j++) {
                if (a[j] < a[min]) min = j
            }
            [a[min], a[i]] = [a[i], a[min]]
        }
    return a
}

插入排序

1. 将数组最后一个数拿出来
2. 插入到数组的合适位置中
3. 循环1，2，直至结束

const sort = a => {
    for (let i = 1, len = a.length; i < len; i++) {
        const s = a.pop()
        for (let j = i; j >= 0; j--) {
            if (s > a[j - 1]) {
                a.splice(j, 0, s)
                break
            } else if (j == 0) {
                a.splice(0, 0, s)
            }
        }
    }
    return a
}

归并排序

1. 递归的二分数组
2. 循环取左右数组较小的第一位，直到取完返回

const sort = a => {
    return (a.length == 1) ? a : _merge(sort(a.slice(0, ~~(a.length / 2))), sort(a.slice(~~(a.length / 2))))
}

const _merge = (left, right) => {
    const rtn = []
    while (left.length && right.length) rtn.push((left[0] <= right[0]) ? left.shift() : right.shift())
    while (left.length) rtn.push(left.shift())
    while (right.length) rtn.push(right.shift())
    return rtn
}

快速排序

1. 取一个基准值，按大小递归的二分数组
2. 合并小数组、基准值和大数组

const sort = a => {
    const len = a.length
    if (len < 2) return a
    const mid = a.splice(~~(len/2), 1), left = [], right = []
    for (let i = 0; i < len - 1; i++) {
        if (a[i] <= mid) {
            left.push(a[i])
        } else {
            right.push(a[i])
        }
    }
    return merge(sort(left), mid, sort(right))
}

const merge = (left, mid, right) => {
    return left.concat(mid.concat(right))
}

堆排序

1. 递归构造大顶堆／小顶堆
2. 循环交换堆首堆尾后推出最大／小的数然后再构造一次大／小顶堆

const resort = function(arr, i) {
    let max = i,
        left = i * 2 + 1,
        right = i * 2 + 2
    if (left < arr.length && arr[left] > arr[max]) max = left
    if (right < arr.length && arr[right] > arr[max]) max = right
    if (max != i) {
        arr.swap(i, max)
        resort(arr, max)
    }
}
const makeHeap = function (arr) {
    for (let i = ~~(arr.length / 2); i >= 0; i--) {
        resort(arr, i)
    }
}
Array.prototype.swap = function(i, j) {
    [this[i], this[j]] = [this[j], this[i]]
}
const heapSort = function() {
    for (let i = 0, len = a.length; i < len - 1; i++) {
        makeHeap(a)
        console.log(a.shift())
    }
}