数组各种排序算法的实现

[Jason-linjiayu]

冒泡排序

比较相邻元素，如果第一个比第二个大，则交换他们，一轮下来，最大的排在数组末尾，执行n-1轮完成排序

时间复杂度为O(n2)

Array.prototype.bubbleSort = function() {
    function swap(i,j,arr) {
        const temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
    }
    const sort = (arr) => {
    if(arr.length <= 1) return arr
        const n =arr.length
       for(let i=0;i<n;i++) {
           for(let j=i;j<n-i-1;j++) {
                if(arr[j] > arr[j+1]) {
                    swap(j,j+1,arr)
                }
           }
       }
       return arr

    }
    return sort(this)
}
const arr = [1,4,3,2,5,6,9,8,7]
const res = arr.bubbleSort()
console.log(res)

[Jason-linjiayu]

选择排序

遍历数组，把数组最小值放到第一位，把第二小的数放到第二位，以此类推，执行n-1轮

时间复杂度为O(n2)

Array.prototype.selectionSort = function() {
    function swap(i,j,arr) {
        const t = arr[i]
        arr[i] = arr[j]
        arr[j] = t
    }
    const sort = (arr) => {
        if(arr.length === 1) return arr
        const n = arr.length
        for(let i=0;i<n;i++) {
            let min = i
            for(let j=i;j<n;j++) {
                if(arr[min] > arr[j]) {
                    min = j
                }
            }
            if(i !== min ) {
                swap(min,i,arr)
            }
        }
        return arr
    }
    return sort(this)
}
const arr = [1,4,3,2,5,6,9,8,7]
const res = arr.selectionSort()
console.log(res)

[Jason-linjiayu]

插入排序

从第二个数然后排，比它大的就往后排，以此类推

时间复杂度为O(n2)

Array.prototype.selectSort = function() {
    if(this.length ===1) return;
    for(let i=1;i<this.length;i++) {
        let j=i
        const temp = this[i]
        while(j>=0 && this[j-1] > temp ) {
            this[j] = this[j-1]
            j--
        }
        this[j] = temp
    }
      return this
}
const arr = [1,4,3,2,5,6,9,8,7]
const res = arr.selectSort()
console.log(res)

[Jason-linjiayu]

归并排序

先把数组分成两半，递归地对数组进行排序，然后把子数组合并，分的时间复杂度是O(logN) 合的时间复杂度是O(n),总的时间复杂度为O(NlogN)。

Array.prototype.mergeSort = function() {

    const rec = (arr) => {
        if(arr.length === 1) return arr
        const mid = arr.length >> 1;
        const orderLeft = rec(arr.slice(0,mid))
        const orederRight = rec(arr.slice(mid))
        const res = []
        while(orderLeft.length || orederRight.length) {
            if(orderLeft.length && orederRight.length) {
                res.push(orderLeft[0] < orederRight[0] ? orderLeft.shift(): orederRight.shift())
            } else if(orderLeft.length) {
                res.push(orderLeft.shift())
            } else {
                res.push(orederRight.shift())
            }
        }
        return res
    }
    const res = rec(this)
    res.forEach((n,i) => this[i] = n)
    return res
}
const arr = [1,4,3,2,5,6,9,8,7]
const res = arr.mergeSort()
console.log(res,arr)

[Jason-linjiayu]

快速排序

从数组中任意找个基准，比基准小的放在左边，比基准大的放在右边。然后递归对子数组进行分区。

时间复杂度为O(logN)

Array.prototype.quickSort = function() {

    const sort = (arr) => {
        const n = arr.length;
        if(n <= 1) return arr
        const midIndex = n >> 1;
        const mid = arr.splice(midIndex,1)[0]
        const left = []
        const right = []
        for(let i=0;i<n-1;i++) {
            if(arr[i] < mid) {
                left.push(arr[i])
            } else {
                right.push(arr[i])
            }
        }
        return [...sort(left),mid,...sort(right)]
    }

    const res = sort(this)
    res.forEach((n,i) => this[i] = n);
    return res
}
const arr = [1,4,3,2,5,6,9,8,7]
const res = arr.quickSort()
console.log(res,arr)