之前,我们涵盖了一些(初学者排序算法)(https://andsky.com/tech/tutorials/js-bubble-selection-insertion-sort),可以完成工作,但很快就失去了更大的数据集的能力。
前提条件
能够通过 Big O Notation来思考时间和空间的复杂性将是非常有用的。
概念
类似于 二进制搜索, merge sort 是一种分割和征服算法,目标是将我们的问题分解成子问题,并反复继续分解这些问题,直到我们有许多简单的问题,我们可以很容易地把它们重新组合起来。
合并类型是建立在比较整个数组而不是单个项目的想法上。首先,我们需要把整个数组分成许多子数组,不断地将一切分成两半,直到一切都独自在自己的数组中。
从那里我们可以开始合并,因为两个数组应该已经分类,我们可以很容易地比较每个数字中的哪个数字更小,并将它们放在正确的地方。
正如你可以看到的那样,一半的数组在下一半之前完成,每一半的前半部分在下一半之前完成(不同的颜色代表不同的数组)。
图形 / 动画 通过 VisuAlgo.net
实践数据
这里是我将提及的50个未分类的项目的范围。
1const unsortedArr = [31, 27, 28, 42, 13, 8, 11, 30, 17, 41, 15, 43, 1, 36, 9, 16, 20, 35, 48, 37, 7, 26, 34, 21, 22, 6, 29, 32, 49, 10, 12, 19, 24, 38, 5, 14, 44, 40, 3, 50, 46, 25, 18, 33, 47, 4, 45, 39, 23, 2];
走
为了简化我们的问题,我们可以从创建一个实用函数开始,该函数将合并两个分类的数组. 有许多不同的方法来做到这一点,但我发现这是最简要的。
只要两个数组中有项目,请检查两个数组中的第一个项目是否较小,然后将其排序,然后用shift()将该项目从数组中删除。
因此,两组数逐步缩小,直到其中一个是空的,剩余被扔到尽头,因为它已经排序。
1const merge = (arr1, arr2) => {
2 let sorted = [];
3
4 while (arr1.length && arr2.length) {
5 if (arr1[0] < arr2[0]) sorted.push(arr1.shift());
6 else sorted.push(arr2.shift());
7 };
8
9 return sorted.concat(arr1.slice().concat(arr2.slice()));
10};
11
12console.log(merge([2, 5, 10, 57], [9, 12, 13]));
排序
这是一个简单的部分,我们可以使用回归函数来连续将我们的数组切成两半,使用slic()来保存中心的两侧数据,当我们有1个项目数组时,它将返回,然后我们将使用我们的合并实用程序开始将它们重新构建成一个大数组,每个合并将它们分类。
1const mergeSort = arr => {
2 if (arr.length <= 1) return arr;
3 let mid = Math.floor(arr.length / 2),
4 left = mergeSort(arr.slice(0, mid)),
5 right = mergeSort(arr.slice(mid));
6
7 return merge(left, right);
8};
9
10console.log(mergeSort(unsortedArr));
结论
虽然合并排序是迄今为止我们所涵盖的最佳算法,因为它是O(nlogn),但要记住,如果您不知道需要排序多少数据,请考虑使用另一个算法,例如插入排序,当数据集足够小以获得两个世界的最佳时。