排序算法总结

  1. 冒泡排序

    • 比较所有相邻元素,如果第一个比第二个大,则交换它们
    • 一轮下来,可以保证最后一个数是最大的
    • 执行n-1轮,就可以完成排序
    • 时间复杂度O(n^2)
Array.prototype.bubbleSort = function() {
    const len = this.length
    for(let i = 0; i < len - 1; i++) {          
        for(let j = 0; j < len - i - 1; j++) {  // 从前往后遍历
            if (this[j] > this[j + 1]) {
                const temp = this[j]
                this[j] = this[j + 1]
                this[j + 1] = temp
            }
        }
    }
    // 与上面等同
    // for(let i = 0; i < len - 1; i++) {
    //     for(let j = i; j >= 0; j--) {        // 从后往前遍历
    //         if (this[j] > this[j + 1]) {
    //             const temp = this[j]
    //             this[j] = this[j + 1]
    //             this[j + 1] = temp
    //         }
    //     }
    // }
}

const arr = [6,3,8,2,1]
console.log('排序前', arr)
arr.bubbleSort()
console.log('排序后', arr)

image.png

  1. 选择排序

    • 找到数组中的最小值,选中它并将其放置在第一位
    • 接着找到第二小的值,选中它并将其放在第二位
    • 执行n-1轮
    • 时间复杂度O(n^2)
Array.prototype.selectionSort = function () {
    let len = this.length
    let minIndex, temp
    for(let i = 0; i < len - 1; i++) {
        minIndex = i
        for(j = i + 1; j < len; j++) {
            if (this[j] < this[minIndex]) { // 寻找最小的数
                minIndex = j                // 保存最小数的索引
            }
        }
        temp = this[i]                      // 将最小数与第i个数交换
        this[i] = this[minIndex]
        this[minIndex] = temp
    }
}

const arr = [6,3,8,2,1]
console.log('排序前', arr)
arr.selectionSort()
console.log('排序后', arr)

image.png

  1. 插入排序

    • 从第二个数往前比
    • 比它大就往后排
    • 以此类推进行到最后一个数
    • 时间复杂度O(n^2)
Array.prototype.insertionSort = function() {
    const len = this.length
    let preIndex, current
    for(let i = 1; i < len; i++) {
        preIndex = i - 1
        current = this[i]
        while(preIndex >= 0 && this[preIndex] > current) {
            this[preIndex + 1] = this[preIndex]
            preIndex--
        }
        this[preIndex + 1] = current
    }
}

const arr = [7,0,6,3,4,2,5,1]
console.log('排序前', arr)
arr.insertionSort()
console.log('排序后', arr)

image.png

  1. 归并排序

    • 分:把数组劈成两半,再递归对子数组进行“分”的操作,直到分成一个个单独的数
    • 合:把两个数合并成有序数组,再对有序数组进行合并,直到全部数组合并为一个完整数组
    • 时间复杂度O(n*logN)
Array.prototype.mergeSort = function() {
    // 分(递归)
    const rec = (arr) => {
        if (arr.length === 1) return arr
        const mid = Math.floor(arr.length / 2)
        const left = arr.slice(0, mid)
        const right = arr.slice(mid, arr.length)
        const orderLeft = rec(left)
        const orderRight = rec(right)
        return merge(orderLeft, orderRight)
    }
    // 合
    const merge = (orderLeft, orderRight) => {
        const res = []
        while(orderLeft.length && orderRight.length) {
            if (orderLeft[0] < orderRight[0]) {
                res.push(orderLeft.shift())
            } else {
                res.push(orderRight.shift())
            }
        }
        while(orderLeft.length) {
            res.push(orderLeft.shift())
        }
        while(orderRight.length) {
            res.push(orderRight.shift())
        }
        return res
    }
    const res = rec(this)
    res.forEach((n, i) => this[i] = n)

}

const arr = [7,0,6,3,4,2,5,1]
console.log('排序前', arr)
arr.mergeSort()
console.log('排序后', arr)

image.png

  1. 快速排序

    • 分区:从数组中任意选择一个“基准”,所有比基准小的元素放在基准前面,比基准大的元素放在基准后面。
    • 递归:递归地对基准前后的子数组进行分区。
    • 时间复杂度O(n*logN)
Array.prototype.quickSort = function() {
    const rec = (arr) => {
        if (arr.length < 2) return arr
        const left = []
        const right = []
        const mid = arr[0]
        for(let i = 1; i < arr.length; i++) {
            if (arr[i] < mid) left.push(arr[i])
            else right.push(arr[i])
        }
        return [...rec(left), mid, ...rec(right)]
    }
    const res = rec(this)
    res.forEach((n, i) => this[i] = n)
}

const arr = [7,0,6,3,4,5,2,1]
console.log('排序前', arr)
arr.quickSort()
console.log('排序后', arr)

image.png

你可能感兴趣的