乐趣区

关于前端:归并排序算法

归并排序

原文链接:https://note.noxussj.top/?source=sifo

什么是归并排序(mergeSort)?

次要分成两局部实现,分、合操作:

  • 分:把数组分成两半,在递归地对子数组进行 “ 分 ” 操作,直到分成一个个独自的数
  • 合:把两个数组合并为有序数组,再对有序数组进行合并,直到全副子数组合并为一个残缺数组

归并排序就是采纳了分而治之的算法设计思维,另外归并排序其实就像擂台赛一样,每两组进行 pk,最初到半决赛,总决赛相似。


算法步骤

  1. 通过 Math.floor 将指标数组劈成两半,左边可能会多进去一个
  2. 通过递归的形式对方才合成进去的数组,再次进行劈成两半操作
  3. 直到劈成数组变成一个为止
  4. 开始进行合并操作,对两个数组进行遍历排序,小的放右边,大的放左边
  5. 始终合并到最大的数组
  6. 排序实现

动画演示链接

https://visualgo.net/zh/sorting


根底案例

  • 工夫复杂度:O (n * logn)
  • 空间复杂度:O (1)
    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)
            const res = []
    
            while (orderLeft.length || orderRight.length) {if (orderLeft.length && orderRight.length) {res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
                } else if (orderLeft.length) {res.push(orderLeft.shift())
                } else if (orderRight.length) {res.push(orderRight.shift())
                }
            }
    
            return res
        }
    
        const res = rec(this)
    
        res.forEach((n, i) => {this[i] = n
        })
    }
    
    const arr = [5, 4, 3, 2, 1]
    
    arr.mergeSort() // [1, 2, 3, 4, 5]

“ 分 ” 工夫复杂度是 O (logn),” 合 ” 工夫复杂度是 O (n),所以整体的工夫复杂度为 O (n * logn)。代码中没有借助其余数据结构来存储线性增长的元素,所以空间复杂度为 O (1)。


原文链接:https://note.noxussj.top/?source=sifo

退出移动版