排序算法

冒泡排序

冒泡排序比较所有相邻的两个项，如果第一个比第二个大，则交换它们。元素项向上移动至正确的顺序，就好像气泡升至表面一样，冒泡排序因此得名。

function bubbleSort(array) {
    const { length } = array
    for (let i = 0; i < length; i++) {
        for (let j = 0; j < length - 1; j++) {
            if (array[j] > array[j + 1]) {
                [array[j], array[j + 1]] = [array[j + 1], array[j]]
            }
        }
    }
    return array
}

改进后的冒泡排序

如果从内循环减去外循环中已跑过的轮数，就可以避免内循环中所有不必要的比较

function modifiedBubbleSort(array) {
    const { length } = array
    for (let i = 0; i < length; i++) {
        for (let j = 0; j < length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                [array[j], array[j + 1]] = [array[j + 1], array[j]]
            }
        }
    }
    return array
}

选择排序

选择排序算法是一种原址比较排序算法。选择排序大致的思路是找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位

function selectionSort(array) {
    const { length } = array
    let indexMin
    for (let i = 0; i < length; i++) {
        indexMin = i
        for (let j = i + 1; j < length; j++) {
            if (array[indexMin] > array[j]) {
                indexMin = j
            }
        }
        if (i !== indexMin) {
            [array[i], array[indexMin]] = [array[indexMin], array[i]]
        }
    }
    return array
}

插入排序

插入排序每次排一个数组项，以此方式构建最后的排序数组。假定第一项已经排序了。接着，它和第二项进行比较——第二项是应该待在原位还是插到第一项之前呢？这样，头两项就已正确排序，接着和第三项比较

function insertionSort(array) {
    const { length } = array
    for (let i = 1; i < length; i++) {
        let j = i
        let tem = array[i]
        while (j > 0 && array[j - 1] > tem) {
            array[j] = array[j - 1]
            j--
        }
        array[j] = tem
    }
    return array
}

快速排序

创建两个数组(left right) 用中间项和其它项比较，比中间项小的放在左边数组 比中间项大的放在右边数组... 左边数组和右边数组均按照以上思路 进行排序

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr
    }
    var mind = Math.floor(arr.length / 2)
    var mid = arr.splice(mind, 1)
    var left = []
    var right = []
    for (var i = 0; i < arr.length; i++) {
        var cur = arr[i]
        if (cur < mid) {
            left.push(cur)
        } else {
            right.push(cur)
        }
    }
    return quickSort(left).concat(mid, quickSort(right))
}