JavaScript如何实现归并排序

　　介绍

小编给大家分享一下JavaScript如何实现归并排序,希望大家阅读完这篇文章之后都有所收获、下面让我们一起去探讨吧!

<强> JavaScript 栏目在本文中,我们学习归并排序背后的逻辑,并用JavaScript实现。最后,在空间和时间复杂度方面将归并排序与其他算法进行比较。

<强>归并排序背后的逻辑

归并排序使用<>强分而治之的概念对给定的元素列表进行排序。它将问题分解为较小的子问题,直到它们变得足够简单以至可以直接解决为止。

以下是归并排序的步骤:

<李>

将给定的列表分为两半(如果列表中的元素数为奇数,则使其大致相等)。

<李>

以相同的方式继续划分子数组,直到只剩下单个元素数组。

<李>

从单个元素数组开始,<强>合并子数组,以便对每个合并的子数组进行排序。

<李>

重复第3步单元,直到最后得到一个排好序的数组。

以数组<代码>[4、8、7、2、11、1,3]为例,让我们看一下归并排序是如何工作的:

JavaScript如何实现归并排序

<强>用JavaScript实现归并排序

首先实现一个将两个已排序子数组合并为一个已排序数组的函数<代码>合并()> 合并()函数只用于其进行合并。

可以通过遍历这两个子数组来实现:

function 合并(左,右),{ 　　,,,let  arr =, [] 　　,,,//,如果任何一个数组为空,就退出循环 　　,,,while  (left.length ,,, right.length), { 　　,,,,,,,//,从左右子数组的最小元素中选择较小的元素 　　,,,,,,,if (左[0],& lt;,右[0]),{ 　　,,,,,,,,,,,arr.push (left.shift ()),, 　　,,,,,,,},{else  　　,,,,,,,,,,,arr.push (right.shift ()), 　　,,,,,,,} 　　,,,} 　　,,,, 　　,,,//,连接剩余的元素,防止没有把两个数组遍历完整 　　,,,return [,加勒比海盗,……左,,……right 】 　　}

在这个函数中,通过把两个排好序的子数组(<代码> ,<代码> )合并来获得一个排好序的大数组。首先,创建一个空数组。之后在左<代码> 和<代码>对两个子数组中最小元素中的较小的一个,并将其添加到空数组。我们只需要检查左<代码> 和<代码>对子数组中的第一个元素,因为它们是已排好序的。

在这个过程中,从子数组中删除了被选择的元素(通过<代码>转变(),函数实现)。继续这个过程,直到其中一个子数组变为空。最后把非空子数组的剩余元素(因为它们已经被排序)插入主数组的最后面。

现在有了合并两个已排序数组的代码,接下来为实现归并排序算法的最终代码。这意味着要继续分割数组,直到最终只包含一个元素的数组为止:

function 归并排序(数组),{ 　　const 才能;half =array.length /, 2 　　,, 　　如果才能(& lt; array.length  2) { 　　,,,return  array  　　,,} 　　,, 　　const 才能;left =, array.splice(0,,一半) 　　return 才能;合并(归并排序(左),归并排序(数组) 　　}

在代码中先确定中点,并用<代码>拼接()函数将数组分为两个子数组。如果元素数量为奇数,则左侧的元素数量会少一个。不断的划分数组,直到剩下单个元素的数组(<代码>数组。长度& lt;2> 合并()函数合并子数组。

代码实现后用前面的用例测试一下:

array =,(4, 8日,7日,,2,,,,1,,3]; 　　console.log(归并排序(数组));

输出符合预期:

1,2,3,4,7,8,11

<强>归并排序的效率

归并排序的最差时间复杂度为O (n \ \ log n)美元,与快速排序的最佳情时间复杂度相同。归并排序是目前最快的排序算法之一。

与快速排序不同,归并排序不是<强>就地强排序算法,这意味着除了输入数组之外,它还会占用额外的空间。这是因为我们使用了辅助数组来存储子数组。归并排序的空间复杂度为,O (n)美元。

归并排序的另一个优点是非常适合多线程,因为每个被划分出的一半都可以单独排序。另一种常见的减少归并排序运行时间的方法是在到达相对较小的子数组时(大约7个元素)使用插入排序。这是因为插入排序在处理小型或几乎排好序的数组时表现非常好。

JavaScript如何实现归并排序