Mcbai

JS编程: 归并排序

原文链接: hackernoon.com

JS编程: 归并排序

想成为一个更好的开发者,那么理解数据结构、算法和基本编程思想是必须的。现在大多数问题都被现代工具和各种库解决了,但是对这些领域有一个更深的了解,将会大大拓宽你软件开发的视野。

就我自己而言,掌握这些概念是相当困难的,因为在我每天的工作里,几乎都不用这些。我正在写的这一系列文章就是为了提升我和那些跟我一样的人对这些方面的理解。

什么是归并排序(Merge Sort)?

在计算机科学中,归并排序是一种常用的排序算法。Firefox和Safari在实现Array.prototype.sort()时,使用便是这种算法。 (记住在不同的浏览器,JavaScript行为方式并不一致)。归并排序性能很好,并且容易实现和理解。

所以,如何使用归并排序来排序列表,这个算法又是如何工作的? 它所围绕的观点是,更容易对两个已经排好序的数组进行排序,而不是一个没有排序的数组。 当我们有两个排好序的数组,我们会逐一比较他们的每个项,并且将较小的那个项放在结果列表。想象你有两个列表A和B,比较A[0]和B[0]。假设A[0]更小,我们就将它添加到结果列表,然后继续。接着比较A[1]和B[0],这次B[0]更小,所以我们就将B[0]添加到结果列表,然后继续比较A[1]和B[1],如此反复...

在排序结束时,任何剩下的变量都直接放在结果列表后——因为A和B两个数组已经排过序,并不会造成重排序。

那么它如何工作?

概念很容易理解,但是我们如何达到有两个排好序的数组的状态? 有多个项的数组除非排好序,否则无法进行比较。我们可以通过递归拆分数组,直到我们能比较多对单一项的时候为止,来实现这一点。

[1, 5, 3, 9, 6, 4, 8]
[1, 5, 3, 9] | [6, 4, 8]
[1, 5] | [3, 9] [6] | [4, 8]
[1] | [5] [3] | [9] [4] | [8]

这并不是最全面的模式,但是你能看见把一个数组怎样递归拆分成更小的数组,直到我们只拥有包含单个项的数组。这时,我们开始挨个将他们进行比较,并且用上述方法排序将我们的数组进行排序。

[9, 3, 6, 4]
[9, 3] | [6, 4]
[9] | [3] [6] | [4]
[3, 9] | [4, 6]
[3, 4, 6, 9]

换句话说就是,我们把数组拆分成多个最小的块,然后按照正确的顺序重新组装他们。这里是一个JavaScript中,利用slice方法的实现,用来得到数组中我们需要的部分。

// Split the array into halves and merge them recursively

function  mergeSort (arr) {

if (arr.length  ===  1) {

// return once we hit an array with a single item

return arr

}

const middle =  Math.floor(arr.length  /  2) // get the middle item of the array rounded down

const left =  arr.slice(0, middle) // items on the left side

const right =  arr.slice(middle) // items on the right side

return  merge(

mergeSort(left),

mergeSort(right)

)

}

// compare the arrays item by item and return the concatenated result

function  merge (left, right) {

let result = []

let indexLeft =  0

let indexRight =  0

while (indexLeft <  left.length  && indexRight <  right.length) {

if (left[indexLeft] < right[indexRight]) {

result.push(left[indexLeft])

indexLeft++

} else {

result.push(right[indexRight])

indexRight++

}

}

return  result.concat(left.slice(indexLeft)).concat(right.slice(indexRight))

}

const list = [2, 5, 1, 3, 7, 2, 3, 8, 6, 3]

console.log(mergeSort(list)) // [ 1, 2, 2, 3, 3, 3, 5, 6, 7, 8 ]

算法在你第一次阅读它们的时候并不是很明白,花一些时间在上面——一天、两天、一周,直到你弄懂它们。仅仅是阅读复制代码,并不能帮助你更好的思考,所以多花些额外的时间并围绕这个概念进行思考。

感谢你的阅读!你可以在我的个人资料里查看更多关于JS的文章,或者在这里查看更多计算机科学主题:

Programming with JS:

递归(Recursion): https://hackernoon.com/programming-with-js-recursion-31371e2bf808 归并排序(Merge Sort): https://medium.com/@KondovAlexander/programming-with-js-merge-sort-deb677b777c0 二分检索法(Binary Search): https://medium.com/@KondovAlexander/programming-with-js-binary-search-aaf86cef9cb3 插入排序(Insertion Sort): https://medium.com/@KondovAlexander/programming-with-js-insertion-sort-1316df8354f5