本篇文章给大家带来的内容是关于JavaScript中归并排序的介绍（代码示例），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（pide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序
归并排序是一种非常稳定的排序方法，它的时间复杂度无论是平均，最好，最坏都是nlogn。
归并排序的2个步骤
先拆分，一直拆分到只有一个数
拆分完成后，开始递归合并
拆分过程
从上图可以看出，归并排序会将一个数组进行两两拆分，一直拆分到只有一个数的时候停止拆分。
那么拆分的代码就很简单了，就是得到一个指向中间的指针q，将数组拆分成(start,p)和（p，end）两个部分。
立即学习“Java免费学习笔记（深入）”；
p表示数组的开始下标
r表示数组的结束下标
function pide(p, r){ return Math.floor( (p + r) / 2 ); }
登录后复制
合并过程
合并的过程就如上图所示
遍历两组数据
进行对比大小
较小的那个值取出来放在第一个位置
举个例子：
假设现在数组A的数据是[2,5,1,3]
经过我们的拆分后会是(0,2),(2,4);
我们通过A.slice(0,2)和A.slice(2,4)=>得到两个数组A1[2,5]和A2[1,3]
然后我们对数组[2,5,1,3]进行遍历，第一次会得到两边较小的数1，第二次2，第三次3，第四次是5
function merge(A, p, q, r){ const A1 = A.slice(p, q); const A2 = A.slice(q, r); // 哨兵，往A1和A2里push一个最大值，比如防止A1里的数都比较小，导致第三次遍历某个数组里没有值 A1.push(Number.MAX_SAFE_INTEGER); A2.push(Number.MAX_SAFE_INTEGER); // 循环做比较，每次取出较小的那个值 for (let i = p, j = 0, k = 0; i < r; i++) { if (A1[j] < A2[k]) { A[i] = A1[j]; j++; } else { A[i] = A2[k]; k++; } } }
登录后复制
主程序
主程序就是做递归重复上面的操作了
function merge_sort(A, p = 0, r) { r = r || A.length; if (r - p === 1) { return; } const q = pide(p, r); merge_sort(A, p, q); merge_sort(A, q, r); merge(A, p, q, r); return A; }
登录后复制
完整代码
function pide(p, r) { return Math.floor((p + r) / 2); } function merge(A, p, q, r) { const A1 = A.slice(p, q); const A2 = A.slice(q, r); A1.push(Number.MAX_SAFE_INTEGER); A2.push(Number.MAX_SAFE_INTEGER); for (let i = p, j = 0, k = 0; i < r; i++) { if (A1[j] < A2[k]) { A[i] = A1[j]; j++; } else { A[i] = A2[k]; k++; } } } function merge_sort(A, p = 0, r) { r = r || A.length; if (r - p === 1) { return; } const q = pide(p, r); merge_sort(A, p, q); merge_sort(A, q, r); merge(A, p, q, r); return A; }
登录后复制
以上就是JavaScript中归并排序的介绍（代码示例）的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2734589.html
