前端实现归并排序(Merge Sort)算法
前端  /  管理员 发布于 8年前   665
归并排序(Merge Sort)是建立归并操作上的一种有效,稳定的排序算法,该算法是采用分治法的一个非常典型的应用
将已有序的子序列合并,得到完全有序的序列,即先使每个子序列有序,再使子序列段间有序
例如对于含有 n
个记录的无序表,首先默认表中每个记录各为一个有序表(只不过表的长度都为 1)
然后进行两两合并,使 n
个有序表变为n/2
个长度为 2 或者 1 的有序表(例如 4 个小有序表合并为 2 个大的有序表)
通过不断地进行两两合并,直到得到一个长度为 n
的有序表为止
例如对无序表{49,38,65,97,76,13,27}进行归并排序分成了分、合两部分:
如下图所示:
归并合过程中,每次得到的新的子表本身有序,所以最终得到有序表
上述分成两部分,则称为二路归并,如果分成三个部分则称为三路归并,以此类推
关于归并排序的算法思路如下:
分:把数组分成两半,再递归对子数组进行分操作,直至到一个个单独数字
合:把两个数合成有序数组,再对有序数组进行合并操作,直到全部子数组合成一个完整的数组
用代码表示则如下图所示:
function mergeSort(arr) { // 采用自上而下的递归方法
const len = arr.length;
if(len < 2) {
return arr;
}
let middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
const result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
上述归并分成了分、合两部分,在处理分过程中递归调用两个分的操作,所花费的时间为2乘T(n/2)
,合的操作时间复杂度则为O(n)
,因此可以得到以下公式:
总的执行时间 = 2 × 输入长度为n/2
的sort
函数的执行时间 + merge
函数的执行时间O(n)
当只有一个元素时,T(1) = O(1)
如果对T(n) = 2 * T(n/2) + O(n)
进行左右 / n的操作,得到 T(n) / n = (n / 2) * T(n/2) + O(1)
现在令 S(n) = T(n)/n
,则S(1) = O(1)
,然后利用表达式带入得到S(n) = S(n/2) + O(1)
所以可以得到:S(n) = S(n/2) + O(1) = S(n/4) + O(2) = S(n/8) + O(3) = S(n/2^k) + O(k) = S(1) + O(logn) = O(logn)
综上可得,T(n) = n * log(n) = nlogn
关于归并排序的稳定性,在进行合并过程,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也不会交换,由此可见归并排序是稳定的排序算法
在外排序中通常使用排序-归并的策略,外排序是指处理超过内存限度的数据的排序算法,通常将中间结果放在读写较慢的外存储器,如下分成两个阶段:
例如,使用100m内存对900m的数据进行排序,过程如下:
123 在
Clash for Windows作者删库跑路了,github已404中评论 按理说只要你在国内,所有的流量进出都在监控范围内,不管你怎么隐藏也没用,想搞你分..原梓番博客 在
在Laravel框架中使用模型Model分表最简单的方法中评论 好久好久都没看友情链接申请了,今天刚看,已经添加。..博主 在
佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 @1111老铁这个不行了,可以看看近期评论的其他文章..1111 在
佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 网站不能打开,博主百忙中能否发个APP下载链接,佛跳墙或极光..路人 在
php中使用hyperf框架调用讯飞星火大模型实现国内版chatgpt功能示例中评论 教程很详细,如果加个前端chatgpt对话页面就完美了..Copyright·© 2019 侯体宗版权所有· 粤ICP备20027696号