关于javascript:排序算法总结

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)

2. 抉择排序

   • 找到数组中的最小值，选中它并将其搁置在第一位
   • 接着找到第二小的值，选中它并将其放在第二位
   • 执行 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)

3. 插入排序

   • 从第二个数往前比
   • 比它大就往后排
   • 以此类推进行到最初一个数
   • 工夫复杂度 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)

4. 归并排序

   • 分：把数组劈成两半，再递归对子数组进行“分”的操作，直到分成一个个独自的数
   • 合：把两个数合并成有序数组，再对有序数组进行合并，直到全副数组合并为一个残缺数组
   • 工夫复杂度 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)

5. 疾速排序

   • 分区：从数组中任意抉择一个“基准”，所有比基准小的元素放在基准后面，比基准大的元素放在基准前面。
   • 递归：递归地对基准前后的子数组进行分区。
   • 工夫复杂度 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)